图的存储结构和遍历

1. 图的基本概念

图（Graph）是一种极为重要且基础的结构。由顶点（Vertex，也称为节点 Node）集合V和边（Edge）集合 E组成的一种数据结构，通常表示为 G=(V,E)其中 V代表顶点的有穷非空集合，而 E 则代表边的集合。

image-20250313135342494

接下来，我们再了解一些图相关的术语：

  • 顶点（Vertex）集合：具有有穷性且非空，意味着其中包含有限数量的顶点元素，并且至少存在一个顶点
  • 边（Edge）集合：边用于表示顶点与顶点之间的关联关系，它们可以是无向的，用以体现顶点间的双向联系，也可以是有向的，来明确顶点间的单向关联
  • 度（Degree）：在无向图中，一个顶点的度是指与该顶点相连的边的数量；
  • 入度（In - Degree）：在有向图中，入度是指向该顶点的边的数量
  • 出度（Out - Degree）：在有向图中，出度是从该顶点出发的边的数量。
  • 相邻顶点（Adjacent Vertices）：如果两个顶点之间有边相连，则称这两个顶点相邻。
  • 生成树（Spanning Tree）：连通无向图的一个子图，它是包含图中所有顶点的树（无环的连通图）。
  • 森林（Forest）：由若干棵树组成的图，即每个连通分量都是树的图。
  • 权（Weight）：与边相关的一个数值，它可以用来表示从一个顶点到另一个顶点的某种代价、距离、费用、时间等具体含义，具体的意义取决于所解决的实际问题。
  • 网（network）：通常指的是带权图，根据图的边是否有方向，网可以分为有向网和无向网。

1.1 有向图

有向图（Directed Graph，也称为Digraph）是图的一种类型，由顶点集合 V和有向边集合 E 组成，记作 G=(V,E)。其中，有向边是具有方向的边，每一条有向边由一个有序的顶点对 ⟨u,v⟩表示，意味着这条边是从顶点 u指向顶点 v。如果一个有向图，每条边都带有权值，这个图就叫做带权有向图。

对于一个有向图而言，有如下特点：

  • 边的方向性：边具有明确的方向，从一个顶点指向另一个顶点，因此 ⟨u,v⟩和 ⟨v,u⟩代表两条不同的边。
  • 顶点的入度和出度：入度指指向该顶点的有向边的数量，出度指从该顶点出发的有向边的数量。
    • 顶点H的出度是2，入度是3
    • 顶点A的出度是2，入度是1
    • 顶点B的出度是1，入度是1
  • 连通性概念特殊：有向图的连通性分为强连通和弱连通。
    • 强连通图：对于图中任意两个顶点 u和 v，都存在从 u 到 v的路径以及从 v 到 u 的路径。
    • 弱连通图：忽略边的方向后图是连通的，不要求顶点之间在有向图中一定存在双向路径。显然，强连通图一定是弱连通图，但弱连通图不一定是强连通图。
  • 特殊的边：对于有向图而言，顶点可以有一条到达自己的边，也就是这条边从当前顶点出，从当前顶点入。

1.2 无向图

无向图（Undirected Graph）同样由顶点集合 V和边集合 E组成，记作 G=(V,E)。不过，无向图中的边是没有方向的，每条边由一个无序的顶点对 (u,v)表示，意味着顶点 u 和 v 之间的连接是双向的。如果一个无向图，每条边都带有权值，这个图就叫做带权无向图。

关于无向图，它有如下的特点：

  • 边无方向性：边不具有特定的方向，(u,v) 和 (v,u)表示同一条边。
  • 顶点的度：顶点的度是指与该顶点相连的边的数量。
    • 顶点H的度为5
    • 顶点F、C的度为2
    • 顶点G、A、B的度为3
  • 连通性概念简单：如果无向图中任意两个顶点之间都存在路径，则称该无向图是连通图。
  • 无特殊的边：在无向图中，不允许边从当前顶点出，又从当前顶点入。

2. 图的存储结构

2.1 邻接矩阵

