c语言无向图的邻接矩阵
时间: 2023-10-18 09:30:33 浏览: 53
邻接矩阵可以用来表示无向图。对于一个n个结点的无向图,邻接矩阵是一个n*n的矩阵,其中第i行第j列的元素表示结点i和结点j之间是否有边相连,如果有,为1;否则,为0。
下面是一个示例代码,其中使用二维数组来表示邻接矩阵:
```c
#include <stdio.h>
#define MAXN 100
int graph[MAXN][MAXN]; // 邻接矩阵
int n; // 结点数
int main() {
scanf("%d", &n);
// 读入邻接矩阵
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf("%d", &graph[i][j]);
}
}
// 输出邻接矩阵
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
printf("%d ", graph[i][j]);
}
printf("\n");
}
return 0;
}
```
在这个示例中,我们首先读入结点数n,然后读入n*n的邻接矩阵,最后输出邻接矩阵。在实际使用中,我们可以根据邻接矩阵来进行图的遍历、查找等操作。
相关问题
c语言无向图邻接矩阵广度深度遍历概要设计
广度优先搜索(BFS)与深度优先搜索(DFS)是常用的图遍历算法,针对无向图的邻接矩阵进行概要设计如下:
1. 邻接矩阵的表示:
使用二维数组来表示无向图的邻接矩阵。其中,数组的行和列分别代表图的顶点,数组元素的值表示两个顶点之间是否有边连接。
2. 广度优先搜索(BFS)概要设计:
- 创建一个队列,用于存放已经访问过但未处理的顶点。
- 从指定的起点开始,将其加入队列,并标记为已访问。
- 当队列不为空时,循环执行以下步骤:
- 从队列中取出一个顶点,输出其值。
- 遍历该顶点的所有邻接顶点,如果未访问过,则将其加入队列,并标记为已访问。
- 当队列为空时,表示图的遍历完成。
3. 深度优先搜索(DFS)概要设计:
- 创建一个栈,用于存放已经访问过但未处理的顶点。
- 从指定的起点开始,将其加入栈,并标记为已访问。
- 当栈不为空时,循环执行以下步骤:
- 从栈顶取出一个顶点,输出其值。
- 遍历该顶点的所有邻接顶点,如果未访问过,则将其加入栈,并标记为已访问。
- 当栈为空时,表示图的遍历完成。
总结:通过使用邻接矩阵来表示无向图,可以实现广度优先搜索和深度优先搜索的算法。广度优先搜索使用队列进行顶点的遍历,而深度优先搜索使用栈进行顶点的遍历。无论是BFS还是DFS,都需要对顶点进行标记来避免重复访问,以确保图的遍历的正确性。
无向图邻接矩阵的存储C语言,使用邻接矩阵存储无向图
好的,以下是使用邻接矩阵存储无向图的 C 语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 顶点的最大数量
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 顶点数组
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵数组
int vertex_num; // 顶点的数量
int edge_num; // 边的数量
} Graph; // 图的结构体
// 初始化图
void init_graph(Graph *g) {
g->vertex_num = 0;
g->edge_num = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
g->vertex[i] = 0;
for (int j = 0; j < MAX_VERTEX_NUM; j++) {
g->edge[i][j] = 0;
}
}
}
// 添加顶点
void add_vertex(Graph *g, int v) {
g->vertex[g->vertex_num] = v;
g->vertex_num++;
}
// 添加边
void add_edge(Graph *g, int v1, int v2) {
g->edge[v1][v2] = 1;
g->edge[v2][v1] = 1;
g->edge_num++;
}
// 打印图
void print_graph(Graph *g) {
printf("Graph:\n");
printf("Vertex: ");
for (int i = 0; i < g->vertex_num; i++) {
printf("%d ", g->vertex[i]);
}
printf("\n");
printf("Edge:\n");
for (int i = 0; i < g->vertex_num; i++) {
for (int j = 0; j < g->vertex_num; j++) {
printf("%d ", g->edge[i][j]);
}
printf("\n");
}
}
int main() {
Graph g;
init_graph(&g);
// 添加顶点
add_vertex(&g, 1);
add_vertex(&g, 2);
add_vertex(&g, 3);
add_vertex(&g, 4);
// 添加边
add_edge(&g, 0, 1);
add_edge(&g, 1, 2);
add_edge(&g, 2, 3);
add_edge(&g, 3, 0);
// 打印图
print_graph(&g);
return 0;
}
```
以上代码演示了如何使用邻接矩阵存储无向图,包括初始化图、添加顶点、添加边以及打印图等操作。其中,邻接矩阵数组表示顶点之间的边是否存在,如果存在则为 1,否则为 0。
阅读全文