当前正在阅读

数据结构与算法

预计阅读时间: 2 小时

章节目录

数据结构与算法（一）线性结构篇

图结构篇

图结构在我们的生活中实际上是非常常见的，其中最显著的就是我们的地图了，比如我的家乡重庆：

可以看到，地图盘根错节，错综复杂，不同的道路相互连接，我们可以自由地从这些道路通过，从一个地点到达另一个地点。当然除了地图，我们的计算机网络、你的人际关系网等等，这些都可以用图结构来表示。图结构也是整个数据结构中比较难的一部分，而这一章，我们将探讨图结构的性质与应用。

图也是由多个结点连接而成的，但是一个结点可以同时连接多个其他结点，多个结点也可以同时指向一个结点，跟我们之前讲解的树结构不同，它是一种多对多的关系：

它比树形结构更加复杂，没有明确的层次关系，结点与结点之间的连接关系更加自由，图结构是任意两个数据对象之间都有可能存在某种特定关系的数据结构。

基本概念

图（Graph）一般由两个集合共同构成，一个是非空但是有限的顶点集合V（Vertex），另一个是描述顶点之间连接关系的边集合E（Edge，边集合可以为空集，比如只有一个顶点的情况下，没得连啊），一个图实际上正是由这些结点（顶点）和对应的边组成的。因此，图可以表示为： $G = (V, E)$

比如一个图我们可以表示为，集合 $V = \{A,B,C,D\}$ ，集合 $E = \{(A,B),(B,C),(C,D),(D,A),(C,A)\}$ ，图有两种基本形式，一种是上面那样的有向图（有向图表明了方向，从哪个点到哪个点），还有一种是无向图（无向图仅仅是连接，并不指明方向），比如我们上面这样表示就是一个无向图：

每个结点的度就是与其连接的边数，每条边是可以包含权值的，当前也可以不包含。

当然我们也可以将其表示为有向图，集合 $V = \{A,B,C,D\}$ ，集合 $E = \{,,,,\}$ 注意有向图的边使用尖括号<>表示。比如上面这个有向图，那么就长这样：

如果是无向图的一条边(A,B)，那么就称A、B互为邻接点；如果是有向图的一条边<A,B>，那么就称起点A邻接到终点B。有向图的每个结点分为入度和出度，其中入度就是与顶点相连且指向该顶点的边的个数，出度就是从该顶点指向邻接顶点的边的个数。

只要我们的图中不出现自回路边或是重边，那么我们就可以称这个图为简单图，比如上面两张图都是简单图。而下面的则是典型的非简单图了，其中图一出现了自回路，而图二出现了重边：

如果在一个无向图中，任意两个顶点都有一条边相连，则称该图为无向完全图：

同样的，在一个有向图中，如果任意两顶点之间都有由方向互为相反的两条边连接，则称该图为有向完全图：

图通过边将顶点相连，这样我们就可以从一个顶点经过某条路径到达其他顶点了，比如我们现在想要从下面的V5点到达V1点：

那么我们可以有很多种路线，比如经过V2到达，经过V3到达等：

在一个无向图中，如果从一个顶点到另一个顶点有路径，那么就称这两个顶点是连通的。可以看到，要从V5到达V1我们可以有很多种选择，从V5可以到达V1（当然也可以反着来），所以，我们称V5和V1连通的。特别的，如果图中任意两点都是连通的，那么我们就称这个图为连通图。对于有向图，如果图中任意顶点A和B，既有从A到B的路径，也有B到A的路径，则称该有向图是强连通图。

对于图 $G = (V, E)$ 和 $G' = (V', E')$ ，若满足 $V'$ 是 $V$ 的子集，并且 $E'$ 是 $E$ 的子集，则称 $G'$ 是 $G$ 的子图，比如下面的两个图：

其中右边的图就满足上述性质，所以说右边的图是左边图的子图。

无向图的极大连通子图称为连通分量，有向图的极大连通子图称为强连通分量。那么什么是极大连通子图呢？首先连通子图就是原图的子图，并且子图也是连通图，同时应该具有最大的顶点数，即再加入原图中的其他顶点会导致子图不连通，拥有极大顶点数的同时也要包含依附于这点顶点所有的边才行，比如：

可以看到右侧图1、2、3都是左图的子图，但是它们并不都是原图的连通分量，首先我们来看图1，它也是一个连通图，并且包含极大顶点数和所有的边（也就是原图内部的这一块）所以说它是连通分量，我们接着来看图2，它虽然也是连通图，但是并没有包含极大顶点数（最多可以吧D也给加上，但是这里没加）所以说并不是。最后来看图3，它也是连通图，并且包含了极大顶点数和边，所以说是连通分量。

