关于最小生成树的应用
已知带权无向图（如下所示），求最小生成树。Program2用图要求输出：(1)所有的边及权值，如：（‘a’,’b’,10）…(2)最小生成树所包含的边，如：（’a’,‘c’,‘weight’:8）…
prim算法
def findTree(G:dict):
start = list(G.keys())[0]
choice = [(start, i, j) for i, j in G[start].items()]
choice.sort(key=lambda x:x[2])
tree = list()
seen = {start}
while choice:
node = choice.pop(0)
if node[1] not in seen:
seen.add(node[1])
line = sorted([node[0],node[1]])
line.append(node[2])
tree.append(line)
for i, j in G[node[1]].items():
choice.append((node[1],i,j))
choice.sort(key=lambda x:x[2])
return tree
if __name__ == "__main__":
graph = {
"a":{"b":10, "c":8, "f":5},
"b":{"a":10, "d":9, "f":7},
"c":{"a":8, "e":10, "f":17},
"d":{"b":9, "e":11, "f":12, "g":4},
"e":{"c":10, "d":11, "f":3, "g":16},
"f":{"a":5, "b":7, "c":17, "d":12, "e":3},
"g":{"d":4, "e":16}
}
lines = set()
for node, value in graph.items():
for i, j in value.items():
temp = sorted([node,i])
temp.append(j)
lines.add(tuple(temp))
print(lines)
tree = findTree(graph)
print(tree)
- 这篇文章：关于最小生成树的考点 也许有你想要的答案，你可以看看
最小生成树（带权无向图）
这个类似的，借鉴下
#include<iostream>
#include<assert.h>
#include<string>
#include<limits.h>
#define NUM 7
using namespace std;
//利用二维数组创建有向图的邻接矩阵
void CreateMatrix(int mat[NUM][NUM]);
//利用Prim算法求解最小生成树
void DijkstraSearch(int mat[NUM][NUM], int i, int visit[NUM], int dist[NUM], int path[NUM]);
int main()
{
//创建有向图的带有权值的邻接矩阵
int mat[NUM][NUM];
for (int i = 0; i < NUM;i++)
{
for (int j = 0; j < NUM;j++)
{
mat[i][j] = INT_MAX;
}
}
CreateMatrix(mat);
int visit[NUM] = {0};
int dist[NUM];
for (int i = 0; i < NUM;i++)
{
dist[i] = INT_MAX;
}
int path[NUM] = {0};
//利用Prim算法求解最小生成树
//初始源点的dist初始化为0，path初始化为0
dist[0] = 0;
path[0] = 0;
DijkstraSearch(mat,0,visit,dist,path);
//输出最小生成树的边及相应权值，总权值
int totalValue = 0;
for (int i = 1; i < NUM;i++)
{
totalValue += dist[i];
printf("最小生成树的边：<v%d , v%d>",(i+1),(path[i]+1));
printf(" 权值：%d",dist[i]);
printf("\n");
}
printf("最小生成树的总权值：%d",totalValue);
printf("\n");
return 0;
}
//利用二维数组创建有向图的邻接矩阵，带权值
void CreateMatrix(int mat[NUM][NUM])
{
mat[0][1] = 2;
mat[0][2] = 4;
mat[0][3] = 1;
mat[1][0] = 2;
mat[1][3] = 3;
mat[1][4] = 10;
mat[2][0] = 4;
mat[2][3] = 2;
mat[2][5] = 5;
mat[3][0] = 1;
mat[3][1] = 3;
mat[3][2] = 2;
mat[3][4] = 7;
mat[3][5] = 8;
mat[3][6] = 4;
mat[4][1] = 10;
mat[4][3] = 7;
mat[4][6] = 6;
mat[5][2] = 5;
mat[5][3] = 8;
mat[5][6] = 1;
mat[6][3] = 4;
mat[6][4] = 6;
mat[6][5] = 1;
}
//利用Prim算法求解最小生成树
void DijkstraSearch(int mat[NUM][NUM], int i, int visit[NUM], int dist[NUM], int path[NUM])
{
//初始化
visit[i] = 1;
//dist[i] = 0;
//path[i]=0;
//访问与顶点i相邻接的未被访问的顶点，获取路径长度，如果小于之前路径长度则替换，并记录路径
for (int j = 0; j < NUM;j++)
{
if (visit[j] == 0 && mat[i][j] != INT_MAX)
{
if (mat[i][j]<dist[j])
{
dist[j] = mat[i][j];
path[j] = i;
}
}
}
//在未被访问过的顶点中寻找路径最短的顶点
int minDist = -1;
for (int m = 0;m<NUM;m++)
{
if (visit[m] == 0)
{
minDist = m;
break;
}
}
for (int k = minDist + 1; k<NUM; k++)
{
if (visit[k] == 0 && dist[k]<dist[minDist])
{
minDist = k;
}
}
//如果找到继续寻找到下一个顶点的最短路径（递归）
if (minDist != -1)
{
DijkstraSearch(mat, minDist, visit, dist, path);
}
}
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632