数据结构08-图

数据结构与算法 2022年9月15日

图存储结构

图结构简介

在之前的章节中已经见过了一对一和一对多的数据结构，它们分别可以使用线性表和树来描述。本节介绍一种典型的多对多数据结构：图(graph)。

下面展示了一个简单的图结构，可以看出每两个数据之间都可能有对应关系：

这种对应关系使得图不能简单地使用节点和指针表示，否则一个节点需要大量空间来表示这种对多的关系。在介绍图的表示方法之前，可以了解一下图的定义。

图的若干定义

一个图 \\( G=(V,E) \\) 由顶点(vertex)集合 \\( V \\) 和边(edge)集合 \\( E \\) 组成。顶点类似于树节点的概念，边是一对顶点的关联 \\( (v, w) \\) 其中 \\( v, w \in V \\) ，边有时也称为弧(arc)。

有时候顶点之间并不是双向联系，而是像树一样的单方面指向，这种图称为有向图(digraph)。有向图的顶点对是有序的。下面展示了一个有向图，每两个数据之间的对应关系可能是指向也可能是被指向：

有向图中顶点的入度(indegree)指的是箭头指向它的数量，而出度(outdegree)指的是它指出的箭头数量。

两个顶点 \\( v \\) 和 \\( w \\) 邻接(adjacent)指的是边 \\( (v, w) \in E \\) ，即两个顶点之间有直接连接（且符合指向顺序）的边。

一个边有时也具有值(cost)或称为权(weight)。例如在一个地图中，两个地点（顶点）之间路线（边）的权可以反映它们的距离。

图的一条路径(path)从一个顶点到另一顶点途经的所有顶点组成的序列，用数学描述就是是一个顶点序列 \\( w_1, w_2, \dots, w_N \\) 使得 \\( (w_i, w_{i+1}) \in E \\) 。从一个顶点到自身可以看作一条路径，这种路径不包含边，路径长为 0 。

如果一个顶点到其自身存在一条边 \\( (v, v) \\) ，那么路径 \\( v,v \\) 称为环(loop)，一般来说很少有图的应用需要有这种直接与自身有关联的顶点。

与环相似的概念是圈(cycle)，如果路径中第一个顶点和最后一个顶点相同，且路径的长度至少为 1（至少涉及两个顶点），则这样的路径就是圈。对于无向图还要求边之间互不相同，防止在两个顶点间左右横跳被认为是圈。

如果在一个无向图中从每一个顶点到其它顶点中都存在一条路径，则称该无向图是连通(connected)的。具有这样性质的有向图称为强连通(strongly connected)的；如果它不具备这样的性质，但它的边去掉方向所退化为的无向图是连通的，那么该有向图是弱连通(weakly connected)的。一个比较典型的实例是航空系统，如果航空网络构成的图是强连通的，那么说明从任意一个航站到另一个航站都只需要若干次换乘；否则还需要借助其它交通方式才能到达。

图的实现

下面以有向图为例说明图的实现。无向图可以看作每一条边都是双向连接的有向图。

表示图的一种最简单的方式是使用二维数据，一个维度存储这些顶点，另一个维度存储顶点之间的对应关系：如果存在边 \\( (u, v) \\) ，那么就置 \\( A[u][v] \\) 为 1 或它的权；否则将其清零或使用 \\( \infty \\) 等表示。

这种二维数组称为邻接矩阵(adjacency matrix)，使用邻接矩阵表示图易于理解，且对无向图来说由于指向具有对称性，存储时可以采用上三角或下三角矩阵进一步压缩空间。

然而邻接矩阵的空间要求还是太多了，它的空间复杂度为 \\( O(|V|^2) \\) ，除非图中顶点间的关联基本都存在，否则邻接矩阵的大多数位置都不会被用到。

如果要提高空间利用率，那么就需要只存储存在的数据而不存储不存在的数据。那么就可以使用链表这种长度可以灵活调整的数据结构：对于每一个顶点，使用一个链表存放所有邻接的顶点，这样空间需求只为 \\( O(|V|+|E|) \\) 。这种图的表现形式称为邻接表(adjacency list)。

以下展示了图的邻接表表示方法，左侧是图的直观结构：