邻接矩阵（Adjacency Matrix）是图（Graph）这种数据结构的一种常用表示方法，它用一个二维数组来表示图中顶点之间的连接关系。假设图 G的顶点集合V={v0,v1,⋯ ,vn−1}，则邻接矩阵 A 中的元素 A[i][j]用于表示顶点 vi与顶点 vj之间的关系，具体规则如下：

  1. 无向图

    image-20250314105251626

    若采用邻接矩阵对上面的无向图进行存储，那么在这个二维数组里，我们可作出如下规定：

    • 如果顶点vi和vj 之间存在一条边，则 A[i][j]=A[j][i]=1。

    • 如果顶点 vi 和 vj之间不存在边，则 A[i][j]=A[j][i]=0。

    • 无向图的邻接矩阵是对称矩阵，即 A[i][j]=A[j][i] ，这是因为无向图的边没有方向，若 vi到 vj 有边，那么vj 到 vi 也必然有边。

    image-20250314105417259

  2. 有向图

    image-20250314102505570

    若采用邻接矩阵对上面的有向图进行存储，那么在这个二维数组里，我们可作出如下规定：

    • 如果存在一条从顶点 vi 到顶点vj 的有向边，则 A[i][j]=1。

    • 如果不存在从顶点 vi 到顶点 vj 的有向边，则 A[i][j]=0。

    • 有向图的邻接矩阵不一定是对称的，因为边有方向，从 vi 到 vj 有边，不意味着从 vj 到 vi 也有边。

    image-20250317114957113

    在上图的邻接矩阵中，顶点4的出度为2，分别为：4->2、4->3；入度为3，分别为：1->4、2->4、5->4。

    在该邻接矩阵里，矩阵的横向代表着各顶点的出度情况，纵向则体现了各顶点的入度情况。借助这些数据，我们能够轻而易举地还原出与之对应的有向图。

  3. 带权图

    image-20250314110546374

    对于带权图（包括带权有向图和带权无向图），邻接矩阵中的元素 A[i][j]存储的是顶点 vi 到顶点 vj的边的权值。

    • 如果顶点vi 和 vj之间存在边，A[i][j]存储该边的权值 w。

    • 如果顶点 vi 和vj之间不存在边，通常用一个特殊值（如无穷大 ∞，在编程实现中可以用一个足够大的数来表示）表示，同时 A[i][i]=0（表示顶点到自身的距离为 0）。

    image-20250314110606942

基于前文的详细讲解，接下来为大家总结一番采用邻接矩阵存储图时所具备的优缺点：

  • 优点

    1. 实现简单直观：邻接矩阵本质上是一个二维数组，其结构清晰易懂。
    2. 查询效率高：要判断图中任意两个顶点之间是否存在边，或者获取边的权值，只需通过二维数组的下标直接访问对应的矩阵元素即可。这个操作的时间复杂度为 O(1)，无论图的规模大小，查询操作都能在常数时间内完成，速度极快。
    3. 方便处理自环和重边：自环是指顶点到自身的边，重边是指两个顶点之间存在多条边。
      • 自环可以直接通过对角线上的元素体现
      • 重边可以通过对矩阵元素的值进行特殊处理（如存储边的数量或边权的累加值）来表示
    4. 适合稠密图：当图是稠密图，即图中边的数量接近顶点数量的平方时，邻接矩阵能够充分利用存储空间。

  • 缺点：

    1. 空间复杂度高：邻接矩阵的空间复杂度为 O(V2)，其中 V是图的顶点数量。

      对于稀疏图（边的数量远小于顶点数量的平方）来说，矩阵中大部分元素都是 0（表示顶点之间不存在边），这会导致大量的存储空间被浪费。

    2. 添加和删除顶点效率低：如果需要在图中添加或删除一个顶点，就需要对邻接矩阵进行扩展或缩减。

      这涉及到重新分配二维数组的空间，并将原矩阵中的数据复制到新的矩阵中，时间复杂度为 O(V2)。在动态图（图的结构会频繁发生变化）的场景下，这种操作的效率低下，会严重影响程序的性能。

    3. 不适合大规模图：由于邻接矩阵的空间复杂度与顶点数量的平方成正比，当图的规模非常大时，所需的存储空间会急剧增加，可能会超出计算机的内存限制。

2.2 邻接表

2.2.1 邻接表

邻接表（Adjacency List）是图的一种链式存储结构，它结合了数组和链表的特点。对于一个具有 V个顶点和 E条边的图，邻接表由一个包含 V个元素的数组组成，数组的每个元素对应图中的一个顶点，我们可以将这个数组看作是顶点表。而数组中的每个元素又是一个链表的头节点，这个链表被称为边表，链表中的每个节点代表与该顶点相邻的一个顶点以及它们之间边的信息（如权值）。

根据上面的描述，当我们采用邻接表这种高效且常用的方式来存储无向图、有向图、带权图时，所需要实现的整体结构实际上包含两个关键部分：

  • 顶点表：顶点数组，每个顶点包含两个部分数据，一是顶点的数据信息，二是指向该顶点邻接节点的指针。
  • 邻接表：邻接表是一个链表，链表中的每个节点代表与该顶点相邻的一个顶点，节点中通常包含相邻顶点的编号以及指向下一个相邻顶点节点的指针

