c语言实现 建立图的邻接表存储并在此基础上实现图的深度优先遍历和广度优先遍历。
时间: 2023-11-20 16:09:39 浏览: 137
以下是C语言实现建立图的邻接表存储,并在此基础上实现图的深度优先遍历和广度优先遍历的示例代码。
```c
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
// 边表节点
typedef struct EdgeNode{
int adjvex; // 邻接点序号
struct EdgeNode *next; // 指向下一个邻接点的指针
}EdgeNode;
// 顶点表节点
typedef struct VertexNode{
char data; // 顶点信息
EdgeNode *firstedge; // 指向第一个邻接点的指针
}VertexNode;
// 图
typedef struct{
VertexNode vertex[MAX_VERTEX_NUM]; // 顶点表
int vexnum; // 顶点数
int edgenum; // 边数
}Graph;
// 建立图的邻接表存储
void CreateGraph(Graph *G){
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->edgenum);
getchar(); // 吸收换行符
// 输入顶点数据
printf("请输入顶点的信息:");
for(int i = 0; i < G->vexnum; i++){
scanf("%c", &G->vertex[i].data);
G->vertex[i].firstedge = NULL;
getchar(); // 吸收换行符
}
// 输入边的信息
printf("请输入每条边的两个顶点的序号:");
for(int i = 0; i < G->edgenum; i++){
int v1, v2;
scanf("%d%d", &v1, &v2);
EdgeNode *e1 = (EdgeNode*)malloc(sizeof(EdgeNode));
e1->adjvex = v2;
e1->next = G->vertex[v1].firstedge;
G->vertex[v1].firstedge = e1;
EdgeNode *e2 = (EdgeNode*)malloc(sizeof(EdgeNode));
e2->adjvex = v1;
e2->next = G->vertex[v2].firstedge;
G->vertex[v2].firstedge = e2;
}
}
// 深度优先遍历
void DFS(Graph G, int v, int visited[]){
visited[v] = 1;
printf("%c ", G.vertex[v].data);
EdgeNode *p = G.vertex[v].firstedge;
while(p != NULL){
int w = p->adjvex;
if(!visited[w]){
DFS(G, w, visited);
}
p = p->next;
}
}
// 广度优先遍历
void BFS(Graph G, int v, int visited[]){
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
visited[v] = 1;
printf("%c ", G.vertex[v].data);
queue[rear++] = v;
while(front < rear){
int w = queue[front++]; // 出队
EdgeNode *p = G.vertex[w].firstedge;
while(p != NULL){
int u = p->adjvex;
if(!visited[u]){
visited[u] = 1;
printf("%c ", G.vertex[u].data);
queue[rear++] = u; // 入队
}
p = p->next;
}
}
}
int main(){
Graph G;
CreateGraph(&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; // 重置访问标记数组
}
for(int i = 0; i < G.vexnum; i++){
if(!visited[i]){
BFS(G, i, visited);
}
}
return 0;
}
```
在上述代码中,我们创建了三个数据结构:边表节点、顶点表节点和图。其中,边表节点包含了邻接点的序号和指向下一个邻接点的指针;顶点表节点包含了顶点的信息和指向第一个邻接点的指针;图则由顶点表构成,包含了顶点数和边数。
在建立图的邻接表存储后,我们实现了图的深度优先遍历和广度优先遍历。具体而言,深度优先遍历使用递归实现,广度优先遍历使用队列实现。在遍历过程中,使用访问标记数组来避免重复访问。
以上就是C语言实现建立图的邻接表存储并实现深度优先遍历和广度优先遍历的示例代码。
阅读全文