class Graph: def init(self, n, e): self.n = n # 图中顶点个数 self.e = e # 图中边的条数 self.arcs = [[float('inf')] * (n + 1) for _ in range(n + 1)] # 初始化邻接矩阵,用inf表示两点不直接相连 self.a = [[float('inf')] * (n + 1) for _ in range(n + 1)] # 存储最短距离 self.path = [[0] * (n + 1) for _ in range(n + 1)] # 存储最短路径 # 弗洛伊德算法 def floyd(self): for i in range(1, self.n + 1): for j in range(1, self.n + 1): self.a[i][j] = self.arcs[i][j] if i != j and self.a[i][j] < float('inf'): self.path[i][j] = i else: self.path[i][j] = 0 for k in range(1, self.n + 1): for i in range(1, self.n + 1): for j in range(1, self.n + 1): if self.a[i][k] + self.a[k][j] < self.a[i][j]: self.a[i][j] = self.a[i][k] + self.a[k][j] self.path[i][j] = self.path[k][j] for i in range(1, self.n + 1): for j in range(1, self.n + 1): if i != j: print(f'{i}到{j}的最短路径为{self.a[i][j]}:', end='') next = self.path[i][j] print(j, end='') while next != i: print(f'←{next}', end='') next = self.path[i][next] print(f'←{i}') # 计算最短距离之和 def add(self): sum = [0] * (self.n + 1) for i in range(1, self.n + 1): for j in range(1, self.n + 1): if i != j: sum[i] += self.a[i][j] print(f'{i}到各顶点的最短路径总和为{sum[i]}') address = 1 for i in range(2, self.n + 1): if sum[0] > sum[i]: sum[0] = sum[i] address = i print(f'所以最短路径总和为{sum[0]},学院超市的最佳选址为顶点{address}') if name == 'main': n = int(input('请输入图中顶点个数:')) e = int(input('请输入图中边的条数:')) t = Graph(n, e) print('学校超市最佳选址*') print() print('请输入存在路径的两个单位以及相通两个单位间的距离(用空格隔开)') print() for k in range(1, e + 1): i, j, w = map(float, input().split()) t.arcs[i][j] = w t.floyd() t.add() input('按回车键退出')
时间: 2024-02-20 12:59:35 浏览: 28
你的代码中出现了使用浮点数作为列表的索引的地方,具体是在这一行:
```python
i, j, w = map(float, input().split())
```
在这里,你将输入的三个数字分别赋值给了 i、j 和 w,但是输入的数字可能会包含小数点,导致 i 和 j 是浮点数,无法作为邻接矩阵的索引。你需要将 i 和 j 转换成整数,例如可以使用 `int()` 函数将它们转换成整数,例如:
```python
i, j, w = map(float, input().split())
i, j = int(i), int(j)
```
这样就可以将 i 和 j 转换成整数,避免了使用浮点数作为列表索引导致的错误。
相关问题
class adjMatrixGraph: # 构造方法,n个顶点m条边 def init(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表,默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g 根据上面代码编写一个广度优先搜索的函数
可以参考以下代码实现广度优先搜索:
```
from queue import Queue
class adjMatrixGraph:
# 构造方法,n个顶点m条边
def __init__(self, n, m):
self.verNum = n #顶点数
self.edgeNum = m #边数
self.vertex = [0] * n #顶点列表
self.edge = [[0 for i in range(self.verNum)] for j in range(self.verNum)] #邻接矩阵二维列表
self.vis = [False] * n #顶点的访问列表,默认没访问过
def addVertex(self, ls):
#添加顶点列表
self.vertex = ls
def addEdge(self, fr, to):
#添加边(fr,to)
ifr = self.vertex.index(fr) #起点下标
ito = self.vertex.index(to) #终点下标
self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵
# 广度优先搜索
def bfs(self, start):
visited = [False] * self.verNum # 标记所有节点是否被访问
q = Queue() # 创建队列
q.put(start) # 将起始节点入队
visited[self.vertex.index(start)] = True # 标记起始节点为已访问
while not q.empty(): # 队列非空
node = q.get() # 取队首节点
print(node, end=' ') # 输出节点值
# 遍历队首节点的所有邻居节点
for i in range(self.verNum):
if self.edge[self.vertex.index(node)][i] == 1 and not visited[i]:
visited[i] = True # 标记邻居节点为已访问
q.put(self.vertex[i]) # 将邻居节点入队
```
使用方式如下:
```
# 创建图对象
g = adjMatrixGraph(6, 7)
# 添加顶点列表
g.addVertex(['A', 'B', 'C', 'D', 'E', 'F'])
# 添加边
g.addEdge('A', 'B')
g.addEdge('A', 'C')
g.addEdge('B', 'D')
g.addEdge('C', 'D')
g.addEdge('C', 'E')
g.addEdge('D', 'E')
g.addEdge('D', 'F')
# 广度优先搜索
g.bfs('A')
```
输出结果为:`A B C D E F`
class adjMatrixGraph: # 构造方法,n个顶点m条边 def __init__(self,n,m): self.verNum = n #顶点数 self.edgeNum = m #边数 self.vertex = [0] * n #顶点列表 self.edge = [[0 for i in range(self.verNum)] \ for j in range(self.verNum)] #邻接矩阵二维列表 self.vis = [False] * n #顶点的访问列表,默认没访问过 def addVertex(self,ls): #添加顶点列表 self.vertex = ls def addEdge(self,fr,to):#添加边(fr,to) ifr = self.vertex.index(fr) #起点下标 ito = self.vertex.index(to) #终点下标 self.edge[ifr][ito] = self.edge[ito][ifr] = 1 #邻接矩阵 #邻接矩阵建图 def createGraph(): n,m = map(int,input().split()) #输入n个顶点和m条边 g = adjMatrixGraph(n,m) #创建无向图G g.addVertex(list(input().split())) #输入顶点列表 for i in range(m): #输入m条边 fr,to = input().split() g.addEdge(fr,to) return g 编写一个深度优先搜索得函数
以下是一个深度优先搜索函数的示例代码:
```python
def DFS(graph, start):
visited = [False] * graph.verNum # 初始化所有顶点为未访问状态
stack = [] # 栈用于存储待访问的顶点
stack.append(start) # 将起始顶点加入栈中
while stack:
# 取出栈顶元素作为当前访问的顶点
cur = stack.pop()
if not visited[cur]:
visited[cur] = True # 将当前顶点标记为已访问
print(graph.vertex[cur], end=' ') # 输出当前顶点的值
# 将当前顶点的未访问过的邻居加入栈中
for i in range(graph.verNum):
if graph.edge[cur][i] == 1 and not visited[i]:
stack.append(i)
```
其中,`graph` 参数是一个 `adjMatrixGraph` 对象,`start` 参数是起始顶点的下标。该函数首先初始化所有顶点为未访问状态,然后将起始顶点加入栈中。接着进入循环,每次取出栈顶元素作为当前访问的顶点,将其标记为已访问,并输出其值。然后将当前顶点的未访问过的邻居加入栈中,继续循环直到栈为空。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)