在C++中可以通过STL容器来维护顶点表、邻接表这两部分数据。关于邻接表顶点结构我们可以做如下定义：

1
2
3
4
5
6
7
struct Node 
{
    int vertex;
    int weight;   // 可选
    Node* next; 
    Node(int v, int w) : vertex(v), weight(w), next(nullptr) {}
};
  • vertex：邻接顶点的编号
  • weight：带权邻接表当前这个边的权重，如果邻接表不带权则不需要该属性
  • next：指向下一个邻接节点的指针

当运用邻接表来存储有向图和无向图时，二者在某些细节之处存在差异。接下来，我将借助图表为大家清晰呈现这些差异：

  1. 无向图

    在无向图的邻接表中，如果顶点 i和顶点 j之间存在一条边，那么在顶点 i对应的链表中会有一个指向顶点 j的节点，同时在顶点j对应的链表中也会有一个指向顶点i的节点。也就是说，每条边在邻接表中会被存储两次。

  2. 有向图

    image-20250314165421395

    对于有向图，若存在一条从顶点i到顶点j的有向边，那么只会在顶点i对应的链表中添加一个指向顶点j的节点，而顶点j对应的链表中不会有关于这条边的信息（除非存在从j到i的反向边）。

    因此，当采用邻接表存储有向图时，邻接表仅能记录每个顶点的出边信息。这意味着，从数据结构的直接表现上，我们只能直接知晓每个顶点指向哪里，而无法直接得知哪些顶点指向它。所以，若需要明确某一顶点的入边情况，就只能按顺序逐个检查邻接表中的各个链表，查看是否存在指向该顶点的边，这一过程会带来额外的时间开销，尤其是在图的规模较大时，遍历操作的效率问题会更为凸显。

2.2.2 逆邻接表

逆邻接表是一种用于表示有向图的数据结构，它是邻接表的一种变体。在有向图中，普通邻接表主要记录每个顶点的出边信息，即从该顶点出发可以到达哪些其他顶点；而逆邻接表则侧重于记录每个顶点的入边信息，也就是有哪些顶点可以到达该顶点。

和邻接表类似，逆邻接表也由顶点表和邻接表两部分构成：

  • 顶点表：顶点数组，每个顶点包含两个部分数据，一是顶点的数据信息，二是指向该顶点的逆邻接节点指针。
  • 逆邻接表：对于每个顶点，其逆邻接表是一个链表，链表中的每个节点代表有一条边指向该顶点的相邻顶点，节点包含相邻顶点的编号以及指向下一个相邻顶点节点的指针。

在C++中可以通过STL容器来维护顶点表、逆邻接表这两部分数据。关于逆邻接表顶点结构和邻接表是相同的：

1
2
3
4
5
6
7
struct Node 
{
    int vertex;
    int weight;   // 可选
    Node* next; 
    Node(int v, int w) : vertex(v), weight(w), next(nullptr) {}
};
  • vertex：邻接顶点的编号
  • weight：带权邻接表当前这个边的权重，如果邻接表不带权则不需要该属性
  • next：指向该节点的逆邻接节点指针

在逆邻接表这种数据结构里，专门存储了各个节点的入边信息。不过，若要借助逆邻接表获取节点的出边信息，就不得不对整个逆邻接表展开全面遍历，此过程往往会耗费较多的时间和计算资源。

如果我们期望能够从节点中同时便捷地读取出入边和出边这两种信息，逆邻接表便显得力不从心了。这时，采用下文中即将详细介绍的十字链表就能很好地满足这一需求。十字链表在设计上兼顾了入边和出边信息的高效存储与读取，能让我们更加轻松、快速地获取节点的完整连接信息。

2.2.3 优点和缺点