可以看到这种结构类似于分离链接散列表。邻接表是表示图的基本方法，接下来的操作都以邻接表为例。邻接表的定义可以参考如下：

typedef struct graph_arc graph_arc;
typedef struct graph_vertex {
    elemtype data;
    graph_arc* firstarc;
} graph_vertex;
struct graph_arc {
    graph_vertex* vertex;
    struct graph_arc* nextarc;
    int weight;
};
typedef struct graph {
    graph_vertex** vertices;
    int vertex_num;
    int arc_num;
    int size;
} * graph;

接下来介绍几个关于图的典型问题。

拓扑排序

拓扑排序是一种针对有向图顶点的一种排序，由于有向图有指向关系，因此可以通过该指向关系来为顶点安排先后顺序。

一种典型的拓扑排序应用就是选课流程：为了确保知识的连贯性，有些课程必须学完之后才可以继续学习下一门课程，那么这些课程之间就可以按学习顺序构成一个有向图，使用拓扑排序可以确定如何安排课程。

因此，被排序的图除了是有向的外，还要求它没有圈，不然圈上的元素没有严格的先后关系。

例如，以下图：

顶点的指向顺序从左向右。特别地，顶点 C 和 D 之间是并列的，没有严格的先后关系，两者任意一个排在前面都可以。因此，以上图的拓扑排序可以有两种结果：

A→B→C→D→E
A→B→D→C→E

拓扑排序的思路也很简单：如果一个顶点可以排在最前面，那么应该没有顶点指向它，即它的入度为 0 ；那么只需要找出入度为 0 的顶点，然后将它和它指出的边暂时排除，继续寻找下一个符合条件（入度为 0 ）的顶点即可。以下展示了这一步骤：

以上算法可以做一个小的优化：每一次查找入度为 0 的顶点都花费 \\( O(|V|) \\) 的时间，但只取出一个顶点做处理，如果下一次还是遍历图去寻找入度为 0 的顶点，会使得算法的运行时间达到了平方级 \\( O(|V|^2) \\) 。在第一次扫描时，可以将入度为 0 的顶点放入一个表中，然后逐个取出表中的顶点，检查它指向的顶点入度减 1 后是否为 0 ：只要一个顶点的入度降为 0 ，说明去除那些指向它的顶点后它就可以作为下一位置的顶点，可以同样地将它放入表中继续处理。

这样就只需一次扫描顶点和边并建立表，使执行时间可以变为 \\( O(|V|+|E|) \\) 。这种表可以使用栈或队列。这里使用队列以实现顺序处理。

拓扑排序的代码实现为：

void TopSort(graph g) {
    int indegree[VERTEX_MAXNUM];
    memset(&indegree, 0, sizeof indegree);
    Graph_GatherInDegree(g, indegree);

    queue q = Queue_New(VERTEX_MAXNUM);
    for (int i = 0; i < g->size; i++)
        if (indegree[i] == 0)
            Queue_Enqueue(q, g->vertices[i]->data);

    int counter = 0;
    while (!Queue_IsEmpty(q)) {
        graph_vertex* v = Graph_GetVertexByData(g, Queue_Dequeue(q));
        printf("%d >", v->data);  // print in topological order
        counter++;
        for (graph_arc* arc = v->firstarc; arc; arc = arc->nextarc) {
            graph_vertex* w = arc->vertex;
            if (--indegree[Graph_GetVertexIndex(g, w)] == 0)
                Queue_Enqueue(q, w->data);
        }
    }
    if (counter != g->vertex_num)
        warning("Graph has a cycle");

    Queue_Delete(q);
}

由于图的实现比较复杂，本节涉及到的代码一般会将一些细节抽象为函数，使用类似伪代码的形式展现。如果要获取包括拓扑排序在内的完整图论算法实现，以及图的创建等其它操作实现，可以访问 GitHub 仓库。

这个程序比较复杂，它可以分为几个部分理解。在计算入度时，由于邻接表只记录一个顶点指出的边，因此要计算入度时需要遍历所有的顶点才能完整得出指向一个顶点的所有边。这里使用一个数组 indegree[] 在一次遍历时便统计出所有顶点的边，加快运行的同时方便处理。

