用c写一个图的邻接,遍历,的程序
时间: 2023-06-23 10:08:33 浏览: 35
以下是一个用C语言实现图的邻接表存储和遍历的程序示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义图中最大节点数
#define MAX_VERTEX_NUM 100
// 定义邻接表节点结构体
typedef struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
// 定义顶点信息结构体
typedef struct VertexNode {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VertexNode;
// 定义图结构体
typedef struct Graph {
VertexNode vertex[MAX_VERTEX_NUM]; // 存放顶点信息的数组
int vexnum, arcnum; // 顶点数和边数
} Graph;
// 初始化图
void InitGraph(Graph *G) {
G->vexnum = 0;
G->arcnum = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertex[i].data = 0;
G->vertex[i].firstarc = NULL;
}
}
// 在图中添加一个顶点
void AddVertex(Graph *G, int data) {
G->vertex[G->vexnum].data = data;
G->vertex[G->vexnum].firstarc = NULL;
G->vexnum++;
}
// 在图中添加一条边
void AddEdge(Graph *G, int i, int j) {
ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertex[i].firstarc;
G->vertex[i].firstarc = p;
G->arcnum++;
}
// 深度优先遍历
void DFS(Graph *G, int v, int visited[]) {
printf("%d ", G->vertex[v].data);
visited[v] = 1;
ArcNode *p = G->vertex[v].firstarc;
while (p != NULL) {
if (visited[p->adjvex] == 0) {
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->vertex[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front < rear) {
int w = queue[front++];
ArcNode *p = G->vertex[w].firstarc;
while (p != NULL) {
if (visited[p->adjvex] == 0) {
printf("%d ", G->vertex[p->adjvex].data);
visited[p->adjvex] = 1;
queue[rear++] = p->adjvex;
}
p = p->next;
}
}
}
int main() {
Graph G;
InitGraph(&G);
// 添加顶点
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, 0);
AddEdge(&G, 1, 2);
AddEdge(&G, 1, 3);
AddEdge(&G, 2, 1);
AddEdge(&G, 2, 4);
AddEdge(&G, 3, 0);
AddEdge(&G, 3, 1);
AddEdge(&G, 3, 4);
AddEdge(&G, 4, 2);
AddEdge(&G, 4, 3);
// 深度优先遍历
int visited[MAX_VERTEX_NUM] = {0};
printf("DFS: ");
DFS(&G, 0, visited);
printf("\n");
// 广度优先遍历
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
visited[i] = 0;
}
printf("BFS: ");
BFS(&G, 0, visited);
printf("\n");
return 0;
}
```
该程序实现了以下功能:
1. 定义了邻接表节点结构体 `ArcNode` 和顶点信息结构体 `VertexNode`,以及图结构体 `Graph`。
2. 实现了初始化图函数 `InitGraph`,添加顶点函数 `AddVertex` 和添加边函数 `AddEdge`。
3. 实现了深度优先遍历函数 `DFS` 和广度优先遍历函数 `BFS`。
4. 在 `main` 函数中创建了一个图,添加了顶点和边,并进行了深度优先遍历和广度优先遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)