最后给大家总结一下邻接表的优缺点：

  • 优点

    1. 空间效率高

      邻接表的空间复杂度为 O(V+E)，其中V是图的顶点数，E是图的边数。对于稀疏图（边的数量远小于顶点数量的平方），使用邻接表存储可以大大节省存储空间，因为它只存储实际存在的边，避免了像邻接矩阵那样为不存在的边分配大量空间。

    2. 便于插入和删除边

      在邻接表中插入或删除一条边相对容易。插入边时，只需要在相应顶点的链表中添加一个新节点；删除边时，只需要在链表中找到对应的节点并删除即可。这些操作的时间复杂度通常为O(1)或 O(d)，其中d是顶点的度（即与该顶点相邻的边的数量）。

    3. 方便遍历图

      在进行图的遍历时，邻接表可以很方便地访问一个顶点的所有邻接顶点。通过遍历顶点对应的链表，就可以依次访问到该顶点的所有出边和相邻顶点，时间复杂度为O(V+E)。

  • 缺点

    1. 查找边效率低

      在邻接表中判断两个顶点之间是否存在边，需要遍历其中一个顶点对应的链表，最坏情况下的时间复杂度为 O(d)，其中 d是顶点的度。而在邻接矩阵中，判断两个顶点之间是否存在边的时间复杂度为 O(1)。因此，当需要频繁进行边的查找操作时，邻接表的效率不如邻接矩阵。

    2. 不适合稠密图

      对于稠密图（边的数量接近顶点数量的平方），邻接表的空间优势不再明显，因为每个顶点的链表中会包含大量的节点，使得邻接表的空间复杂度接近邻接矩阵的 O(V2)。而且，由于链表的指针开销，实际占用的空间可能会比理论上的O(V+E)更大。

    3. 表示自环和重边稍复杂

      虽然邻接表可以表示自环（顶点到自身的边）和重边（两个顶点之间有多条边），但在处理时需要额外的逻辑来区分和处理这些特殊情况。例如，在统计边的数量或进行一些图算法时，需要对自环和重边进行特殊处理，增加了代码的复杂度。

2.3 十字链表

十字链表（Orthogonal List）结合了邻接表和逆邻接表的优点，既可以快速找到一个顶点的所有出边，也可以快速找到所有入边。它通过特定的指针连接方式，能够直接从顶点节点访问到其对应的入边和出边链表，无需像邻接表或逆邻接表那样进行大量的遍历操作。例如，当需要查找某个顶点的所有出边时，可以直接从该顶点的出边链表头开始遍历；当需要查找入边时，也可以直接从入边链表头开始遍历，大大提高了处理入边和出边信息的效率。

在十字链表中，存在着两个具有举足轻重地位的组成部分——边节点与顶点节点:

  • 顶点节点：存储了顶点的相关信息，同时包含指向该顶点的第一条入边和第一条出边的指针。通过这些指针，可以快速定位到该顶点的入边和出边链表，从而实现对入边和出边信息的高效访问。

    image-20250315100903014
    • data：节点中存储的数据
    • firstIn：入边表头指针，指向该顶点的入边表中第一个结点
    • firstOut：出边表头指针，指向该顶点的出边表中的第一个结点

  • 边节点：存储了一条边的详细信息，包括边的起点（尾顶点）、终点（头顶点），以及与其他边节点的关联指针。这些指针用于连接具有相同尾顶点或头顶点的边，形成出边链表和入边链表。

    image-20250316094615466
    • tailVertex：弧起点在顶点表的下标
    • headVertex：弧终点在顶点表中的下标
    • headlink：入边表指针域，指向终点相同的下一条边
    • taillink：出边表指针域，指向起点相同的下一条边
    • weight：如果是网，用来存储边的权值。如果边不带权，该属性可以忽略。

对照上文的介绍和给出的结构图，在C++中我们可以这样定义十字链表中的顶点节点和边节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 边节点结构体
struct ArcNode 
{
    int tailvex, headvex;     // 弧的尾顶点和头顶点
    ArcNode* hlink, * tlink;  // 分别指向弧头相同和弧尾相同的下一条弧
    ArcNode(int t, int h) : tailvex(t), headvex(h), hlink(nullptr), tlink(nullptr) {}
};

// 顶点节点结构体
struct VexNode 
{
    int data;                      // 顶点的数据
    ArcNode* firstin, * firstout;  // 分别指向该顶点的第一条入弧和第一条出弧
    VexNode(int d) : data(d), firstin(nullptr), firstout(nullptr) {}
};

下面是一个十字链表的示例图:

  • V1有两个出边，所以在V1的firstOut指向V0后，tailLink指向V2，形成一个出边表，对应的是图中红色箭头。
  • V0有两个入边，所以在V0的firstIn指向V1后，V1的headLink指向V2，V2后再无V0的入边顶点，所以其headLink为空，由此形成一个入边表，对应的是图中蓝色箭头。

十字链表巧妙地融合了邻接表和逆邻接表的优势，达成了二者的有机整合。借助这种独特的整合方式，无论是查找以顶点 vi为尾的弧，还是探寻以 vi为头的弧，都变得轻而易举。这种便利性使得计算顶点的出度和入度也变得十分简单高效，无需进行复杂的遍历和统计操作。