原图为连通图，那么连通分量就是其本身，有且仅有一个。
原图为非连通图，那么连通分量会有多个。

对于极小连通子图，我们会在后面的生成树部分进行讲解。

存储结构

前面我们介绍了图的一些基本概念，我们接着来看如何在程序中对图结构进行表示，这一部分可能会涉及到某些在《线性代数》这门课程中出现的概念。

邻接矩阵

邻接矩阵实际上就是用矩阵去表示图中各顶点之间的邻接关系和权值。假设有一个图 $G = (V, E)$ ，其中有N个顶点，那么我们就可以使用一个N×N的矩阵来表示，比如下面有A、B、C、D四个顶点的图：

此时我们需要使用邻接矩阵来表示它，就像下面这样：

对于一个不带权值的图来说：

G_{ij} = \begin{cases} 1, 无向图的(v_i,v_j)或有向图的是图中的边\\ 0, 无向图的(v_i,v_j)或有向图的不是图中的边 \end{cases}

对于一个带权值的图来说，如果有边，则直接填写对应边的权值，如果没有，那么就填写0或是∞（因为某些图会认为0也是权值，所以说可以用∞，它可以是一个计算机允许的最大值大于所有边的权值的数）来进行表示：

G_{ij} = \begin{cases} w_{ij}, 无向图的(v_i,v_j)或有向图的是图中的边\\ 0或∞, 无向图的(v_i,v_j)或有向图的不是图中的边 \end{cases}

所以说，对于上面的有向图，我们应该像这样填写：

那么我们来看看无向图的邻接矩阵呢？比如下面的这个图：

对于无向图来说，一条边两边是相互连接的，所以说，A连接B，那么B也连接A，所以说就像这样：

![image-20220822222331925](/Users/nagocoler/Library/Application Support/typora-user-images/image-20220822222331925.png)

可以看到得到的矩阵用我们在《线性代数》中的定义来说就是一个对称矩阵（上半和下半都是一样的）因为没有自回路顶点，所以说主对角线上的元素全都是0。由于无向图没有方向之分，顶点之间是相互连接的，所以说无向图的邻接矩阵必定是一个对称矩阵。

我们可以来总结一下性质：

无向图的邻接矩阵一定是一个对称矩阵，因此，有时为了节省时间，我们可以只存放上半部分。
对于无向图，邻接矩阵的第i行非0（或非∞）的个数就是第i个顶点的度。
对于有向图，邻接矩阵的第i行非0（或非∞）的个数就是第i个顶点的出度（纵向就是入度了）

接着我们来看看如何通过代码实现，首先我们需要对结构体进行一下定义，这里我们以有向图为例：

c 复制代码

#define MaxVertex 5

typedef char E;   //顶点存放的数据类型，这个不用我多说了吧

typedef struct MatrixGraph {
    int vertexCount;   //顶点数
    int edgeCount;     //边数
    int matrix[MaxVertex][MaxVertex];   //邻接矩阵
    E data[MaxVertex];    //各个顶点对应的数据
} * Graph;

接着我们可以对其进行一下初始化创建后返回：

c 复制代码

Graph create(){   //创建时，我们可以指定图中初始有多少个结点
    Graph graph = malloc(sizeof(struct MatrixGraph));
    graph->vertexCount = 0;    //顶点和边数肯定一开始是0
    graph->edgeCount = 0;
    for (int i = 0; i < MaxVertex; ++i)    //记得把矩阵每个位置都置为0
        for (int j = 0; j < MaxVertex; ++j)
            graph->matrix[i][j] = 0;
    return graph;
}

int main(){
    Graph graph = create();   //这里咱们就搞一个
    
}

接着我们就可以编写一下添加顶点和添加边的函数了：

c 复制代码

void addVertex(Graph graph, E element){
    if(graph->vertexCount >= MaxVertex) return;
    graph->data[graph->vertexCount++] = element;   //添加新元素
}

void addEdge(Graph graph, int a, int b){   //添加几号顶点到几号顶点的边
    if(graph->matrix[a][b] == 0) {
        graph->matrix[a][b] = 1;  //注意如果是无向图的话，需要[a][b]和[b][a]都置为1
        graph->edgeCount++;
    }
}

我们来尝试构建一下这个有向图：

c 复制代码

Graph graph = create();
for (int c = 'A'; c <= 'D' ; ++c) 
    addVertex(graph, (char) c);
