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。

相关问题

建立一个带权无向图的邻接矩阵存储，再从0号顶点出发用Prim算法求该图的最小生成树，按顺序输出所得到的各条边

好的,我来为您解释如何使用邻接矩阵存储带权无向图,并使用Prim算法求最小生成树,同时按顺序输出所得到的各条边。

1. 建立邻接矩阵:
首先,我们需要建立一个二维数组来表示图的邻接矩阵。假设图有n个顶点,那么我们就创建一个n*n的矩阵。对于每一条边(u,v,w),我们将在矩阵的[u][v]和[v][u]位置填入权重w。如果两点之间没有边,则填入一个特殊值(如∞)表示无穷大。

2. Prim算法步骤:
a) 初始化:
- 创建一个大小为n的数组key,用于存储连接顶点的最小权重。
- 创建一个大小为n的数组parent,用于存储最小生成树的父节点。
- 创建一个大小为n的布尔数组inMST,用于标记顶点是否已经包含在最小生成树中。
- 将起始点(0号顶点)的key值设为0,其他顶点的key值设为∞。
- 将inMST数组的所有值设为false。

b) 主循环:
- 重复n次:
- 找到key值最小的、尚未包含在MST中的顶点u。
- 将u标记为已包含在MST中。
- 对于u的所有邻接顶点v:
- 如果v尚未包含在MST中,且边(u,v)的权重小于v的当前key值:
- 更新v的key值为边(u,v)的权重。
- 将u设为v的父节点。

3. 输出结果:
- 遍历parent数组,对于每个顶点(除了起始点),输出边(parent[i], i, key[i])。

下面是使用Python实现的代码示例:

import sys

def prim(graph):
    n = len(graph)
    key = [sys.maxsize] * n
    parent = [None] * n
    inMST = [False] * n
    key[0] = 0

    for _ in range(n):
        u = min_key(key, inMST)
        inMST[u] = True

        for v in range(n):
            if (graph[u][v] > 0 and not inMST[v] and
                    graph[u][v] < key[v]):
                key[v] = graph[u][v]
                parent[v] = u

    print_mst(parent, graph)

def min_key(key, inMST):
    min_val = sys.maxsize
    min_index = -1
    for i in range(len(key)):
        if key[i] < min_val and not inMST[i]:
            min_val = key[i]
            min_index = i
    return min_index

def print_mst(parent, graph):
    print("Edge \tWeight")
    for i in range(1, len(parent)):
        print(f"{parent[i]} - {i} \t{graph[i][parent[i]]}")

# 示例图
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

prim(graph)

这段代码会输出最小生成树的所有边及其权重。

用邻接矩阵储存带权无向图，并用这个带权无向图实现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 列表中保存的是最小生成树中的边和其权重，每个元素为 (节点编号, 权重) 的形式。