编写一段代码,用c语言实现以下描述,有这几个条件,1.实现图的存储,输出存储结构示意图.2.输出对建立的图进行深度优先搜索和广度优先搜索所得的遍历序列。
时间: 2024-02-25 09:53:02 浏览: 125
数据结构-c语言-带main函数-图7.3-图的遍历-深度优先搜索-递归方法-邻接矩阵-有向图。
好的,我可以为你提供一份实现图存储和搜索的代码。这里我采用邻接表的方式来存储图,同时实现深度优先搜索和广度优先搜索。
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
// 邻接表结点
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一个结点的指针
} ArcNode;
// 顶点结构体
typedef struct VNode {
int data; // 顶点数据
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 邻接表结构体
typedef struct {
AdjList vertices; // 存储顶点的数组
int vexnum; // 顶点数
int arcnum; // 边数
} ALGraph;
// 初始化图
void InitGraph(ALGraph *G, int vexnum) {
G->vexnum = vexnum;
G->arcnum = 0;
for (int i = 0; i < G->vexnum; i++) {
G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
}
// 添加边
void AddEdge(ALGraph *G, int v1, int v2) {
ArcNode *node1 = (ArcNode *)malloc(sizeof(ArcNode));
node1->adjvex = v2;
node1->nextarc = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = node1;
ArcNode *node2 = (ArcNode *)malloc(sizeof(ArcNode));
node2->adjvex = v1;
node2->nextarc = G->vertices[v2].firstarc;
G->vertices[v2].firstarc = node2;
G->arcnum++;
}
// 深度优先搜索
void DFS(ALGraph *G, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
ArcNode *p = G->vertices[v].firstarc;
while (p) {
int adjvex = p->adjvex;
if (!visited[adjvex]) {
DFS(G, adjvex, visited);
}
p = p->nextarc;
}
}
// 广度优先搜索
void BFS(ALGraph *G, int v, int visited[]) {
int queue[G->vexnum];
int front = 0, rear = 0;
queue[rear++] = v;
visited[v] = 1;
while (front < rear) {
int u = queue[front++];
printf("%d ", u);
ArcNode *p = G->vertices[u].firstarc;
while (p) {
int adjvex = p->adjvex;
if (!visited[adjvex]) {
visited[adjvex] = 1;
queue[rear++] = adjvex;
}
p = p->nextarc;
}
}
}
int main() {
ALGraph G;
int vexnum = 5;
InitGraph(&G, vexnum);
AddEdge(&G, 0, 1);
AddEdge(&G, 0, 2);
AddEdge(&G, 1, 3);
AddEdge(&G, 2, 3);
AddEdge(&G, 3, 4);
// 输出邻接表结构示意图
printf("邻接表结构示意图:\n");
for (int i = 0; i < G.vexnum; i++) {
printf("%d -> ", i);
ArcNode *p = G.vertices[i].firstarc;
while (p) {
printf("%d -> ", p->adjvex);
p = p->nextarc;
}
printf("NULL\n");
}
// 深度优先搜索
printf("深度优先搜索遍历序列:");
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(&G, i, visited);
}
}
printf("\n");
// 广度优先搜索
printf("广度优先搜索遍历序列:");
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);
}
}
printf("\n");
return 0;
}
```
这份代码实现了初始化图、添加边、深度优先搜索和广度优先搜索等功能,并且输出了邻接表结构示意图和遍历序列。其中,深度优先搜索和广度优先搜索都是采用递归和队列方式实现的。你可以根据需要进行修改和调试,希望对你有所帮助!
阅读全文