使用邻接矩阵创建图的算法思想
时间: 2023-12-25 21:04:05 浏览: 38
使用邻接矩阵创建图的算法思想如下:
1. 输入总顶点数和边数,依次输入每个点的信息存入顶点表中。
2. 初始化邻接矩阵,使得每个权值初始化为极大值。
3. 构造邻接矩阵,对于每条边(u, v),将邻接矩阵中第u行第v列和第v行第u列的权值设为该边的权值。
4. 如果是无向图,邻接矩阵是对称的,即第u行第v列和第v行第u列的权值相等。
5. 如果是有向图,邻接矩阵不一定对称,即第u行第v列的权值表示从u到v的边的权值,第v行第u列的权值表示从v到u的边的权值。
相关问题
邻接矩阵创建图的算法思想
邻接矩阵是一种表示图形的方法,其中每个节点都与一个数组或列表相关联,该数组或列表表示与该节点相邻的节点。邻接矩阵可以通过以下算法来创建:
1.输入总顶点数和边数,依次输入每个点的信息并将其存入顶点表中。
2.初始化邻接矩阵,使得每个权值初始化为极大值。
3.构造邻接矩阵,对于每个边,将其权值存储在相应的矩阵元素中。
具体步骤如下:
1.创建一个大小为n*n的矩阵,其中n是顶点的总数。
2.将矩阵中的所有元素初始化为0。
3.对于每个边(u,v),将矩阵中第u行第v列和第v行第u列的元素设置为1,表示这两个节点之间有一条边。
4.如果边有权值,则将矩阵中相应的元素设置为该权值。
5.最终得到的矩阵就是邻接矩阵。
下面是一个Python实现的例子:
```python
n = int(input("请输入总顶点数:"))
m = int(input("请输入总边数:"))
# 初始化邻接矩阵
INF = float('inf')
graph = [[INF] * n for _ in range(n)]
# 构造邻接矩阵
for i in range(m):
u, v, w = map(int, input("请输入第{}条边的起点、终点和权值:".format(i+1)).split())
graph[u][v] = w
graph[v][u] = w
print("邻接矩阵为:")
for i in range(n):
for j in range(n):
if graph[i][j] == INF:
print("INF", end="\t")
else:
print(graph[i][j], end="\t")
print()
```
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为节点数。当节点数比较大时,可能需要使用更高效的算法来求解最小生成树。