使用邻接矩阵实现图的下列算法 1、使用普里姆算法和克鲁斯卡尔算法生成最小生成树 2、求指定顶点到其他各顶点的最短路径 3编写测试main()函数测试算法正确性
时间: 2023-06-16 22:07:50 浏览: 61
以下是使用邻接矩阵实现图的算法和测试代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
const int MAXN = 100;
const int INF = 0x3f3f3f3f;
int n; // 图中顶点数
int G[MAXN][MAXN]; // 邻接矩阵
// 普里姆算法生成最小生成树
void prim(int s) {
int d[MAXN]; // 存储当前各个顶点到最小生成树的最短距离
bool vis[MAXN] = {false}; // 标记顶点是否已经在最小生成树中
memset(d, INF, sizeof(d)); // 初始化距离为无穷大
d[s] = 0; // 起点到自己的距离为0
for (int i = 0; i < n; i++) {
int u = -1, min_d = INF; // 找到距离最小的顶点
for (int j = 0; j < n; j++) {
if (!vis[j] && d[j] < min_d) {
u = j;
min_d = d[j];
}
}
if (u == -1) return; // 找不到可连接的顶点
vis[u] = true; // 将顶点加入最小生成树
for (int v = 0; v < n; v++) {
if (!vis[v] && G[u][v] < d[v]) {
d[v] = G[u][v]; // 更新最短距离
}
}
}
}
// 克鲁斯卡尔算法生成最小生成树
struct edge {
int u, v, w; // 边的起点、终点和权值
bool operator<(const edge& E) const {
return w < E.w; // 按照权值从小到大排序
}
} edges[MAXN * MAXN]; // 存储所有边
int fa[MAXN]; // 并查集
int find(int x) {
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void kruskal() {
int cnt = 0; // 记录加入最小生成树的边数
for (int i = 0; i < n; i++) fa[i] = i; // 初始化并查集
sort(edges, edges + n * (n - 1) / 2); // 将边按照权值排序
for (int i = 0; i < n * (n - 1) / 2; i++) {
int u = edges[i].u, v = edges[i].v, w = edges[i].w;
int fu = find(u), fv = find(v);
if (fu != fv) { // 如果不在同一个连通块中
fa[fu] = fv; // 合并连通块
cnt++; // 边数+1
if (cnt == n - 1) break; // 边数达到n-1,生成树完成
}
}
}
// Dijkstra算法求单源最短路径
void dijkstra(int s, int d[]) {
bool vis[MAXN] = {false}; // 标记顶点是否已经确定最短路径
memset(d, INF, sizeof(d)); // 初始化距离为无穷大
d[s] = 0; // 起点到自己的距离为0
for (int i = 0; i < n; i++) {
int u = -1, min_d = INF; // 找到距离最小的顶点
for (int j = 0; j < n; j++) {
if (!vis[j] && d[j] < min_d) {
u = j;
min_d = d[j];
}
}
if (u == -1) return; // 找不到可连接的顶点
vis[u] = true; // 将顶点加入最短路径
for (int v = 0; v < n; v++) {
if (!vis[v] && G[u][v] != INF && d[u] + G[u][v] < d[v]) {
d[v] = d[u] + G[u][v]; // 更新最短距离
}
}
}
}
int main() {
cin >> n;
memset(G, INF, sizeof(G)); // 初始化邻接矩阵为无穷大
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int w;
cin >> w;
if (w != -1) G[i][j] = w; // 如果有边,存储边的权值
}
}
// 测试普里姆算法
prim(0);
// 测试克鲁斯卡尔算法
kruskal();
// 测试Dijkstra算法
int s;
cin >> s;
int d[MAXN];
dijkstra(s, d);
// 输出最小生成树和最短路径
cout << "最小生成树:" << endl;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (G[i][j] != INF && find(i) == find(j)) {
cout << i << " " << j << " " << G[i][j] << endl;
}
}
}
cout << "最短路径:" << endl;
for (int i = 0; i < n; i++) {
if (i == s) continue;
cout << s << " " << i << " " << d[i] << endl;
}
return 0;
}
```