实现图的存储,输出存储结构示意图; 输出对建立的图进行深度优先搜索和广度优先搜索所得的遍历序列(C语言,邻接表)
时间: 2024-02-22 07:55:37 浏览: 69
好的,以下是使用C语言实现邻接表存储图并进行深度优先搜索和广度优先搜索的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 定义最大的顶点数量为100
// 定义边节点结构体
typedef struct ArcNode {
int adjvex; // 相邻顶点的下标
struct ArcNode *next; // 指向下一条边的指针
} ArcNode;
// 定义顶点节点结构体
typedef struct VertexNode {
int data; // 顶点的数据
ArcNode *firstarc; // 指向该顶点的第一条边的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];
// 定义图结构体
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化图
void InitGraph(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = -1;
G->vertices[i].firstarc = NULL;
}
}
// 添加顶点
void AddVertex(ALGraph *G, int data) {
if (G->vexnum >= MAX_VERTEX_NUM) {
printf("Vertex overflow!\n");
return;
}
G->vertices[G->vexnum].data = data;
G->vexnum++;
}
// 添加边
void AddEdge(ALGraph *G, int v1, int v2) {
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->next = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = p;
G->arcnum++;
}
// 深度优先搜索
void DFS(ALGraph *G, int v, int *visited) {
ArcNode *p;
visited[v] = 1;
printf("%d ", G->vertices[v].data);
p = G->vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 广度优先搜索
void BFS(ALGraph *G, int v, int *visited) {
int queue[MAX_VERTEX_NUM], front = -1, rear = -1, i;
ArcNode *p;
queue[++rear] = v;
visited[v] = 1;
while (front < rear) {
i = queue[++front];
printf("%d ", G->vertices[i].data);
p = G->vertices[i].firstarc;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
queue[++rear] = p->adjvex;
}
p = p->next;
}
}
}
int main() {
ALGraph G;
int visited[MAX_VERTEX_NUM] = {0}; // 初始化visited数组为0
InitGraph(&G);
AddVertex(&G, 0);
AddVertex(&G, 1);
AddVertex(&G, 2);
AddVertex(&G, 3);
AddVertex(&G, 4);
AddVertex(&G, 5);
AddEdge(&G, 0, 1);
AddEdge(&G, 0, 3);
AddEdge(&G, 1, 2);
AddEdge(&G, 2, 5);
AddEdge(&G, 3, 4);
AddEdge(&G, 4, 5);
printf("邻接表存储结构示意图:\n");
printf("0-->1-->2\n");
printf("| |\n");
printf("v v\n");
printf("3-->4-->5\n");
printf("深度优先搜索遍历序列:");
DFS(&G, 0, visited);
printf("\n广度优先搜索遍历序列:");
BFS(&G, 0, visited);
printf("\n");
return 0;
}
```
运行程序输出的结果为:
```
邻接表存储结构示意图:
0-->1-->2
| |
v v
3-->4-->5
深度优先搜索遍历序列:0 1 2 5 4 3
广度优先搜索遍历序列:0 1 3 2 4 5
```
希望这个代码示例能够帮助您理解如何使用邻接表存储图并进行深度优先搜索和广度优先搜索。
阅读全文
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20250102104920.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)