addEdge(graph, 0, 1);   //A -> B
addEdge(graph, 1, 2);   //B -> C
addEdge(graph, 2, 3);   //C -> D
addEdge(graph, 3, 0);   //D -> A
addEdge(graph, 2, 0);   //C -> A

接着我们打印此领接矩阵，看看是否变成了我们预想中的那样：

c 复制代码

void printGraph(Graph graph){
    for (int i = -1; i < graph->vertexCount; ++i) {
        for (int j = -1; j < graph->vertexCount; ++j) {
            if(j == -1)
                printf("%c", 'A' + i);
            else if(i == -1)
                printf("%3c", 'A' + j);
            else
                printf("%3d", graph->matrix[i][j]);
        }
        putchar('\n');
    }
}

最后得到：

可以看到结果跟我们上面推导得出的邻接矩阵一模一样，当然这里仅仅是演示了普通的有向图，我们也可以稍微将代码进行修改，将其变成一个无向图或是带权有向图，这里就不做演示了。

邻接表

前面我们介绍了领接矩阵，我们可以使用邻接矩阵在程序中保存一个图的边相关信息，它采用二维数组的形式，将对应边的连接关系进行存储，但是我们知道，数组存在容量上的局限性（学了这么多节课了，应该能体会到，数组需要一段连续空间，无论是申请还是用起来都很麻烦）同时，我们创建邻接矩阵后，如果图的边数较多（稠密图）利用率还是挺高的，但是一旦遇到边数很少的图（稀疏图）那么表中大量的位置实际上都是0，根本没有被利用起来，是很浪费的。

此时，我们可以考虑使用链式结构来解决这种问题，就像下面这样：

对于图中的每个顶点，建立一个数组，存放一个头结点，我们将与其邻接的顶点，通过一个链表进行记录（看着挺像前面讲的哈希表）这样，也可以表示一个图的连接关系，并且内存空间能够得到更加有效的利用。当然，对于无向图来说，跟之前一样，两边都需要进行保存：

我们来尝试编写一下代码实现，首先还是定义：

c 复制代码

#define MaxVertex 5

typedef char E;

typedef struct Node {   //结点和头结点分开定义，普通结点记录邻接顶点信息
    int nextVertex;
    struct Node * next;
} * Node;

struct HeadNode {   //头结点记录元素
    E element;
    struct Node * next;
};

typedef struct AdjacencyGraph {
    int vertexCount;   //顶点数
    int edgeCount;     //边数
    struct HeadNode vertex[MaxVertex];
} * Graph;

接着是对其进行初始化：

c 复制代码

Graph create(){   //创建时，我们可以指定图中初始有多少个结点
    Graph graph = malloc(sizeof(struct AdjacencyGraph));
    graph->vertexCount = graph->edgeCount = 0;
    return graph;   //头结点数组一开始可以不用管
}

在添加边和顶点时，稍微麻烦一些：

c 复制代码

void addVertex(Graph graph, E element){
    if(graph->vertexCount >= MaxVertex) return;   //跟之前一样
    graph->vertex[graph->vertexCount].element = element;   //添加新结点时，再来修改也行
    graph->vertex[graph->vertexCount].next = NULL;
  	graph->vertexCount++;
}

void addEdge(Graph graph, int a, int b){
    Node node = graph->vertex[a].next;
    Node newNode = malloc(sizeof(struct Node));
    newNode->next = NULL;
    newNode->nextVertex = b;
    if(!node) {    //如果头结点下一个都没有，那么直接连上去
        graph->vertex[a].next = newNode;
    } else {   //否则说明当前顶点已经连接了至少一个其他顶点了，有可能会出现已经连接过的情况，所以说要特别处理一下
        do {
            if(node->nextVertex == b) return;   //如果已经连接了对应的顶点，那么直接返回
            if(node->next) node = node->next;   //否则继续向后遍历
            else break;   //如果没有下一个了，那就找到最后一个结点了，直接结束
        } while (1);
        node->next = newNode;
    }
  	graph->edgeCount++;   //边数计数+1
}

我们来将其构建一下吧，还是以上面的图为例：

c 复制代码

int main(){
    Graph graph = create();
    for (int c = 'A'; c <= 'D' ; ++c)
        addVertex(graph, (char) c);
    addEdge(graph, 0, 1);   //A -> B
    addEdge(graph, 1, 2);   //B -> C
    addEdge(graph, 2, 3);   //C -> D
    addEdge(graph, 3, 0);   //D -> A
    addEdge(graph, 2, 0);   //C -> A

    printGraph(graph);
}

我们来打印看看效果：

c 复制代码