用C++基于十字链法对图进行存储和遍历的示例代码如下：

头文件 - OLGraph.h

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
class OLGraph 
{

public:
    OLGraph(int vexNum);
    ~OLGraph();

    // 添加弧
    void addArc(int tail, int head);
    // 打印十字链表
    void printOLGraph();

private:
    // 边节点结构体
    struct ArcNode 
    {
        int tailvex, headvex; 
        ArcNode* hlink, * tlink;
        ArcNode(int t, int h) : tailvex(t), headvex(h), hlink(nullptr), tlink(nullptr) {}
    };

    // 顶点节点结构体
    struct VexNode 
    {
        int data; 
        ArcNode* firstin, * firstout; 
        VexNode(int d) : data(d), firstin(nullptr), firstout(nullptr) {}
    };

private:
    void dfsRelease(ArcNode* start);
    void dfsRelease1(ArcNode* start);

private:
    int m_vexNum; 
    vector<bool> m_visited;
    vector<VexNode> m_vertices; 
};

源文件 - OLGraph.cpp

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
#include "OLGraph.h"

OLGraph::OLGraph(int vexNum) : m_vexNum(vexNum)
{
    for (int i = 0; i < m_vexNum; ++i) 
    {
        m_vertices.push_back(VexNode(i));
        m_vertices[i].firstin = nullptr;
        m_vertices[i].firstout = nullptr;
    }
    m_visited.resize(m_vexNum * m_vexNum, false);
}

void OLGraph::addArc(int tail, int head)
{
    if (tail < 0 || tail >= m_vexNum || head < 0 || head >= m_vexNum) 
    {
        cout << "Error: Invalid tail or head value!" << endl;
        return;
    }

    ArcNode* newArc = new ArcNode(tail, head);
    newArc->tlink = m_vertices[tail].firstout;
    m_vertices[tail].firstout = newArc;
    newArc->hlink = m_vertices[head].firstin;
    m_vertices[head].firstin = newArc;
}

void OLGraph::printOLGraph()
{
    for (int i = 0; i < m_vexNum; ++i) 
    {
        cout << "Vertex " << i << " - Out Arcs: ";
        ArcNode* p = m_vertices[i].firstout;
        while (p) 
        {
            cout << "(" << p->tailvex << " -> " << p->headvex << ") ";
            p = p->tlink;
        }
        cout << endl;

        cout << "Vertex " << i << " - In Arcs: ";
        p = m_vertices[i].firstin;
        while (p) 
        {
            cout << "(" << p->tailvex << " -> " << p->headvex << ") ";
            p = p->hlink;
        }
        cout << endl;
    }
}

int main() 
{
    OLGraph g(4);
    g.addArc(0, 1);
    g.addArc(0, 2);
    g.addArc(1, 3);
    g.addArc(2, 3);
    g.printOLGraph();
    return 0;
}

终端输出的结果为:

1
2
3
4
5
6
7
8
Vertex 0 - Out Arcs: (0 -> 2) (0 -> 1)
Vertex 0 - In Arcs:
Vertex 1 - Out Arcs: (1 -> 3)
Vertex 1 - In Arcs: (0 -> 1)
Vertex 2 - Out Arcs: (2 -> 3)
Vertex 2 - In Arcs: (0 -> 2)
Vertex 3 - Out Arcs:
Vertex 3 - In Arcs: (2 -> 3) (1 -> 3)

尽管十字链表的结构相对复杂，但其创建图算法的时间复杂度与邻接表保持一致。这意味着在实际应用中，使用十字链表并不会额外增加时间成本，却能显著提升对有向图中入边和出边信息的处理效率。

综上所述，在有向图的相关应用场景中，十字链表无疑是一种极为出色的数据结构模型，能够为图的存储和操作提供强大而高效的支持。

在上面实现的十字链表类中，并没有对边的资源进行释放，关于这一点会在最后一章为大家进行详细讲解。

2.4 邻接多重表

邻接多重表（Adjacency Multilist）是一种用于存储无向图的存储结构，它主要用于解决邻接表在存储无向图时，同一条边会被存储两次（因为无向图的边是双向的），造成存储空间浪费的问题。邻接多重表中，每条边只需要存储一次。

邻接多重表也是由顶点表和边表组成，其顶点节点和边节点的结构如下：

  • 顶点节点

    • data：存储顶点的数据信息。
    • firstedge：指向依附于该顶点的第一条边。

  • 边节点

    • mark：标志域，用于标记该边是否被访问过。
    • ivex 和 jvex：分别表示该边所依附的两个顶点在顶点表中的下标。
    • ilink：指向下一条依附于顶点 ivex 的边。
    • jlink：指向下一条依附于顶点 jvex 的边。
    • weight：边的权重，如果无向图的边不带权，可以忽略此属性
    image-20250318113153051

