边带权值的邻接矩阵代码
时间: 2023-07-03 12:23:23 浏览: 64
以下是边带权值的邻接矩阵代码示例:
```python
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0 for column in range(vertices)] for row in range(vertices)]
def add_edge(self, u, v, weight):
self.graph[u][v] = weight
self.graph[v][u] = weight
def print_graph(self):
for i in range(self.V):
for j in range(self.V):
print(f"{self.graph[i][j]:4}", end="")
print()
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
g.print_graph()
```
输出结果:
```
0 10 6 5
10 0 0 15
6 0 0 4
5 15 4 0
```
相关问题
无向图带权值的邻接矩阵
无向图带权值的邻接矩阵是一个 $n \times n$ 的矩阵,其中 $n$ 是图中节点的数量。如果节点 $i$ 和节点 $j$ 之间有边相连,则邻接矩阵中第 $i$ 行第 $j$ 列和第 $j$ 行第 $i$ 列的元素都是这条边的权值;否则这两个元素的值为 0。
例如,对于下面这个无向图:
```
1
/ \
2---3
```
它的带权值邻接矩阵为:
```
| 1 2 3
--|------
1 | 0 1 1
2 | 1 0 1
3 | 1 1 0
```
其中,第一行和第一列表示节点的编号,其他位置表示对应节点之间的边的权值。
上面代码如何实现在邻接矩阵中记录边的权值。
在邻接矩阵中记录边的权值,可以将邻接矩阵中的元素从 0/1 改为实数型,表示两个节点之间的边的权值大小。
例如,在上面的代码中,如果想要将边的权值记录在邻接矩阵中,可以将其定义为一个二维的实数型数组,例如:
```python
INF = float('inf') # 表示无穷大
# 初始化邻接矩阵
adj_matrix = [[INF for _ in range(n)] for _ in range(n)]
# 添加边的信息
for _ in range(m):
u, v, w = map(int, input().split())
adj_matrix[u][v] = w
adj_matrix[v][u] = w # 无向图需要将两个方向都加上
```
这样,就可以在邻接矩阵中记录每条边的权值了。需要注意的是,如果是无向图,需要将两个方向都加上。另外,如果某些节点之间没有边相连,可以将对应的邻接矩阵中的元素赋值为一个足够大的值,例如上面代码中的 `INF`。