图

:::danger 注意 ⚠
仅此文件从上到下复制成一个文件即可使用哦 ~

包括DFS与BFS

BY Lucifer LGX

:::

命令行

前提是windows有MinGW环境

1
2
3
4
5
6
7
8
# C 语言 编译
gcc xxx.c

# C++ 语言 编译
g++ xxx.cpp

# 运行
# 在同一目录下双击.exe文件

结构体定义

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
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTEX_NUM 20                   // 顶点的最大个数
#define VRType int                          // 表示顶点之间的关系的变量类型
#define InfoType char                       // 存储弧或者边额外信息的指针变量类型
#define VertexType int                      // 图中顶点的数据类型

typedef enum{DG, DN, UDG, UDN} GraphKind;   // 枚举图的 4 种类型
typedef enum{FALSE, TRUE} bools;            // 定义bool型常量
bools visited[MAX_VERTEX_NUM];              // 设置全局数组，记录标记顶点是否被访问过

typedef struct Queue{
    VertexType data;
    struct Queue * next;
}Queue;

typedef struct {
    VRType adj;                             // 对于无权图，用 1 或 0 表示是否相邻；对于带权图，直接为权值。
    InfoType * info;                        // 弧或边额外含有的信息指针
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {
    VertexType vexs[MAX_VERTEX_NUM];        // 存储图中顶点数据
    AdjMatrix arcs;                         // 二维数组，记录顶点之间的关系
    int vexnum, arcnum;                     // 记录图的顶点数和弧（边）数
    GraphKind kind;                         // 记录图的种类
}MGraph;

定位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 根据顶点本身数据，判断出顶点在二维数组中的位置
int LocateVex(MGraph * G, VertexType v){
    int i = 0;
    //遍历一维数组，找到变量v
    for (; i < G->vexnum; i++) {
        if (G->vexs[i] == v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回-1
    if (i > G->vexnum) {
        printf("没有这个顶点! \n");
        return -1;
    }
    return i;
}

第一个顶点

1
2
3
4
5
6
7
8
9
int FirstAdjVex(MGraph G,int v){
    // 查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标
    for(int i = 0; i < G.vexnum; i++){
        if( G.arcs[v][i].adj ){
            return i;
        }
    }
    return -1;
}

下一个顶点

1
2
3
4
5
6
7
8
9
int NextAdjVex(MGraph G,int v,int w){
    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点
    for(int i = w + 1; i < G.vexnum; i++){
        if( G.arcs[v][i].adj ){
            return i;
        }
    }
    return -1;
}

输出

1
2
3
void visitVex(MGraph G, int v){
    printf("%d ", G.vexs[v]);
}

DFS

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
void DFS(MGraph G,int v){
    // 标记为true
    visited[v] = TRUE;
    // 访问第v 个顶点
    visitVex(G, v);
    // 从该顶点的第一个边开始，一直到最后一个边，对处于边另一端的顶点调用DFS函数
    for(int w = FirstAdjVex(G,v); w >= 0; w = NextAdjVex(G, v, w)){
        // 如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数
        if(!visited[w]){
            printf("-> ");
            DFS(G, w);
        }
    }
}

// 深度优先搜索
void DFSTraverse(MGraph G){
    int v;
    // 将用做标记的visit数组初始化为false
    for( v = 0; v < G.vexnum; ++v){
        visited[v] = FALSE;
    }
    // 对于每个标记为false的顶点调用深度优先搜索函数
    for( v = 0; v < G.vexnum; v++){
        // 如果该顶点的标记位为false，则调用深度优先搜索函数
        if(!visited[v]){
            DFS(G, v);
        }
    }
}

队列操作

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
// 初始化队列
void InitQueue(Queue ** Q){
    (*Q) = (Queue*) malloc (sizeof(Queue));
    (*Q)->next = NULL;
}

// 顶点元素v进队列
void EnQueue(Queue **Q, VertexType v){
    Queue * element = (Queue*) malloc (sizeof(Queue));
    element->data = v;
    element->next = NULL;
    Queue * temp = (*Q);
    while (temp->next != NULL) {
        temp = temp->next;
    }
    temp->next = element;
}

// 队头元素出队列
void DeQueue(Queue **Q, int *u){
    (*u) = (*Q)->next->data;
    (*Q)->next = (*Q)->next->next;
}

// 判断队列是否为空
bool QueueEmpty(Queue *Q){
    if (Q->next == NULL) {
        return true;
    }
    return false;
}

BFS

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
//广度优先搜索
void BFSTraverse(MGraph G){
    int v;
    // 将用做标记的visit数组初始化为false
    for( v = 0; v < G.vexnum; ++v){
        visited[v] = FALSE;
    }
    // 对于每个标记为false的顶点调用深度优先搜索函数
    Queue * Q;
    InitQueue(&Q);
    for( v = 0; v < G.vexnum; v++){
        if(!visited[v]){
            visited[v] = TRUE;
            visitVex(G, v);
            EnQueue(&Q, G.vexs[v]);
            while (!QueueEmpty(Q)) {
                int u;
                DeQueue(&Q, &u);
                u = LocateVex(&G, u);
                for (int w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w)) {
                    if (!visited[w]) {
                        printf("-> ");
                        visited[w] = TRUE;
                        visitVex(G, w);
                        EnQueue(&Q, G.vexs[w]);
                    }
                }
            }
        }
    }
}

构造有向图

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
void CreateDG(MGraph *G){
    printf("请输入有向图的顶点数和弧数(以','隔开): \n");
    // 输入图含有的顶点数和弧的个数
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    // 依次输入顶点本身的数据
    int num = 1;
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点名称: \n", num);
        scanf("%d", &(G->vexs[i]));
        num++;
    }
    // 初始化二维矩阵，全部归0，指针指向NULL
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j<G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    // 在二维数组中添加弧的数据
    for (int i = 0; i < G->arcnum; i++) {
        int v1,v2;
        // 输入弧头和弧尾
        printf("请输入弧头和弧尾(以','隔开): \n");
        scanf("%d,%d", &v1, &v2);
        // 确定顶点位置
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        // 排除错误数据
        if (m == -1 || n == -1) {
            printf("没有这个顶点! \n");
            return;
        }
        // 将正确的弧的数据加入二维数组
        G->arcs[n][m].adj = 1;
    }
}

构造无向图

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
void CreateDN(MGraph *G){
    printf("请输入无向图的顶点数和弧数(以','隔开): \n");
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    int num = 1;
    for (int i = 0 ; i < G->vexnum; i++) {
        printf("请输入第%d个顶点名称: \n", num);
        scanf("%d", &(G->vexs[i]));
        num++;
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2;
        printf("请输入弧头和弧尾(以','隔开): \n");
        scanf("%d,%d", &v1, &v2);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (m == -1 || n == -1) {
            printf("没有这个顶点!\n");
            return;
        }
        // 无向图的二阶矩阵沿主对角线对称
        G->arcs[n][m].adj = 1;
        G->arcs[m][n].adj = 1;
    }
}

构造有向网

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
void CreateUDG(MGraph *G){
    printf("请输入有向网的顶点数和弧数(以','隔开): \n");
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    int num = 1;
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点名称: \n", num);
        scanf("%d", &(G->vexs[i]));
        num++;
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2, w;
        printf("请输入弧头、弧尾和权值(以','隔开): \n");
        scanf("%d,%d,%d", &v1, &v2, &w);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (m ==-1 || n == -1) {
            printf("没有这个顶点! \n");
            return;
        }
        G->arcs[n][m].adj = w;
    }
}