假设有一个无向图，包含顶点 v0、v1、v2、v3、v4，边有 (v0, v1)、(v0, v3)、(v2, v1)、(v2, v3)、(v2, v4)、(v4, v1)。其邻接多重表的表示如下：

温馨提示：在邻接多重表中，节点插入顺序会对表结构产生影响，不同的插入顺序会形成不同的表结构。下图中的邻接多重表，其节点是按照上文所给出的边的顺序进行插入的。并且，在链表插入节点的操作过程中，采用的是尾插法。

以下是一个使用 C++ 实现多重邻接表来表示无向图的完整例子。这个例子包含了多重邻接表的节点定义、图的构建、添加边以及遍历图的功能。

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
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 边表节点
struct EdgeNode
{
    bool mark;  
    int ivex, jvex;
    EdgeNode* ilink, * jlink; 
    EdgeNode(int i, int j) : mark(false), ivex(i), jvex(j), 
                             ilink(nullptr), jlink(nullptr) {}
};

// 顶点表节点
struct VertexNode
{
    char data; 
    EdgeNode* firstedge;
    VertexNode(char d) : data(d), firstedge(nullptr) {}
};

class Graph
{
public:
    void addVertex(char data)
    {
        m_vertices.emplace_back(data);
    }

    void addEdge(int i, int j)
    {
        if (i < 0 || i >= m_vertices.size() || j < 0 || j >= m_vertices.size())
        {
            cout << "Invalid vertex indices!" << endl;
            return;
        }

        EdgeNode* newEdge = new EdgeNode(i, j);
        newEdge->ilink = m_vertices[i].firstedge;
        m_vertices[i].firstedge = newEdge;
        newEdge->jlink = m_vertices[j].firstedge;
        m_vertices[j].firstedge = newEdge;
    }

    void traverseGraph()
    {
        for (int i = 0; i < m_vertices.size(); ++i)
        {
            cout << "Vertex: " << m_vertices[i].data << " -> ";
            EdgeNode* edge = m_vertices[i].firstedge;
            while (edge) 
            {
                if (edge->ivex == i) 
                {
                    cout << m_vertices[edge->jvex].data << " ";
                    edge = edge->ilink;
                }
                else 
                {
                    cout << m_vertices[edge->ivex].data << " ";
                    edge = edge->jlink;
                }
            }
            cout << endl;
        }
    }

    ~Graph()
    {
        queue<EdgeNode*> q;
        for (auto& vertex : m_vertices)
        {
            if (vertex.firstedge != nullptr)
            {
                q.push(vertex.firstedge);
                vertex.firstedge = nullptr;
            }
        }

        while (!q.empty())
        {
            EdgeNode* current = q.front();
            q.pop();

            if (current->mark) continue; 
            current->mark = true;
            if (current->ilink != nullptr)
            {
                q.push(current->ilink);
            }
            if (current->jlink != nullptr)
            {
                q.push(current->jlink);
            }
            delete current;
        }
    }
private:
    vector<VertexNode> m_vertices;
};

int main()
{
    Graph g;

    // 添加顶点
    g.addVertex('A');   
    g.addVertex('B'); 
    g.addVertex('C');   
    g.addVertex('D'); 
    g.addVertex('E'); 

    // 添加边
    g.addEdge(0, 1); 
    g.addEdge(0, 3);
    g.addEdge(2, 1);
    g.addEdge(2, 3); 
    g.addEdge(2, 4); 
    g.addEdge(4, 1); 

    // 遍历图
    g.traverseGraph();

    return 0;
}

在上述示例代码里，当为多重邻接表添加边时，采用了头插法将边插入边表集合，将其添加到链表头部的效率更高。这是因为若要把节点添加到尾部，需要对整个边表集合进行遍历，而头插法只需进行简单的指针操作，无需遍历链表。

在处理图的内存释放时，通常需要借助图的遍历操作来实现。图的遍历方法有很多种，但较为常用的主要有深度优先搜索（DFS）和广度优先搜索（BFS）这两种。在前面给出的示例代码中，采用的便是广度优先搜索的方式来完成图的释放。接下来，我们将围绕这两种遍历方式，为大家进行详细且深入的讲解。

3. 图的遍历

