C语言基于邻接表建立一个图,对图进行深度优先遍历及广度优先遍历。
时间: 2023-06-21 13:21:06 浏览: 88
好的,下面是C语言基于邻接表建立一个图,对图进行深度优先遍历及广度优先遍历的代码实现。
首先我们需要定义一个邻接表的结构体,用来存储图:
```c
#define MAX_VERTEX_NUM 100
// 邻接表节点的结构体
typedef struct ArcNode {
int adjvex; // 邻接节点的编号
struct ArcNode *next; // 指向下一个邻接节点的指针
} ArcNode;
// 顶点节点的结构体
typedef struct {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接节点的指针
} VNode;
// 邻接表的结构体
typedef struct {
VNode vertices[MAX_VERTEX_NUM]; // 顶点数组
int vexnum; // 顶点数
int arcnum; // 边数
} ALGraph;
```
然后我们需要实现一个初始化邻接表的函数:
```c
// 初始化邻接表
void InitGraph(ALGraph *G)
{
int i;
G->vexnum = 0;
G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = 0;
G->vertices[i].firstarc = NULL;
}
}
```
接下来,我们需要实现添加边的函数:
```c
// 添加边
void AddArc(ALGraph *G, int v, int w)
{
ArcNode *p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = w;
p->next = G->vertices[v].firstarc;
G->vertices[v].firstarc = p;
G->arcnum++;
}
```
然后,我们需要实现深度优先遍历的函数:
```c
// 深度优先遍历
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 != NULL) {
if (!visited[p->adjvex]) { // 如果邻居节点未被访问过,则递归访问
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
```
最后,我们需要实现广度优先遍历的函数:
```c
// 广度优先遍历
void BFS(ALGraph *G, int v)
{
int visited[MAX_VERTEX_NUM] = {0}; // 标记数组,记录节点是否被访问过
int q[MAX_VERTEX_NUM]; // 队列
int front = 0, rear = 0; // 队头和队尾指针
int i, j;
ArcNode *p;
q[rear++] = v; // 将起点节点入队
visited[v] = 1; // 标记起点节点为已访问
while (front < rear) {
i = q[front++]; // 取出队首节点
printf("%d ", G->vertices[i].data); // 访问该节点
p = G->vertices[i].firstarc;
while (p != NULL) {
j = p->adjvex;
if (!visited[j]) { // 如果邻居节点未被访问过,则将其入队
q[rear++] = j;
visited[j] = 1;
}
p = p->next;
}
}
}
```
完整的代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100
// 邻接表节点的结构体
typedef struct ArcNode {
int adjvex; // 邻接节点的编号
struct ArcNode *next; // 指向下一个邻接节点的指针
} ArcNode;
// 顶点节点的结构体
typedef struct {
int data; // 顶点的数据
ArcNode *firstarc; // 指向第一个邻接节点的指针
} VNode;
// 邻接表的结构体
typedef struct {
VNode vertices[MAX_VERTEX_NUM]; // 顶点数组
int vexnum; // 顶点数
int 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].data = 0;
G->vertices[i].firstarc = NULL;
}
}
// 添加边
void AddArc(ALGraph *G, int v, int w)
{
ArcNode *p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = w;
p->next = G->vertices[v].firstarc;
G->vertices[v].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 != NULL) {
if (!visited[p->adjvex]) { // 如果邻居节点未被访问过,则递归访问
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 广度优先遍历
void BFS(ALGraph *G, int v)
{
int visited[MAX_VERTEX_NUM] = {0}; // 标记数组,记录节点是否被访问过
int q[MAX_VERTEX_NUM]; // 队列
int front = 0, rear = 0; // 队头和队尾指针
int i, j;
ArcNode *p;
q[rear++] = v; // 将起点节点入队
visited[v] = 1; // 标记起点节点为已访问
while (front < rear) {
i = q[front++]; // 取出队首节点
printf("%d ", G->vertices[i].data); // 访问该节点
p = G->vertices[i].firstarc;
while (p != NULL) {
j = p->adjvex;
if (!visited[j]) { // 如果邻居节点未被访问过,则将其入队
q[rear++] = j;
visited[j] = 1;
}
p = p->next;
}
}
}
int main()
{
ALGraph G;
int n, m, i, v, w;
int visited[MAX_VERTEX_NUM] = {0}; // 标记数组,记录节点是否被访问过
printf("请输入顶点数和边数:\n");
scanf("%d%d", &n, &m);
InitGraph(&G);
G.vexnum = n;
printf("请输入顶点的数据:\n");
for (i = 0; i < n; i++) {
scanf("%d", &G.vertices[i].data);
}
printf("请输入每条边的起点和终点:\n");
for (i = 0; i < m; i++) {
scanf("%d%d", &v, &w);
AddArc(&G, v, w);
}
printf("深度优先遍历结果为:\n");
DFS(&G, 0, visited);
printf("\n");
printf("广度优先遍历结果为:\n");
BFS(&G, 0);
printf("\n");
return 0;
}
```
在这个代码中,我们通过读入顶点数和边数,然后按照邻接表的方式存储图,并对图进行深度优先遍历和广度优先遍历,输出访问的节点序列。
阅读全文