构造无向网

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
void CreateUDN(MGraph* G){
    printf("请输入无向网的顶点数和弧数: \n");
    scanf("%d,%d", &(G->vexnum), &(G->arcnum));
    int num = 1;
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点名称: \n", num);
        scanf("%d", &(G->vexs[i]));
        num++;
    }
    for (int i = 0; i < G->vexnum; i++) {
        for (int j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = 0;
            G->arcs[i][j].info = NULL;
        }
    }
    for (int i = 0; i < G->arcnum; i++) {
        int v1, v2, w;
        printf("请输入弧头、弧尾和权值(以','隔开): \n");
        scanf("%d,%d,%d", &v1, &v2, &w);
        int m = LocateVex(G, v1);
        int n = LocateVex(G, v2);
        if (m ==-1 || n == -1) {
            printf("没有这个顶点! \n");
            return;
        }
        //矩阵对称
        G->arcs[n][m].adj = w;
        G->arcs[m][n].adj = w;
    }
}

构造图

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
void CreateGraph(MGraph *G){
    // 选择图的类型
    printf("请选择构造图的类型: \n");
    printf("0: 有向图 \n");
    printf("1: 无向图 \n");
    printf("2: 有向网 \n");
    printf("3: 无向网 \n");
    printf("您的选择是: \n");
    scanf("%d", &(G->kind));
    // 根据所选类型，调用不同的函数实现构造图的功能
    switch (G->kind) {
        case DG:
            return CreateDG(G);
            break;
        case DN:
            return CreateDN(G);
            break;
        case UDG:
            return CreateUDG(G);
            break;
        case UDN:
            return CreateUDN(G);
            break;
        default:
            break;
    }
}

遍历

1
2
3
4
5
6
7
8
void PrintGrapth(MGraph G){
    for (int i = 0; i < G.vexnum; i++){
        for (int j = 0; j < G.vexnum; j++){
            printf("%d ", G.arcs[i][j].adj);
        }
        printf("\n");
    }
}

主函数

1
2
3
4
5
6
7
8
9
10
int main() {
    MGraph G;           //建立一个图的变量
    CreateGraph(&G);    //调用创建函数，传入地址参数
    PrintGrapth(G);     //输出图的二阶矩阵
    printf("\n DFS遍历: \n");
    DFSTraverse(G);
    printf("\n BFS遍历: \n");
    BFSTraverse(G);
    return 0;
}