void printGraph(Graph graph){
    for (int i = 0; i < graph->vertexCount; ++i) {
        printf("%d | %c", i, graph->vertex[i].element);
        Node node = graph->vertex[i].next;
        while (node) {
            printf(" -> %d", node->nextVertex);
            node = node->next;
        }
        putchar('\n');
    }
}

得到结果如下：

可以看到结果符合我们的预期。

不过虽然这样的方式看上去更加的简单高效，但是会给我们带来一些不必要的麻烦，比如上面创建的领接表，我们只能快速得到某个顶点指向了哪些顶点，也就是只能计算到顶点的出度，但是无法快速计算顶点的入度，只能将所有结点统计之后才能得到入度。所以说在表示有向图时，查找上并没有邻接矩阵来的方便。

为了解决这种问题，我们可以建立一个逆领接表，来表示所有指向当前顶点的顶点列表：

实际上就是反着来而已，通过建立这两个领接表，就能在一定程度上缓解不方便的情况。

图练习题：

在一个具有n个顶点的有向图中，若所有顶点的出度之和为s，则所有顶点的入度数之和为？

A. s B. s - 1 C. s + 1 D. 2s

有向图的所有出度实际上就是所有顶点连向其他顶点的边数，对于单个顶点来说，要么是自己指向别人（自己的出度，别人的入度），要么别人指向自己（别人的出度，自己的入度），这东西就是个相对的而已，而这些都可以一律看做出度，所以说所有顶点入度数之和就是所有顶点出度之和，所以选A
在一个具有n个顶点的无向完全图中，所含的边数为？

A. n B. n(n-1) C. n(n - 1)/2 D. n(n + 1)/2

首先回顾一下无向完全图的定义：在一个无向图中，任意两个顶点都有一条边相连，则称该图为无向完全图。既然任意两个顶点都有一个，那么每个结点都会有n-1条与其连接的边，所以说总数为 $n \times (n-1)$ 但是由于是无向图，没有方向之分，所以说需要去掉一半的数量，得到 $\frac {n \times (n-1)} {2}$ ，选择C
若要把n个顶点连接为一个连通图，则至少需要几条边？

A. n B. n - 1 C. n + 1 D. 2n

连通图的定义是，每个顶点至少有一条到达其他顶点的路径，所以说我们只需要找一个最简单能够保证每个结点都有与其相连的就行了，也就是连成一根直线（或者是树）的情况，选择B
对于一个具有 n 个顶点和 e 条边的无向图，在其对应的邻接表中，所含边结点有多少个？

A. n B. ne C. e D. 2e

对于无向图，这结点个数等于边数的两倍，对于有向图，刚好等于边数，所以说选择 D

图的遍历

记得小时候每次去书店，都能看到迷宫书：

每次看到都想买一本，但是当时家里条件并不允许消费这么贵的书，所以都只能在书店多看几眼再回去。迷宫的解，实际上就是我们在一个复杂的地图中寻找一条能够从起点到达终点的路径。可以看到从起点开始，每到一个路口，可能都会出现多个分叉，可能有的分叉就会走进死胡同，有的分叉就会走到下一个路口。

那么我们人脑是怎么去寻找到正确的路径呢？

我们首先还是会从起点开始看，我们会尝试去走分叉路的每一个方向，如果遇到死胡同，那么我们就退回到上一个路口，再去尝试其他方向，直到能一直往下走为止。经过不断重复上述的操作，最后我们就肯定能够到达迷宫的出口了。

而图的搜索，实际上也是类似于迷宫这样的形式，我们需要从图的某一个顶点出发，去寻找到图中对应顶点的位置，这一部分，我们将对图的搜索算法进行讨论。

深度优先搜索（DFS）

我们之前在学习二叉树的过程中，讲解了树的前序遍历，各位回想一下，我们当时是如何在进行遍历的？

前序遍历就是勇往直前，直接走到底，然后再回去走其他的分支，而我们的图其实也可以像这样，我们可以一路向前，如果到了死胡同，那么就倒回去再走其他的方向，如果所有方向都走不通，继续再回到上一个路口（实际上就是我们人脑的思维）这样不断的寻找，肯定是可以找到的。

比如现在我们要从A开始寻找下图中的I：

那么我们的路线可以是这样的：

此时顶点B有三个方向，那么我们可以先随便选一个方向（当然，一般情况下为了规范，推荐按照字母排列顺序来走，这里为了演示，就随便走了）看看：

此时来到K，我们发现K已经是一个死胡同，没有其他路了，那么此时我们就需要回到上一个路口，继续去探索其他的路径：

此时我们接着往下一个相邻的顶点G走，发现G有其他的分叉，那么我们就继续向前：

