在邻接矩阵上实现最短路经、最小生成树的求法
时间: 2023-01-11 07:55:36 浏览: 96
在邻接矩阵上实现最短路径的常用方法是使用 Dijkstra 算法。这是一种贪心算法,它的基本思想是从起点开始,每次找出离起点最近的未标记的顶点,标记并更新从起点到该顶点的距离。这个过程重复执行,直到所有的顶点都被标记为止。
Dijkstra 算法的基本步骤如下:
1. 将所有的顶点的距离设为无穷大,将起点的距离设为 0。
2. 将所有的顶点放入一个优先队列中,按照距离排序。
3. 取出优先队列中距离最小的顶点 u,标记它为已经访问过。
4. 遍历顶点 u 的所有邻接点 v,若 v 未被标记,则将其距离更新为 min(dis[v], dis[u] + w(u,v))。
5. 重复步骤 3 和 4,直到所有的顶点都被标记。
在邻接矩阵上实现最小生成树的常用方法是使用 Prim 算法。这也是一种贪心算法,它的基本思想是从起点开始,每次找出离当前生成树最近的未标记的边,并将该边加入生成树中。这个过程重复执行,直到所有的顶点
相关问题
C语言创建图的邻接矩阵并用普里姆算法求最小生成树
创建图邻接矩阵的步骤如下:
1. 定义一个二维数组来表示图的邻接矩阵,其中第i行第j列的值表示节点i到节点j的边权重。如果两个节点之间没有边,则该位置的值可以设置为无穷大或者一个非常大的值。
2. 初始化邻接矩阵,将所有值都设为无穷大或者一个非常大的值。
3. 遍历所有的边,将相应位置的值设置为边的权重。
下面是一个简单的示例代码:
```c
#include <stdio.h>
#define MAX 100
#define INF 0x7fffffff
int G[MAX][MAX];
int n, m;
void createGraph() {
int i, j, u, v, w;
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
G[i][j] = INF;
}
}
for(i = 1; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u][v] = G[v][u] = w;
}
}
```
接下来,我们使用普里姆算法求最小生成树。普里姆算法是一种贪心算法,它的基本思想是从一个任意节点开始,不断选择与当前生成树相连的最小边,直到所有的节点都被连通为止。具体步骤如下:
1. 选择一个任意节点作为起点,加入生成树中。
2. 遍历与生成树相邻的节点,找到其中权重最小的一条边,将它所连接的节点加入生成树中。
3. 重复步骤2,直到所有的节点都被加入生成树中。
下面是一个简单的示例代码:
```c
void prim() {
int i, j, k, min, sum = 0;
int lowcost[MAX], closest[MAX];
for(i = 2; i <= n; i++) {
lowcost[i] = G[1][i];
closest[i] = 1;
}
closest[1] = 0;
for(i = 2; i <= n; i++) {
min = INF;
k = 0;
for(j = 2; j <= n; j++) {
if(closest[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
closest[k] = 0;
sum += min;
for(j = 2; j <= n; j++) {
if(closest[j] != 0 && G[k][j] < lowcost[j]) {
lowcost[j] = G[k][j];
closest[j] = k;
}
}
}
printf("最小生成树的权值之和为:%d\n", sum);
}
```
在上面的代码中,我们使用两个数组`lowcost`和`closest`来记录生成树中与每个节点相连的最小边和最近的节点。在初始化时,我们将数组`lowcost`和`closest`分别设置为节点1到其他节点的边权重和节点1。接着,我们遍历所有的节点,找到与当前生成树相邻的节点中,权重最小的一条边,并将它所连接的节点加入生成树中。接着,我们更新数组`lowcost`和`closest`中的值,继续遍历下一个节点,直到所有的节点都被加入生成树中。
完整代码如下:
```c
#include <stdio.h>
#define MAX 100
#define INF 0x7fffffff
int G[MAX][MAX];
int n, m;
void createGraph() {
int i, j, u, v, w;
scanf("%d %d", &n, &m);
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
G[i][j] = INF;
}
}
for(i = 1; i <= m; i++) {
scanf("%d %d %d", &u, &v, &w);
G[u][v] = G[v][u] = w;
}
}
void prim() {
int i, j, k, min, sum = 0;
int lowcost[MAX], closest[MAX];
for(i = 2; i <= n; i++) {
lowcost[i] = G[1][i];
closest[i] = 1;
}
closest[1] = 0;
for(i = 2; i <= n; i++) {
min = INF;
k = 0;
for(j = 2; j <= n; j++) {
if(closest[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
closest[k] = 0;
sum += min;
for(j = 2; j <= n; j++) {
if(closest[j] != 0 && G[k][j] < lowcost[j]) {
lowcost[j] = G[k][j];
closest[j] = k;
}
}
}
printf("最小生成树的权值之和为:%d\n", sum);
}
int main() {
createGraph();
prim();
return 0;
}
```
注意,上面的代码中使用了无穷大来表示两个节点之间没有边。在实际使用时,可以根据具体情况选择一个合适的值来表示无穷大。此外,普里姆算法的时间复杂度为O(n^2),其中n为节点数。当节点数比较大时,可能需要使用更高效的算法来求解最小生成树。
建立无向有权图的邻接矩阵并用普里姆算法求最小生成树
首先,我们需要了解无向有权图的邻接矩阵是什么。邻接矩阵是用一个二维数组来表示图的方法,其中数组中的每个元素表示该位置上的两个顶点是否有边相连,如果相连则为边权,否则为无穷大。
假设我们有一个这样的无向有权图,其中有5个节点和7条边:
```
2
1------2
|\ /|
| \ / |
4| \/ |3
| /\ |
| / \ |
|/ \|
4------5
5
```
我们可以用邻接矩阵来表示这个图,其中数组a[i][j]表示从节点i到节点j的边权,如果没有边相连则为无穷大:
```
1 2 3 4 5
1 0 2 inf 4 inf
2 2 0 3 5 1
3 inf 3 0 inf inf
4 4 5 inf 0 1
5 inf 1 inf 1 0
```
接下来,我们可以用普里姆算法来求最小生成树。普里姆算法是一种贪心算法,它从一个任意的节点开始,不断寻找与该节点直接相连的最小权值边所连接的节点,并将其加入生成树中,直到所有节点都加入为止。
我们在这里选择节点1作为起点,然后不断寻找与它相连的最小权值边所连接的节点。具体步骤如下:
1. 将节点1加入生成树中,并将其标记为已访问。
2. 找到与节点1相连的所有边,并选择其中权值最小的边(即与节点2相连的边),将节点2加入生成树中,并将其标记为已访问。
3. 找到与生成树中已有节点相连的所有边,并选择其中权值最小的边(即与节点5相连的边),将节点5加入生成树中,并将其标记为已访问。
4. 找到与生成树中已有节点相连的所有边,并选择其中权值最小的边(即与节点4相连的边),将节点4加入生成树中,并将其标记为已访问。
5. 找到与生成树中已有节点相连的所有边,并选择其中权值最小的边(即与节点2相连的边),但是节点2已经被标记为已访问,因此我们跳过这条边。
6. 找到与生成树中已有节点相连的所有边,并选择其中权值最小的边(即与节点5相连的边),但是节点5已经被标记为已访问,因此我们跳过这条边。
7. 所有节点都已经被加入生成树中,算法结束。
最终得到的最小生成树是:
```
2
1------2
|
4------5
```
其中所有边的权值之和为2+1+1=4。