图的遍历方法种类繁多，其中最为经典且广泛应用的当属深度优先搜索和 广度优先搜索。这两种算法不仅在理论研究中占据重要地位，还在实际应用中展现了强大的能力，例如在路径查找、连通性分析、拓扑排序以及最短路径问题等领域均有出色表现。两者相辅相成，为图相关问题的解决提供了多样化的思路和工具。

3.1 深度优先搜索

深度优先搜索（Depth-First Search，简称 DFS）是一种用于遍历或搜索树或图的算法，它可以通过递归或栈的方式深入探索树或图的每一个分支，适合解决需要回溯或探索所有可能路径的场景。

深度优先搜索就像是一个执着的探险家，在图这个“迷宫”中进行探索。从图中的某个起始顶点出发，它会沿着一条路径尽可能深入地访问图中的顶点，直到无法继续前进（即当前顶点的所有邻接顶点都已被访问过），此时它会回溯到上一个顶点，再去探索其他未被访问的路径，如此反复，直到图中所有可达的顶点都被访问。

image-20250318183106563

深度优先搜索的算法步骤如下：

  • 递归方式
    1. 选择一个起始顶点作为当前顶点，并将其标记为已访问。
    2. 递归地访问当前顶点的所有未访问过的邻接顶点。
    3. 当当前顶点的所有邻接顶点都被访问过后，回溯到上一个顶点。
    4. 重复步骤 2 和 3，直到所有可达的顶点都被访问。
  • 栈方式
    1. 选择一个起始顶点，将其压入栈中，并标记为已访问。
    2. 当栈不为空时，弹出栈顶顶点。
    3. 将该顶点的所有未访问过的邻接顶点压入栈中，并标记为已访问。
    4. 重复步骤 2 和 3，直到栈为空。

接下来我们基于深度优先搜索这种方式对2.3章节中实现的十字邻接表类中的资源进行释放：

基于栈的方式对图中的边资源进行释放：

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
void OLGraph::dfsRelease(ArcNode* start)
{
    if (!start) return;

    stack<ArcNode*> arcStack;
    arcStack.push(start);

    while (!arcStack.empty()) 
    {
        ArcNode* current = arcStack.top();
        arcStack.pop();

        if (current->tailvex < 0 || current->tailvex >= m_vexNum ||
            current->headvex < 0 || current->headvex >= m_vexNum) 
        {
            continue;
        }

        int arcId = current->tailvex * m_vexNum + current->headvex;
        if (arcId < 0 || arcId >= m_visited.size()) 
        {
            continue; 
        }

        if (m_visited[arcId]) continue;
        m_visited[arcId] = true; 
        if (current->tlink) arcStack.push(current->tlink);
        if (current->hlink) arcStack.push(current->hlink);
        cout << "释放当前的边为: " << current->tailvex << "," << current->headvex << endl;
        delete current; 
    }
}

基于递归的方式对图中的资源进行释放：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void OLGraph::dfsRelease1(ArcNode* start)
{
    if (!start) return;
    if (start->tailvex < 0 || start->tailvex >= m_vexNum ||
        start->headvex < 0 || start->headvex >= m_vexNum) 
    {
        return;
    }

    int arcId = start->tailvex * m_vexNum + start->headvex;
    if (arcId < 0 || arcId >= m_visited.size()) 
    {
        return;
    }
    if (m_visited[arcId]) return;
    m_visited[arcId] = true;
    if (start->tlink) dfsRelease(start->tlink);
    if (start->hlink) dfsRelease(start->hlink);
    cout << "释放当前的边为: " << start->tailvex << "," << start->headvex << endl;
    delete start;
}

最后就可以在类的析构函数中调用dfsRelease或者dfsRelease1函数对图的所有边进行释放了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
OLGraph::~OLGraph()
{
    for (int i = 0; i < m_vexNum; ++i) 
    {
        if (m_vertices[i].firstout) 
        {
            dfsRelease(m_vertices[i].firstout);
            // dfsRelease1(m_vertices[i].firstout);
        }
        if (m_vertices[i].firstin) 
        {
            dfsRelease(m_vertices[i].firstin);
            // dfsRelease1(m_vertices[i].firstin);
        }
    }
}

当使用十字链表存储有向图时，每个顶点会维护其出边和入边的链表。如果图不连通，那么不同子图中的边之间没有直接的可达关系。也就是说，从某一个顶点的某条出边开始进行深度优先搜索（DFS），可能无法访问到其他子图中的边。

所以，为了确保释放图中所有边的内存，需要遍历每个顶点，对每个顶点的出边链表（通过 firstout 指针）和入边链表（通过 firstin 指针）分别调用 dfsRelease 函数进行释放操作。