此时走到F发现又是死路，那么退回到G，走其他的方向：

运气太垃了，又到死胡同了，同样的，回到G继续走其他方向：

走到C之后，我们有其他的路，我们继续往后走：

此时走到顶点H，发现H只有一条路，并且H再向前是已经走过的顶点B，那么此时不能再向前了，所以说直接退回到C，走另一边：

此时来到E，又有两条路，那么继续随便选一条走：

此时来到顶点J，发现又是死胡同，退回到E，继续走另一边：

好了，经过了这么多试错，终于是找到了I顶点，这种方式就是深度优先搜索了。

那么我们就来打个代码玩玩吧，这里我们构建一个简单一点的图：

这里我们使用邻接表表示图，因为邻接表直接保存相邻顶点，所以说到达顶点时遍历相邻顶点会更快（能够到达 $O(V + E)$ 线性阶）而如果使用邻接矩阵的话，我们得完整遍历整个二维数组，就比较费时间了（需要 $O(V^2)$ 平方阶）。

比如现在我们想从A开始查找顶点F，首先先把图给建好（注意有6个顶点，记得容量写好）：

c 复制代码

int main(){
    Graph graph = create();
    for (int c = 'A'; c <= 'F' ; ++c)
        addVertex(graph, (char) c);
    addEdge(graph, 0, 1);   //A -> B
    addEdge(graph, 1, 2);   //B -> C
    addEdge(graph, 1, 3);   //B -> D
    addEdge(graph, 1, 4);   //D -> E
    addEdge(graph, 4, 5);   //E -> F

    printGraph(graph);
}

然后就是我们的深度优先搜索算法了：

c 复制代码

/**
 * 深度优先搜索算法
 * @param graph 图
 * @param startVertex 起点顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 已到达过的顶点数组
 */
void dfs(Graph graph, int startVertex, int targetVertex, int * visited){

}

我们先将深度优先遍历写出来：

c 复制代码

/**
 * 深度优先搜索算法（无向图和有向图都适用）
 * @param graph 图
 * @param startVertex 起点顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 已到达过的顶点数组
 */
void dfs(Graph graph, int startVertex, int targetVertex, int * visited) {
    visited[startVertex] = 1;   //走过之后一定记得mark一下
    printf("%c -> ", graph->vertex[startVertex].element);   //打印当前顶点值
    Node node = graph->vertex[startVertex].next;   //遍历当前顶点所有的分支
    while (node) {
        if(!visited[node->nextVertex])   //如果已经到过（有可能是走其他分支到过，或是回头路）那就不继续了
            dfs(graph, node->nextVertex, targetVertex, visited);  //没到过就继续往下走，这里将startVertex设定为对于分支的下一个顶点，按照同样的方式去寻找
        node = node->next;
    }
}

int main(){
    ...

    int arr[graph->vertexCount];
    for (int i = 0; i < graph->vertexCount; ++i) arr[i] = 0;
    dfs(graph, 0, 5, arr);
}

深度优先遍历结果如下：

路线如下：

现在我们将需要查找的顶点进行判断：

c 复制代码

/**
 * 深度优先搜索
 * @param graph 图
 * @param startVertex 起点顶点下标
 * @param targetVertex 目标顶点下标
 * @param visited 已到达过的顶点数组
 * @return 搜索结果，如果找到返回1，没找到返回0
 */
_Bool dfs(Graph graph, int startVertex, int targetVertex, int * visited) {
    visited[startVertex] = 1;
    printf("%c -> ", graph->vertex[startVertex].element);
    if(startVertex == targetVertex) return 1;   //如果当前顶点就是要找的顶点，直接返回
    Node node = graph->vertex[startVertex].next;
    while (node) {
        if(!visited[node->nextVertex])
            if(dfs(graph, node->nextVertex, targetVertex, visited))  //如果查找成功，直接返回1，不用再看其他分支了
                return 1;
        node = node->next;
    }
    return 0;   //while结束那肯定是没找到了，直接返回0
}

int main(){
    ...

    int arr[graph->vertexCount];
    for (int i = 0; i < graph->vertexCount; ++i) arr[i] = 0;
    printf("\n%d", dfs(graph, 0, 5, arr));
}

得到结果如下：

再来找一下顶点D呢：

可以看到到D之后就停止了，因为已经找到了。那么要是去寻找一个没有连接到图中的结点呢？

可以看到整个图按照深度优先遍历找完了都没找到。

前往下一部分继续阅读，当前位于 1 / 2 分段

大纲 (于 2025年1月1日更新)

正在加载页面，请稍后...