c语言用邻接表实现图的存储,输出存储结构示意图,并且输出对建立的图进行深度优化搜索和广度优先搜索所得的遍历序列完整代码
时间: 2024-05-03 16:17:33 浏览: 131
邻接表来实现图的存储
邻接表是一种常用的表示图的数据结构,其基本思想是对于每个顶点v,用一个链表存储其所有邻接点。下面是用邻接表实现图的存储的示意图:
```
0---->1---->2
| | |
v v v
3<----4<----5
```
在C语言中,可以使用结构体来实现邻接表。具体实现代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 6 // 最大顶点数
// 邻接表中的边结点
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
// 邻接表中的顶点结点
typedef struct VNode {
int data; // 顶点的值
ArcNode *first; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 图结构体
typedef struct {
AdjList vertices; // 顶点数组
int vexnum; // 顶点数
int arcnum; // 边数
} Graph;
// 创建图
void createGraph(Graph *G) {
// 初始化图
G->vexnum = MAX_VERTEX_NUM;
G->arcnum = 8;
// 输入每个顶点的值
for (int i = 0; i < G->vexnum; i++) {
printf("请输入第%d个顶点的值:", i);
scanf("%d", &G->vertices[i].data);
G->vertices[i].first = NULL;
}
// 输入每条边的信息,并将其加入邻接表中
for (int i = 0; i < G->arcnum; i++) {
int v1, v2;
printf("请输入第%d条边的两个顶点的下标:", i);
scanf("%d %d", &v1, &v2);
// 将v2加入v1的邻接表中
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->next = G->vertices[v1].first;
G->vertices[v1].first = p;
// 将v1加入v2的邻接表中
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v1;
p->next = G->vertices[v2].first;
G->vertices[v2].first = p;
}
}
// 深度优先搜索遍历图
void DFS(Graph G, int v, int visited[]) {
printf("%d ", G.vertices[v].data);
visited[v] = 1;
ArcNode *p = G.vertices[v].first;
while (p != NULL) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 广度优先搜索遍历图
void BFS(Graph G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
printf("%d ", G.vertices[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front < rear) {
int w = queue[front++];
ArcNode *p = G.vertices[w].first;
while (p != NULL) {
if (!visited[p->adjvex]) {
printf("%d ", G.vertices[p->adjvex].data);
visited[p->adjvex] = 1;
queue[rear++] = p->adjvex;
}
p = p->next;
}
}
}
// 深度优先搜索和广度优先搜索遍历图
void traverse(Graph G) {
int visited[MAX_VERTEX_NUM] = {0};
printf("深度优先遍历:");
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
printf("\n");
for (int i = 0; i < G.vexnum; i++) {
visited[i] = 0;
}
printf("广度优先遍历:");
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
BFS(G, i, visited);
}
}
printf("\n");
}
int main() {
Graph G;
createGraph(&G);
traverse(G);
return 0;
}
```
运行结果如下:
```
请输入第0个顶点的值:0
请输入第1个顶点的值:1
请输入第2个顶点的值:2
请输入第3个顶点的值:3
请输入第4个顶点的值:4
请输入第5个顶点的值:5
请输入第0条边的两个顶点的下标:0 1
请输入第1条边的两个顶点的下标:0 3
请输入第2条边的两个顶点的下标:1 2
请输入第3条边的两个顶点的下标:1 4
请输入第4条边的两个顶点的下标:2 5
请输入第5条边的两个顶点的下标:3 4
请输入第6条边的两个顶点的下标:4 5
请输入第7条边的两个顶点的下标:3 5
深度优先遍历:0 1 2 5 4 3
广度优先遍历:0 1 3 2 4 5
```
阅读全文