最后再来看一下深度优先搜索的时间和空间复杂度：

  • 时间复杂度：对于一个具有n个顶点和m条边的图，如果使用邻接表来表示图，每个顶点和每条边都会被访问一次，时间复杂度为O(n+m)；若使用邻接矩阵表示图，由于需要遍历矩阵中的每个元素，时间复杂度为 O(n2)。
  • 空间复杂度：主要取决于递归调用栈的深度或栈中存储的顶点数。最坏情况下，递归深度可能达到n，所以空间复杂度为O(n)。

应用场景：

  1. 连通性检测：判断图是否连通，找出图中的连通分量。例如，在社交网络中，可以通过深度优先搜索确定哪些用户群体是相互连接的。
  2. 拓扑排序：在有向无环图（DAG）中，深度优先搜索可以用于拓扑排序，确定任务的执行顺序。比如在项目管理中，确定各个任务之间的先后依赖关系。
  3. 路径查找：寻找图中从一个顶点到另一个顶点的路径。像在地图导航中，搜索从起点到终点的可能路线。
  4. 环检测：检测图中是否存在环。在编译过程中，检查代码中的依赖关系是否存在循环依赖。

3.2 广度优先搜索

图的广度优先搜索（Breadth - First Search，BFS）是一种用于遍历或搜索图数据结构的经典算法。

广度优先搜索就像在图这个网络中进行逐层扩散的探索。从图中的某个起始顶点出发，它会先访问该顶点所有的邻接顶点，也就是距离起始顶点为 1 的所有顶点；接着，再依次访问这些邻接顶点的未被访问过的邻接顶点（距离起始顶点为 2 的顶点），以此类推，按照距离起始顶点由近到远的顺序，逐层地对图中的顶点进行访问，直到图中所有可达的顶点都被访问完毕。

image-20250318183503794

广度优先搜索的算法步骤如下：

  1. 选择起始顶点：任选图中的一个顶点作为起始点，将其标记为已访问，并将其加入到一个队列中。
  2. 队列操作 –> 当队列不为空时，执行以下操作：
    • 从队列的头部取出一个顶点。
    • 访问该顶点的所有未被访问过的邻接顶点，将这些邻接顶点标记为已访问，并将它们依次加入到队列的尾部。
  3. 结束条件：重复上述队列操作，直到队列为空，此时图中所有可达顶点都已被访问。

根据上面的步骤，我们基于广度优先搜索这种方式对2.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
AMGraph::~AMGraph()
{
    queue<EdgeNode*> q;
    for (auto& vertex : m_vertices)
    {
        if (vertex.firstedge != nullptr)
        {
            q.push(vertex.firstedge);
            vertex.firstedge = nullptr;
        }
    }

    while (!q.empty())
    {
        EdgeNode* current = q.front();
        q.pop();

        if (current->mark) continue; 
        current->mark = true;
        if (current->ilink != nullptr)
        {
            q.push(current->ilink);
        }
        if (current->jlink != nullptr)
        {
            q.push(current->jlink);
        }
        delete current;
    }
}

根据上面的代码我们来分析一下广度优先搜索的时间复杂度和空间复杂度:

  • 时间复杂度：对于一个具有n个顶点和m条边的图，如果使用邻接表来表示图，每个顶点和每条边都会被访问一次，时间复杂度为O(n+m)；若使用邻接矩阵表示图，由于需要遍历矩阵中的每个元素，时间复杂度为 O(n2)。
  • 空间复杂度：主要取决于队列中存储的顶点数。最坏情况下，队列可能需要存储所有的顶点，所以空间复杂度为O(n)。

应用场景:

  • 最短路径问题：在无权图中，广度优先搜索可以用来寻找从一个顶点到另一个顶点的最短路径。因为它是按照层次依次访问顶点的，所以第一次到达目标顶点时所经过的路径就是最短路径。例如在地图导航中，当不考虑距离权重时，可使用 BFS 寻找两点间最少经过节点数的路径。
  • 连通性检测：判断图是否连通，找出图中的连通分量。例如在社交网络分析中，确定不同用户群体之间是否存在连接。
  • 迷宫问题：在迷宫中寻找从起点到终点的最短路径。可以将迷宫抽象为图，每个格子作为一个顶点，相邻格子之间有边相连，然后使用 BFS 进行搜索。
  • 分层遍历：当需要按照层次对图进行遍历和处理时，广度优先搜索非常适用。例如在解析 HTML 文档树结构时，按层次依次处理各个节点。