由于图中可能存在圈，但无法通过简单的方式来判断。不过如果存在圈，圈上的顶点就不会降到 0 ，使得它们不会被排序。那么最后只需要判断排序的顶点数是否等于图中包含的顶点数，就知道图中是否存在圈了。

图的遍历

遍历也是图常用的一种操作。遍历的要求是从图中的某一个顶点开始，访问每个路径上能到达的顶点且每个顶点应该只访问一次。遍历可以用于规划路线、安排流量、计算其它数学量等。

深度优先搜索

深度优先搜索(depth-first search, DFS)的原理是从某个顶点搜索时，当搜索到下一个顶点时，再递归地从下一个顶点继续搜索下一个顶点。

下图展示了深度优先搜索某一时刻顶点的搜索情况，可以看出远处的顶点可能会被先搜索到：

深度优先搜索可以使用递归的形式来求解。另外为了让每个顶点只遍历一次，还需要有一个额外的顶点字段或数组记录顶点是否被访问过。

以下代码是深度优先搜索的一个通用形式：

void Graph_DepthFirstSearch(graph g, graph_vertex* v) {
    visited[v->data] = true;
    for (graph_arc* arc = v->firstarc; arc; arc = arc->nextarc) {
        graph_vertex* w = arc->vertex;
        if (!visited[w->data])
            Graph_DepthFirstSearch(g, w);
    }
}

值的注意的是，如果图是无向不连通或有向弱连通的，未必所有顶点都会在此过程中访问到。

广度优先搜索

深度优先搜索的缺点是有时要搜索的顶点可能离它较近，但程序可能会花费很多不必要的时间处理更远的顶点。这在图很大时不利于处理较近的顶点。广度优先搜索(breadth-first search)则优先处理较近的顶点，然后再处理更远的顶点。

广度优先搜索的原理为：从某一顶点开始搜索时，遍历每一个顶点时，依次遍历其所有的邻接点，然后再从这些邻接点出发，同样依次访问它们的邻接点。按照此过程，直到图中所有被访问过的顶点的邻接点都被访问到。

下图展示了广度优先搜索某一时刻顶点的搜索情况，搜索的顶点从起点开始向外辐射展开：

广度优先搜索需要在访问一批顶点时保存这些顶点的信息，这样下一次才能向外拓展一层。保存已访问但还没向外拓展的顶点可以使用队列来实现，并且使用队列可以让先向外拓展的顶点下一次也先向外拓展。

以下代码是广度优先搜索的一个通用形式：

void Graph_BreadthFirstSearch(graph g, graph_vertex* v) {
    bool visited[g->size];
    memset(visited, 0, sizeof visited);
    queue q = Queue_New(VERTEX_MAXNUM);
    if (!visited[v->data]) {
        visited[v->data] = true;
        Queue_Enqueue(q, v->data);
        while (!Queue_IsEmpty(q)) {
            graph_vertex* w = Graph_GetVertexByData(g, Queue_Dequeue(q));
            for (graph_arc* arc = w->firstarc; arc; arc = arc->nextarc)
                if (!visited[arc->vertex->data]) {
                    visited[arc->vertex->data] = true;
                    Queue_Enqueue(q, arc->vertex->data);
                }
        }
    }
    Queue_Delete(q);
}

图的两种遍历方式各有侧重点，它们都有比较典型的应用。

最短路径算法

图的顶点之间会互相联系，形成一种网状结构。这个时候查找两个顶点之间的最短路径就是一个常见的问题。例如，导航和游戏在寻路时都需要在地图上的两点内规划一条最短的路线。

无权图的最短路径

无权图在寻找最短路径时只需要考虑边的条数，而不需要考虑边的权重，因此这种情况实现起来比较简单：在计算顶点 \\( v_1 \\) 到 \\( v_2 \\) 的最短路径时，只需要使路径上具有最少的边即可。

无权图的最短路径可以使用广度优先搜索的思想解决：广度优先搜索每向外拓展一层，那么路径长便增加 1 ，并且第一次遇到一个顶点时的路径是离起点最短的路径。

可以通过一个附加的顶点字段或数组记录每个顶点离起点的最短路径，并且它可以代替之前使用的 visited[] 数组：在起始时置所有顶点的路径为 -1（无限远），每搜索到一个顶点，只要它是无限远，那就说明没有访问过，将其路径长置为上一级顶点的路径长多 1 。

