「图-深度&广度优先遍历（邻接表）」C语言实现

文章目录
  1. 示意图
  2. 结构定义
  3. 重点
  4. 源码

示意图

待补充。。。

结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/*---------------------------- 图-邻接表结构定义 -----------------------------*/

#define MAXVEX 100        // 最大顶点数

typedef char VertexType;  // 顶点数据类型
typedef int EdgeType;     // 边/弧权值数据类型

// 首先定义边表节点，后续顶点表节点需要用
typedef struct edgeNode {
    int adjvex;         // 存储某顶点的邻接点在顶点表中的下标
    EdgeType weight;    // 存储权值
    struct edgeNode * next;  
} EdgeNode;

// 定义顶点表节点
typedef struct vertexNode {
    VertexType data;
    EdgeNode * firstEdge;
} VertexNode;

// 有了顶点表节点构成的数组，即确定了邻接表
// 类似于有了头指针，即确定了链表一样
typedef VertexNode AdjList[MAXVEX];  // 在这里为顶点表分配了内存，就无需动态分配了

// 最终定义图的邻接表结构
typedef struct {
    AdjList adjList;
    int numVex, numEdge;
} ALGraph;

//上面可以改为：
// typedef struct {
//     VertexNode adjList[MAXVEX];
//     int numVex, numEdge;
// } ALGraph;

/*---------------------------- 图-邻接表结构定义 -----------------------------*/


bool visited[MAXVEX];  // 标记数组

重点

深度优先：类似于树的前序遍历

广度优先：类似于树的层序遍历（借助队列实现）

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
/*
 * 功能: 图-邻接表的深度&广度优先遍历
 * 作者: Guyue
 * 微信公众号: https://img.arctee.cn/one/pokeai-wechat.png
 * 网站：https://pokeai.cn
 * Github: https://github.com/Pokoai/DaHua-Data-Structure/tree/main/A1-LatestVersion
 * Date: 2022-10-01
 */


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#include "linkQueue.h"


/*---------------------------- 图-邻接表结构定义 -----------------------------*/

#define MAXVEX 100        // 最大顶点数

typedef char VertexType;  // 顶点数据类型
typedef int EdgeType;     // 边/弧权值数据类型

// 首先定义边表节点，后续顶点表节点需要用
typedef struct edgeNode {
    int adjvex;         // 存储某顶点的邻接点在顶点表中的下标
    EdgeType weight;    // 存储权值
    struct edgeNode * next;  
} EdgeNode;

// 定义顶点表节点
typedef struct vertexNode {
    VertexType data;
    EdgeNode * firstEdge;
} VertexNode;

// 有了顶点表节点构成的数组，即确定了邻接表
// 类似于有了头指针，即确定了链表一样
typedef VertexNode AdjList[MAXVEX];  // 在这里为顶点表分配了内存，就无需动态分配了

// 最终定义图的邻接表结构
typedef struct {
    AdjList adjList;
    int numVex, numEdge;
} ALGraph;

//上面可以改为：
// typedef struct {
//     VertexNode adjList[MAXVEX];
//     int numVex, numEdge;
// } ALGraph;

/*---------------------------- 图-邻接表结构定义 -----------------------------*/


bool visited[MAXVEX];  // 标记数组


// 函数前置声明
void CreateALGraph(ALGraph *G);
static void DFS(ALGraph *G, int i);
void DFS_Traverse(ALGraph *G);
void BFS_Traverse(ALGraph * G);


// 主函数
int main(void)
{
    ALGraph G;

    CreateALGraph(&G);

    printf("顶点数: %d，边数: %d\n", G.numVex, G.numEdge);

    VertexType v0 = G.adjList[0].data;            // v0顶点
    int idx = G.adjList[0].firstEdge->adjvex;     // v0顶点的邻接点的下标
    EdgeType w1 = G.adjList[0].firstEdge->weight;  // （v0,v1）边权值
    VertexType v1 = G.adjList[idx].data;          // v0的邻接点v1
    printf("边(%c,%c)的权值: %d\n", v0, v1, w1);

    VertexType v2 = G.adjList[2].data;            // v0顶点
    int idx2 = G.adjList[2].firstEdge->adjvex;     // v0顶点的邻接点的下标
    EdgeType w2 = G.adjList[2].firstEdge->weight;  // （v0,v1）边权值
    VertexType v3 = G.adjList[idx].data;          // v0的邻接点v1
    printf("边(%c,%c)的权值: %d\n", v2, v3, w2);

    printf("深度优先遍历：");
    DFS_Traverse(&G);
    printf("广度优先遍历：");
    BFS_Traverse(&G);
    
    return 0;
}


