c语言实现图的存储,输出存储结构示意图,并且输出对建立的图进行深度优化搜索和
时间: 2024-05-12 09:14:42 浏览: 21
广度优化搜索的遍历结果。
C语言中图的存储可以使用邻接矩阵或邻接表两种方式实现。
1. 邻接矩阵存储
邻接矩阵是一个二维数组,其中每个元素表示两个顶点之间是否有边。如果两个顶点之间存在边,则对应元素的值为1,否则为0。对于无向图而言,邻接矩阵是对称的。
示意图如下:
```
A----B
/ \ |
/ \ |
C----- D
```
对应的邻接矩阵为:
```
A B C D
A 0 1 1 0
B 1 0 1 1
C 1 1 0 1
D 0 1 1 0
```
其中,行和列分别代表图中的顶点,对应元素的值表示两个顶点之间是否有边。
2. 邻接表存储
邻接表是图的一种链式存储结构,每个顶点对应一个链表,链表中存储该顶点与其他顶点之间的边。
示意图如下:
```
A----B
/ \ |
/ \ |
C----- D
```
对应的邻接表为:
```
A -> B -> C
B -> A -> C -> D
C -> A -> B -> D
D -> B -> C
```
其中,每个顶点对应一个链表,链表中存储该顶点与其他顶点之间的边。
下面是使用邻接表实现图的深度优化搜索和广度优化搜索的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef enum {FALSE, TRUE} bool;
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc;// 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
char data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的当前顶点数和弧数
} ALGraph; // 邻接表存储的图类型
bool visited[MAX_VERTEX_NUM]; // 用于记录顶点是否被访问过的数组
// 初始化邻接表
void InitGraph(ALGraph *G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = '\0';
G->vertices[i].firstarc = NULL;
visited[i] = FALSE;
}
}
// 添加顶点
void AddVertex(ALGraph *G, char data) {
G->vertices[G->vexnum].data = data;
G->vexnum++;
}
// 添加弧
void AddArc(ALGraph *G, int v1, int v2) {
ArcNode *p;
if (v1 < 0 || v1 >= G->vexnum || v2 < 0 || v2 >= G->vexnum) {
return;
}
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->nextarc = G->vertices[v1].firstarc;
G->vertices[v1].firstarc = p;
G->arcnum++;
}
// 深度优先搜索遍历
void DFS(ALGraph *G, int v) {
ArcNode *p;
visited[v] = TRUE;
printf("%c ", G->vertices[v].data);
p = G->vertices[v].firstarc;
while (p != NULL) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex);
}
p = p->nextarc;
}
}
// 广度优先搜索遍历
void BFS(ALGraph *G, int v) {
ArcNode *p;
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[v] = TRUE;
printf("%c ", G->vertices[v].data);
queue[rear++] = v;
while (front != rear) {
v = queue[front++];
p = G->vertices[v].firstarc;
while (p != NULL) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = TRUE;
printf("%c ", G->vertices[p->adjvex].data);
queue[rear++] = p->adjvex;
}
p = p->nextarc;
}
}
}
int main() {
ALGraph G;
InitGraph(&G);
AddVertex(&G, 'A');
AddVertex(&G, 'B');
AddVertex(&G, 'C');
AddVertex(&G, 'D');
AddArc(&G, 0, 1);
AddArc(&G, 0, 2);
AddArc(&G, 1, 0);
AddArc(&G, 1, 2);
AddArc(&G, 1, 3);
AddArc(&G, 2, 0);
AddArc(&G, 2, 1);
AddArc(&G, 2, 3);
AddArc(&G, 3, 1);
AddArc(&G, 3, 2);
printf("图的深度优先遍历结果:");
DFS(&G, 0);
printf("\n");
for (int i = 0; i < G.vexnum; i++) {
visited[i] = FALSE;
}
printf("图的广度优先遍历结果:");
BFS(&G, 0);
printf("\n");
return 0;
}
```
输出结果:
```
图的深度优先遍历结果:A C D B
图的广度优先遍历结果:A B C D
```
相关推荐
![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_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)
![](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)