无权图计算最短路径的实现方式和广度优先算法比较相似。接下来介绍有权图最短路径的算法实现。

有权图的最短路径

如果在计算最短路径时要考虑到边上的权，那么计算最短路径就会复杂许多，不过基本的处理思路依然可以参考无权图。

Dijkstra 算法是一个解决有权最短路径问题的较好的算法。该算法和无权最短路径问题一样分阶段执行：每个阶段该算法选择在未访问顶点中路径长 \\( d_v \\) 最小的顶点 \\( v \\) ，并通过该顶点更新邻接顶点的长度：如果从 \\( v \\) 到邻接顶点 \\( w \\) 的路径比从其它顶点到 \\( w \\) 的路径更短，那么就更新 \\( w \\) 最短路径。

例如，假设要在以下有向有权图中寻找从 \\( v_1 \\) 到 \\( v_8 \\) 的最短路径：

那么首先从 \\( v_1 \\) 开始，标记出从它到邻接顶点的路径，并暂时视为最短路径：

然后找到未访问且具有最短路径的顶点，即顶点 \\( v_2 \\) ，再标记出经由它到邻接顶点的路径：

每次更新完邻接顶点的路径后，都继续从未访问的顶点中找出具有最短路径的顶点。

本次找到的顶点为 \\( v_6 \\) ，计算它邻接顶点的路径长时，发现从它到 \\( v_3 \\) 比从已到达的顶点到 \\( v_3 \\) 路径更短，那么就更新到 \\( v_3 \\) 的最短路径：

重复以上步骤，直到确定了 \\( v_1 \\) 与图中所有顶点的最短路径后才结束算法。

例如，接下来两步是处理 \\( v_3 \\) 和 \\( v_4 \\) 顶点并更新它们邻接顶点的路径长：

Dijkstra 算法也可用于处理无向图的最短路径，甚至可以用于处理无权图的最短路径（无权图可以将每条边的权看作 1 ）。

Dijkstra 算法的代码大致实现如下：

int Graph_WeightedPath_Dijkstra(graph g, graph_vertex* v, graph_vertex* w) {
    bool visited[VERTEX_MAXNUM];
    int minpathlen[VERTEX_MAXNUM];
    memset(visited, 0, sizeof visited);
    for (int i = 0; i < VERTEX_MAXNUM; i++) minpathlen[i] = INT_MAX;
   
    minpathlen[v->data] = 0;
    for (int i = 0; i < g->size; i++) {
        if (!g->vertices[i]) continue;
        int minv = 0;
        int minlen = INT_MAX;

        for (int j = 0; j < g->size; j++)
            if (!visited[j] && minpathlen[j] < minlen) {
                minv = j;
                minlen = minpathlen[minv];
            }
        visited[minv] = true;
        graph_vertex* v_k = Graph_GetVertexByData(g, minv);
        for (graph_arc* arc = v_k->firstarc; arc; arc = arc->nextarc) {
            graph_vertex* u = arc->vertex;
            if (!visited[u->data] && (minlen + arc->weight < minpathlen[u->data]))
                minpathlen[u->data] = minlen + arc->weight;
        }
    }
    return minpathlen[w->data];
}

注意一个已计算路径最小值的顶点未必被访问过。