// 创建无向图的邻接表
void CreateALGraph(ALGraph *G)
{
    int i, j, k, w;

    // 读入顶点数和边数
    printf("请输入顶点数和边数（以空格分割）：");
    scanf("%d %d", &G->numVex, &G->numEdge);
    while( getchar() != '\n' );  // 消除回车符及多余字符

    // 读入顶点信息，构建顶点表
    printf("请输入顶点信息（连续输入，勿空格）：");
    for ( i = 0; i < G->numVex; i++ ) {
        scanf("%c", &G->adjList[i].data);  
        G->adjList[i].firstEdge = NULL;  // 将边表置为空
    }
    while( getchar() != '\n' );  // 消除回车符及多余字符

    // 构建边表
    for ( k = 0; k < G->numEdge; k++ ) {
        printf("请输入边(Vi,Vj)的下标i、小标j和权值（以空格分割）：");
        scanf("%d %d %d", &i, &j, &w);
        
        // 为边表节点分配内存空间
        EdgeNode * e = (EdgeNode*)malloc(sizeof(EdgeNode));
        if ( NULL == e) {
            printf("内存分配失败！");
            exit(-1);
        }
        e->weight = w;  // 边表节点的权值域初始化
        e->adjvex = j;  // 记录下边(Vi.Vj)的前节点下标
        e->next = G->adjList[i].firstEdge;  // 头插法，首先将新节点的尾巴指针指向 firstEdge 边节点
        G->adjList[i].firstEdge = e;        // 再将新节点的头练手顶节点 

        // 因为是无向图，调换i、j再操作一遍
        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        if ( NULL == e) {
            printf("内存分配失败！");
            exit(-1);
        }
        e->weight = w;  // 边表节点的权值域初始化
        e->adjvex = i;  // 记录下边(Vi.Vj)的后节点下标
        e->next = G->adjList[j].firstEdge;  
        G->adjList[j].firstEdge = e;        
    }
}

// 邻接表的深度优先递归算法
// 从某个顶点开始，深入挖掘其邻接顶点，完成递归
static void DFS(ALGraph *G, int i)
{
    printf("%c ", G->adjList[i].data);
    visited[i] = true;

    EdgeNode * p = G->adjList[i].firstEdge;  // 第一个邻接顶点  
    while ( p != NULL ) {  // 循环遍历其所有邻接顶点
        if ( !visited[p->adjvex] ) {  
            DFS(G, p->adjvex);
        }
        p = p->next;  // 下一个邻接顶点
    }
}

// 邻接表的深度优先遍历
void DFS_Traverse(ALGraph *G)
{
    // 初始化标记数组
    for ( int i = 0; i < G->numVex; i++ ) {
        visited[i] = false;
    }

    for ( int j = 0; j < G->numVex; j++ ) {  // 适用于非连通图
        if ( !visited[j] ) {
            DFS(G, j);
        }
    }
}

// 邻接表的广度优先遍历
void BFS_Traverse(ALGraph * G)
{
    // 将标记数组初始化
    for ( int i = 0; i < G->numVex; i++ ) {
        visited[i] = false;
    }

    LinkQueue q; 
    int idx;

    InitQueue(&q);
    for ( int j = 0; j < G->numVex; j++ ) {  // 适用于非连通图
        if ( !visited[j] ) {
            EnQueue(&q, j);  // 第一个顶点下标入队
            visited[j] = true;
            while ( QueueIsEmpty(&q) ) {
                DeQueue(&q, &idx);    // 出队
                printf("%c ", G->adjList[idx].data);  // 访问顶点
                
                // 出队的同时将其所有未访问邻接点入队
                EdgeNode *p = G->adjList[idx].firstEdge;
                while ( p != NULL ) {
                    if ( !visited[p->adjvex] ) {  // 勿忘这一句，筛选出尚未访问的顶点
                        EnQueue(&q, p->adjvex);  
                        visited[p->adjvex] = true;
                    }
                    p = p->next;
                }
            }
        }
        
    }
    DestoryQueue(&q);  // 与 InitQueue() 成对出现
}