无向图带权值的邻接矩阵
时间: 2023-11-10 17:03:00 浏览: 236
无向图带权值的邻接矩阵是一个 $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
```
其中,第一行和第一列表示节点的编号,其他位置表示对应节点之间的边的权值。
相关问题
无向图的存储邻接矩阵
无向图的存储邻接矩阵是指使用一个二维数组来表示无向图中各个顶点之间的关系,其中数组的行和列分别代表图中的顶点,而数组中的元素则表示相应顶点之间是否有边相连。如果两个顶点之间有边相连,则对应的数组元素为1,否则为0。由于无向图的邻接矩阵是对称的,因此只需要存储矩阵的一半即可。
下面是一个使用邻接矩阵来存储无向图的例子:
```python
class MGraph:
def __init__(self, vexnum, edgnum):
self.vexnum = vexnum # 顶点数
self.edgnum = edgnum # 边数
self.vexs = [] # 顶点集合
self.Edge = [] # 邻接矩阵
for i in range(self.vexnum):
self.Edge.append([0] * self.vexnum)
def createMGraph(self):
for i in range(self.vexnum):
self.vexs.append(input("请输入第%d个顶点的值:" % (i + 1)))
for k in range(self.edgnum):
i = input("请输入边的起点:")
j = input("请输入边的终点:")
w = input("请输入边的权值:")
self.Edge[i][j] = w
self.Edge[j][i] = w
```
建立无向图的邻接矩阵
建立无向图的邻接矩阵可以按照以下步骤进行:
1. 首先创建一个结构体来存储邻接矩阵的信息,包括一个存放顶点信息的一维数组(Vexs),一个存放边信息的二维数组(Edge),以及当前的顶点数和边数这四个变量。
2. 创建一个子函数CreateMGraph,用来创建无向图的邻接矩阵。在这个函数中,首先根据用户输入的顶点数和边数初始化邻接矩阵,将顶点与自身的边设为0,表示无边;将顶点与其他顶点的边设为“∞”,表示无边。然后,用户需要输入顶点与顶点之间的边的权值,如果没有权值,则输入-1表示有边但没有权值。完成输入后,调用子函数ShowpGraph,将邻接矩阵显示出来。
3. 子函数ShowpGraph用来输出创建的无向图的邻接矩阵。通过遍历邻接矩阵,将顶点和边的信息输出到控制台上即可。
通过以上步骤,就可以建立无向图的邻接矩阵,并将其显示出来。