Dijkstra 算法需要花费线性的时间处理完所有顶点；每处理一个顶点，接下来还需要花费线性时间查找未访问顶点的路径最小值，而所有顶点的最小路径长需要遍历所有边才能得出一个确定的结果，因此该算法的时间复杂度为 \\( O(|V|^2+|E|) = O(|V|^2 \\) 。

如果图较为稠密（每两个顶点间基本都有边，\\( |E| \approx |V|^2 \\) ），那么该算法的效率基本已经是最优的了。

否则当边较为稀疏时，以上算法还有优化的空间。优化主要体现在线性时间的最小值查找上，可以借助优先队列（堆）降低查找的时间。由于优先队列的删除最小值需要 \\( O(\log N) \\) 时间，因此使用优先队列的 Dijkstra 算法花费的总时间为 \\( O(|E|\log |V| + |V|\log |V|) = O(|E| log |V|) \\) ，在边数较少时可以加快运行效率。

使用堆存储路径长的缺点是二叉堆不支持查找，难以修改一个顶点的最小路径长。要改进这个问题只能使用更高级的优先队列结构，这里暂不讨论这个问题。

除此之外，Dijkstra 算法在某些情况下也可能失效。例如当边的权为负值的时候，那么一个已访问的顶点并不一定已经计算出最短路径，因为可能从未访问顶点有一条负值很大的路径指向它使得从更远的顶点到这里反而可能变得更短，问题是该顶点已经用于计算邻接顶点的最短路径，不能只更新该顶点的最短路径长。一个最坏的情况下，图中可能有含有负值边的圈，并且这个负值可能很大使得每走完一圈路径反而会变短。如果不处理这种情况很容易会造成无限循环。

无权最短路径和有权最短路径的算法都可以得出最短路径：可以增加一个辅助顶点字段或数组，记录到达该顶点的最短路径的上一个顶点的信息，最后收集这些信息，就可以从目的顶点逆序到达起始顶点。

最小生成树

最小生成树(minimum spanning tree)是一个主要针对无向图的问题。一个无向图的最小生成树就是由图中所有顶点和部分边构成的另一个图，且边的权重之和最小。

例如，以上是上一节示例退化的无向图及其最小生成树：

最小生成树也有典型的实际应用。例如，假设要在若干地点间建立通信路线，那么需要通过最小生成树来规划建立需要的最短线路长度或最少花费。

最小生成树之所以称为“树”，是因为这样得到的无向图是没有圈的，因此它将退化为树形结构。如果无向图有圈，那么圈上的两个顶点之间就会有两条不一样的路径，但这是不必要的，会增加总的路径长度，只需要保留更短的路径即可。

并且由于无向图是没有圈的，无向图边的条数为 \\( |V| - 1 \\) ，因为除了根之外，每个顶点都需要一条边来接到图中；如果多了一条边，那么某个顶点就会接到图中两次，形成一个不必要的圈。

具有最小生成树的图需要是连通的。计算图的最小生成树有两种常用的算法。

Prim算法

Prim 是一种易于理解的最小生成树算法。该算法先将每个顶点独立出来，然后每次从独立的顶点中选择离生成树最近的顶点，将它和它的边插入生成树中。

一开始可以随机选择一个顶点作为生成树的根。下图展示了该算法计算以上图最小生成树的前几步：

Prim 算法原理比较直观，但有一些细节需要谨慎处理。Prim 算法的实现可以参照以下思路完成：

该思路要求每个顶点有两个字段：分别记录还不在生成树的顶点离生成树的最近路径长与离生成树最近的顶点。

首先，任取一个顶点放入生成树中，并将其邻接的顶点视为离生成树最近的顶点，更新这些顶点的最近路径长与最近顶点：

每个顶点的最近路径长一开始被置为 \\( \infty \\) 或 INT_MAX 。如果一个顶点的最近路径长为 0 ，那么说明该顶点已经位于生成树中。

接下来每次都选取离生成树最近的顶点，将其插入到生成树中，并更新该顶点邻接的顶点信息。例如，下一次离生成树最近的顶点是 \\( v_2 \\) ，则将其插入生成树中。更新 \\( v_2 \\) 邻接顶点时发现 \\( v_3 \\) 离它比离 \\( v_1 \\) 更近，因此将该顶点的相关字段更新：

下一步继续选择离生成树最近的顶点，依照上述方式插入到生成树中并更新邻接顶点的信息：

Prim 算法的简单代码实现可以参考如下，它与 Dijkstra 算法的实现上非常相似：

void Graph_MinSpanTree_Prim(graph g) {
    int min_vtx = g->vertices[0]->data;
    for (graph_arc* arc = g->vertices[0]->firstarc; arc; arc = arc->nextarc) {
        minpathfrom[arc->vertex->data] = min_vtx;
        minpathlen[arc->vertex->data] = arc->weight;
    }
    minpathlen[min_vtx] = 0;        // put it in the tree
    /* Add new edge ( minpathfrom[min_vtx] --- min_len --> min_vtx ) */
    for (int i = 1; i < g->size; i++) {
        if (!g->vertices[i])
            continue;
        int min_len = INT_MAX;      // find the closest vertex
        for (int j = 0; j < g->size; j++)
            if (minpathlen[j] != 0 && minpathlen[j] < min_len) {
                min_len = minpathlen[j];
                min_vtx = j;
            }
        minpathlen[min_vtx] = 0;    // put it in the tree
        /* update adjacent vertex */
        for (graph_arc* arc = Graph_GetVertexByData(g, min_vtx)->firstarc; arc; arc = arc->nextarc)
            if (minpathlen[arc->vertex->data] != 0 && arc->weight < minpathlen[arc->vertex->data]) {
                minpathfrom[arc->vertex->data] = min_vtx;
                minpathlen[arc->vertex->data] = arc->weight;
            }
    }
}

该算法的复杂度分析也和 Dijkstra 算法一致：不使用优先队列时复杂度为 \\( O(|V|^2) \\) ，使用优先队列的复杂度为 \\( O(|E|\log |V|) \\) 。

Kruskal算法

Kruskal 是另一种计算最小生成树的算法，它的实现较为简单：同样将顶点独立出来并向其中添加边，每次都从图中的所有边选取权重最小的边，如果加上该边后的图不会形成圈，则说明该边是最小生成树的一部分。

还是以上面那个图为例，首先选择权重最小的边加入图中：

然后继续选择未添加的权重最小的边尝试放入图中：

继续添加边，但添加边 \\( (v_1, v_4) \\) 时发现会形成圈，因此需要抛弃该边：

重复以上步骤即可建立最小生成树。

Kruskal 算法也不难理解，不过实现时也有很多细节要注意。最大的问题是如何判断添加边后是否会形成圈：如果为连通图中的某个顶点添加一条边会形成圈，那么说明该边指向的还是这一连通图。那么只需要将图中的连通部分各做一个独立的标记，如果准备插入一个边时发现该边的两端同属一个连通图，那么就说明插入该边会产生圈。

例如，以上是某个图调用 Kruskal 算法的中间结果，它形成了三个互相独立的连通图：（这里使用不同颜色作为连通图的标记）

如果要向顶点 \\( v_4 \\) 和 \\( v_6 \\) 之间插入一条边，那么就需要先判断这两个顶点的标记是否相同：如果相同，说明它们属于同一个连通图，两者已经存在了一条路径，再向它们之间插入一条边，则又增加了一条路径，使得无向图产生了一个圈。

Kruskal 算法大致可以由以下方式实现：

void Graph_MinSpanTree_Kruskal(graph g) {

    for (int i = 0; i < g->size; i++)  // collect arcs
        if (g->vertices[i])
            for (graph_arc* arc = g->vertices[i]->firstarc; arc; arc = arc->nextarc)
                arcs[arcs_ptr++] = (struct _graph_arc) {
                    .from=g->vertices[i]->data, .to=arc->vertex->data, .weight=arc->weight };
    qsort(arcs, g->arc_num, sizeof(struct _graph_arc), CompareByWeight);

    int arcs_inserted = 0;
    for (int i = 0; i < g->arc_num; i++) {
        if (conn_mark[arcs[i].from] != conn_mark[arcs[i].to]) {
            /* insert edge (arcs[i].from <-- arcs[i].weight --> arcs[i].to) to tree */
            /* union sets between edge */
            for (int k = 0; k < g->vertex_num; k++)
                if (conn_mark[k] == conn_mark[arcs[i].to])
                    conn_mark[k] = conn_mark[arcs[i].from];

            arcs_inserted++;
            if (arcs_inserted == g->vertex_num - 1)  // minimum spanning tree has created
                break;
        }
    }
}

以上代码首先收集所有的边（注意如果用邻接表表示无向图的话每条边只应该收集一次），然后对所有边做排序，以实现从小到大插入合适的边。

在插入前需要判断边两侧顶点的标记是否相同，如果不相同便可插入，插入完成后还需更新两侧连通图的标记为同一连通图。修改标记的方式为：遍历所有顶点标记，将和边一侧顶点相同的标记修改为另一侧的标记。

这种合并方式虽然易于理解，但效率不高。如果要使用更高效的合并，需要使用某些特殊的集合数据结构才能实现。

近期文章

归档

京ICP备2021034974号
contact me by hello@frozencandles.fun