使用邻接矩阵实现最小生成树Prim算法题目编号:1135-Toy模板网

这篇具有很好参考价值的文章主要介绍了使用邻接矩阵实现最小生成树Prim算法题目编号:1135。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

用邻接矩阵存储无向图，实现最小生成树Prim算法，图中边的权值为整型，顶点个数少于10个。

部分代码提示：
#include
using namespace std;

const int MaxSize = 10;
const int INF = 32767;

class MGraph
{
public:
MGraph(char a[], int n, int e);

void Prim();

private:
char vertex[MaxSize];
int arc[MaxSize][MaxSize];
int vertexNum, arcNum;
};

MGraph::MGraph(char a[], int n, int e)
{
//write your code.

}

int MinEdge(int lowcost[], int vertexNum)
{
//write your code.

}
void MGraph::Prim()
{
//write your code.

}

int main()
{
int n = 0;
int e = 0;
cin >> n >> e;
char p[MaxSize];
int i = 0;

for (i=0; i<n; i++)
{
	cin >> p[i];
}

MGraph MG(p, n, e);

MG.Prim();

return 0;

}

输入描述

首先输入图中顶点个数和边的条数；
再输入顶点的信息（字符型）；
再输入各边及其权值。

输出描述

输出从编号为0的顶点开始的Prim算法最小生成树中的各边及其权值，每条边及其权值占一行。

输入样例

5 7
A B C D E
0 1 6
0 2 2
0 3 1
1 2 4
1 3 3
2 4 6
3 4 7

输出样例

A D 1
A C 2
D B 3
C E 6
内存阀值:50240K 耗时阀值:5000MS文章来源地址https://www.toymoban.com/news/detail-460122.html

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
 
const int N = 510, INF = 0x3f3f3f3f;
char v[N];
int n, m, idx;
int g[N][N],dist[N],st[N];
int pre[N];
 
void prim()
{
    memset(dist, 0x3f, sizeof dist);
    dist[0] = 0;
	
    for(int i = 0; i < n; i++)
    {
        int t = -1;
        for(int j = 0; j < n; j++)
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        st[t] = 1;
        if(i){
        	cout << v[pre[t]] << ' ' << v[t] << ' ' << g[t][pre[t]];
		}
        for(int j = 0; j < n; j++){
        	if(!st[j] && g[t][j]<dist[j]){
        		dist[j] = g[t][j];
        		pre[j] = t;
			}
		}	
    }
}
 
int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> v[i]; 
    
	memset(g, 0x3f, sizeof g);
    int a, b, c;
    while (m -- ){
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = c;
    }
    
    prim();
    
    return 0;
}