图的深度遍历和广度遍历c语言 代码
时间: 2023-09-01 21:07:25 浏览: 60
图的深度遍历和广度遍历都可以用C语言来实现。
深度遍历代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef int VertexType; // 顶点数据类型
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
// 顶点表结点
typedef struct VNode {
VertexType data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 图的结构体
typedef struct {
AdjList vertices; // 顶点表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化一个空图
void initGraph(ALGraph *G) {
int i;
G->vexnum = 0;
G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].firstarc = NULL;
}
}
// 添加一个顶点
void addVertex(ALGraph *G, VertexType v) {
G->vertices[G->vexnum].data = v;
G->vexnum++;
}
// 添加一条边(有向图)
void addArc(ALGraph *G, int i, int j) {
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
G->arcnum++;
}
// 深度优先遍历
void DFS(ALGraph *G, int v, int visited[]) {
visited[v] = 1; // 标记为已访问
printf("%d ", G->vertices[v].data); // 输出当前顶点
ArcNode *p = G->vertices[v].firstarc;
while (p) { // 遍历邻接点
if (!visited[p->adjvex]) { // 如果邻接点未被访问,递归遍历
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 图的深度优先遍历
void DFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点为未访问
int i;
for (i = 0; i < G->vexnum; i++) { // 遍历所有顶点
if (!visited[i]) { // 如果顶点未被访问,从该顶点开始遍历
DFS(G, i, visited);
}
}
}
int main() {
ALGraph G;
initGraph(&G);
addVertex(&G, 1);
addVertex(&G, 2);
addVertex(&G, 3);
addVertex(&G, 4);
addVertex(&G, 5);
addArc(&G, 0, 1);
addArc(&G, 0, 2);
addArc(&G, 1, 3);
addArc(&G, 2, 3);
addArc(&G, 3, 4);
printf("DFS: ");
DFSTraverse(&G);
return 0;
}
```
广度遍历代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
#define MAX_QUEUE_SIZE 20 // 队列最大长度
typedef int VertexType; // 顶点数据类型
// 边表结点
typedef struct ArcNode {
int adjvex; // 邻接点下标
struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;
// 顶点表结点
typedef struct VNode {
VertexType data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 图的结构体
typedef struct {
AdjList vertices; // 顶点表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化一个空图
void initGraph(ALGraph *G) {
int i;
G->vexnum = 0;
G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].firstarc = NULL;
}
}
// 添加一个顶点
void addVertex(ALGraph *G, VertexType v) {
G->vertices[G->vexnum].data = v;
G->vexnum++;
}
// 添加一条边(有向图)
void addArc(ALGraph *G, int i, int j) {
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
G->arcnum++;
}
// 初始化一个队列
void initQueue(int *front, int *rear) {
*front = *rear = 0;
}
// 判断队列是否为空
int isQueueEmpty(int front, int rear) {
return front == rear;
}
// 入队
void enqueue(int *queue, int *rear, int data) {
queue[(*rear)++] = data;
}
// 出队
int dequeue(int *queue, int *front) {
return queue[(*front)++];
}
// 广度优先遍历
void BFS(ALGraph *G, int v, int visited[]) {
int queue[MAX_QUEUE_SIZE]; // 定义一个队列
int front, rear; // 队列的前后指针
initQueue(&front, &rear); // 初始化队列
visited[v] = 1; // 标记为已访问
printf("%d ", G->vertices[v].data); // 输出当前顶点
enqueue(queue, &rear, v); // 将当前顶点入队
while (!isQueueEmpty(front, rear)) { // 队列不为空时循环
int w = dequeue(queue, &front); // 出队
ArcNode *p = G->vertices[w].firstarc;
while (p) { // 遍历所有邻接点
int u = p->adjvex;
if (!visited[u]) { // 如果邻接点未被访问,标记为已访问,输出,入队
visited[u] = 1;
printf("%d ", G->vertices[u].data);
enqueue(queue, &rear, u);
}
p = p->next;
}
}
}
// 图的广度优先遍历
void BFSTraverse(ALGraph *G) {
int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点为未访问
int i;
for (i = 0; i < G->vexnum; i++) { // 遍历所有顶点
if (!visited[i]) { // 如果顶点未被访问,从该顶点开始遍历
BFS(G, i, visited);
}
}
}
int main() {
ALGraph G;
initGraph(&G);
addVertex(&G, 1);
addVertex(&G, 2);
addVertex(&G, 3);
addVertex(&G, 4);
addVertex(&G, 5);
addArc(&G, 0, 1);
addArc(&G, 0, 2);
addArc(&G, 1, 3);
addArc(&G, 2, 3);
addArc(&G, 3, 4);
printf("BFS: ");
BFSTraverse(&G);
return 0;
}
```
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.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)