python带权无向图中邻接矩阵

在Python中，可以使用二维列表来表示带权无向图的邻接矩阵。邻接矩阵是一个方阵，其中的元素表示图中两个顶点之间的边权重。如果两个顶点之间没有边，则对应位置的元素为0或者无穷大。

下面是一个示例代码，展示了如何使用邻接矩阵表示带权无向图：

# 定义邻接矩阵
adjacency_matrix = [
    [0, 2, 0, 4, 0],
    [2, 0, 3, 0, 0],
    [0, 3, 0, 0, 1],
    [4, 0, 0, 0, 5],
    [0, 0, 1, 5, 0]
]

# 打印邻接矩阵
for row in adjacency_matrix:
    print(row)

输出结果为：

[0, 2, 0, 4, 0]
[2, 0, 3, 0, 0]
[0, 3, 0, 0, 1]
[4, 0, 0, 0, 5]
[0, 0, 1, 5, 0]

这个邻接矩阵表示了一个带权无向图，其中顶点之间的边的权重分别为2、4、3、1和5。

相关问题

用邻接矩阵储存带权无向图，并用这个带权无向图实现PRIM算法求最小生成树

假设带权无向图的邻接矩阵为 matrix，节点数为 n。PRIM 算法求最小生成树的代码如下：

def prim(matrix):
    n = len(matrix)
    # 用一个列表记录已经加入已有节点集合的节点
    visited = [0] * n
    # 将起点加入已有节点集合中
    visited[0] = 1
    # 用一个列表记录各个节点到已有节点集合的最短距离
    dist = matrix[0].copy()
    # 用一个列表记录已经加入已有节点集合的边
    edges = []
    # 重复 n-1 次，每次选择一个节点加入已有节点集合，直到所有节点都被加入
    for _ in range(n-1):
        # 找到距离已有节点集合最近的节点，加入已有节点集合中
        min_dist = float('inf')
        min_index = -1
        for i in range(n):
            if not visited[i] and dist[i] < min_dist:
                min_dist = dist[i]
                min_index = i
        visited[min_index] = 1
        # 将已有节点集合中的边加入 edges 列表中
        edges.append((min_index, dist[min_index]))
        # 更新其他节点到已有节点集合的距离
        for i in range(n):
            if not visited[i] and dist[i] > matrix[min_index][i]:
                dist[i] = matrix[min_index][i]
    return edges

其中 edges 列表中保存的是最小生成树中的边和其权重，每个元素为 (节点编号, 权重) 的形式。

无向图采用邻接矩阵进行存储，完成以下操作 (1) 建立无向图的邻接矩阵存储 (2) 输出邻接矩阵 (3) 基于图邻接矩阵的深度优先遍历 （4） 基于图邻接矩阵的广度优先遍历

无向图使用邻接矩阵存储时，它是一个二维数组，其中的行和列分别代表图中的顶点，矩阵的元素表示对应顶点之间的连接关系。如果两个顶点之间存在边，则对应位置的值为1或true；若不存在，则为0或false。

(1) **建立无向图的邻接矩阵存储**：
假设我们有一个无向图G，其顶点集合是V={v1, v2, ..., vn}。邻接矩阵A是一个n×n的矩阵，A[i][j]表示顶点vi到vj是否有边。初始时，所有元素都设为0，然后根据实际的边来填充：

A = [
  [0, 0, ..., 0],
  [0, 0, ..., 0],
  ...,
  [0, 0, ..., 0]
]

每添加一条边(vi, vj)，将A[i][j]和A[j][i]（因为无向图，边是双向的）置为1。

(2) **输出邻接矩阵**：
遍历并打印矩阵A，例如：

for i in range(n):
    for j in range(n):
        if A[i][j]:
            print(f'({i+1}, {j+1}): 1', end='\t')
    print()

(3) **基于图邻接矩阵的深度优先遍历（DFS）**：
DFS可以从任意顶点开始，利用栈数据结构实现：

def DFS(matrix, start, visited=None):
    if visited is None:
        visited = [False] * n
    visited[start] = True
    print(start + 1, end=' ')
    for neighbor in range(n):
        if matrix[start][neighbor] and not visited[neighbor]:
            DFS(matrix, neighbor, visited)

(4) **基于图邻接矩阵的广度优先遍历（BFS）**：
BFS使用队列，从起始顶点开始逐层遍历：

from collections import deque

def BFS(matrix, start):
    visited = [False] * n
    queue = deque([start])
    visited[start] = True
    while queue:
        vertex = queue.popleft()
        print(vertex + 1, end=' ')
        for neighbor in range(n):
            if matrix[vertex][neighbor] and not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)