数据结构 - 图 I (Graph I)

返回分类：全部文章 >> 基础知识

本文将介绍图的基础知识，并用C++实现它。

它包含两部分：

• 编程基础 - 图 I (Graph I) ：存储结构（本文）

• 编程基础 - 图 II (Graph II) ：实现完整的邻接矩阵并遍历

在查看本文之前，需要一些数据结构和程序语言的基础。

尤其是“二维数组”、“矩阵”、“矩阵的压缩(matrix)”。一些遍历和应用的内容还需要“栈(stack)”，“队列(queue)”，“二叉树(binary tree)”等的知识。

---

文章目录

• 数据结构 - 图 I (Graph I)
• 1 图的简述 (Introduction)
• 2 图的存储结构 (Storage Structure)
• 2.1 邻接矩阵 (Adjacency Matrix)
• 2.2 邻接表 (Adjacency List)
• 2.3 十字链表 (Orthogonal List)
• 2.4 邻接多重表 (Adjacency Multilist)
• 7 图的应用实例 (Graph Examples)

---

1 图的简述 (Introduction)

图的概念很多，我们只说一些重要的，其它可以去查资料。

• 图：

  • 图是由顶点集合（vertex）以及顶点间的关系集合（edge）组成的一种数据结构；
  • 图是顶点的 有穷非空 集合；
  • 有向图顶点有序，无向图顶点无序；

• 完全图：

  • 完全无向图： $n$n 个顶点的无向图有 $n \times (n-1) \div 2$n×(n−1)÷2 条边；
  • 完全有向图： $n$n 个顶点的有向图有 $n \times (n-1)$n×(n−1) 条边；

• 邻接顶点：同一条边的两个顶点，互相称为邻接顶点；

• 权（ weight 或 cost ）：具有数值标识的边；

• 网络：带有权的图；

• 顶点的度：该顶点 $v$v 的入度和出度之和；

  • 入度：以顶点为终点的边数，记作 $ID(v)$ID(v) ；
  • 出度：以顶点为出发点的边数，记作 $OD(v)$OD(v) ；

• 路径：从一点到另一点所经过的顶点序列；

  • 路径长度：通过的边数；
  • 简单路径：经过的顶点互不重复；
  • 回路（环）：出发点与终点重合；

• 连通：两个顶点间存在路径，则称这两个顶点连通。

  • 连通图：
    • 无向图中，任意两个顶点都是连通的；
    • 有向图中，路径中任意两个顶点的边必须同向；
  • 强连通图：有向图中，任意两个顶点都存在互通的路径，即双向路径。
  • 生成树：连通图的极小连通子图，如果有 $n$n 个顶点，则有 $n-1$n−1 条边

---

2 图的存储结构 (Storage Structure)

图的基本存储方式有：

• 邻接矩阵 (Adjacency Matrix)
• 邻接表 (Adjacency List)
• 十字链表 (Orthogonal List)
• 邻接多重表 (Adjacency Multilist)

2.1 邻接矩阵 (Adjacency Matrix)

在图的邻接矩阵表示中：

• 顶点列表：记录各个顶点的数据信息；
• 邻接矩阵：表示各个顶点之间的关系（边或权）；

其中无向图的邻接矩阵是对称方阵，有向图的邻接矩阵不一定对称。

Tips
无向图的存储可以进行压缩。
特殊矩阵的压缩存储 (Compressed Storage of Special Matrix)

• 无向图的邻接矩阵，一般只存储与其它结点是否连接，0表示没有连接，1表示右连接。
  例如：

  其矩阵为：

  $\begin{matrix} &A &B &C &D &E &F \\[2ex] A &0 &1 &0 &0 &1 &0 \\[2ex] B &1 &0 &0 &1 &1 &1 \\[2ex] C &0 &0 &0 &1 &0 &1 \\[2ex] D &0 &1 &1 &0 &0 &0 \\[2ex] E &1 &1 &0 &0 &0 &0 \\[2ex] F &0 &1 &1 &0 &0 &0 \end{matrix}$ABCDEF​A010010​B100111​C000101​D011000​E110000​F011000​

• 有向图的邻接矩阵，分有没有权值：

  • 没有权值依然存储0或者1；
  • 有权值的话存储的是权值，其矩阵也叫网络邻接矩阵，如果无连接用无穷符号（ $\infin$∞ ）表示。

  其矩阵为：

  $\begin{matrix} &A &B &C &D &E &F \\[2ex] A &\infin &6 &\infin &\infin &3 &\infin \\[2ex] B &2 &\infin &\infin &1 &9 &0 \\[2ex] C &\infin &\infin &\infin &2 &\infin &0 \\[2ex] D &\infin &\infin &\infin &\infin &\infin &\infin \\[2ex] E &\infin &\infin &\infin &\infin &\infin &\infin \\[2ex] F &\infin &\infin &\infin &\infin &3 &\infin \end{matrix}$ABCDEF​A∞2∞∞∞∞​B6∞∞∞∞∞​C∞∞∞∞∞∞​D∞12∞∞∞​E39∞∞∞3​F∞00∞∞∞​

• 顶点的度：

  • 无向图：其所在行或列的元素之和；
  • 有向图：
    • 出度：顶点所在行元素之和；
    • 入度：顶点所在列元素之和。

• 假设图中有 $n$n 个顶点， $e$e 条边，则邻接矩阵共有 $n^2$n2 个元素：

  • 无向图：有 $2e$2e 个非零元素（对称性）；
  • 有向图：有 $e$e 个非零元素；
  • 若 $e$e 远远小于 $n^2$n2 ，则称此图为稀疏图，其邻接矩阵为稀疏矩阵；
  • 若 $e$e 不是远远小于 $n^2$n2，则称此图为稠密图；
  • 邻接矩阵更适合稠密图。

• 对一个图来说，邻接矩阵是唯一确定的；

• 查找所有顶点的邻接顶点的时间复杂度为 $O(n^2)$O(n2) 。

其基本结构C++代码为：

// Author: https://blog.csdn.net/DarkRabbit
// Graph -> Adjaceny Matrix

#pragma once

#include <limits>
#include <vector>

namespace Graphs
{
    // 邻接矩阵
    template<typename T>
    class AdjacencyMatrix
    {
        public:
        static constexpr double INFINITE_WEIGHT = std::numeric_limits<double>::max(); // 权值无穷符号

        protected:
        std::vector<T>* m_Vertexes; // 顶点列表
        std::vector<std::vector<double>>* m_Edges; // 边的关系，邻接矩阵

        public:
        T GetVertex(int index); // 获取顶点数据
        void PutVertex(int index, const T& vertex); // 设置顶点数据
        double GetWeight(int startVertex, int endVertex); // 获取无向图关系，或有向图权值
        void PutWeight(int startVertext, int endVertex, double weight); // 设置无向图关系，或有向图权值

        public:
        AdjacencyMatrix(bool oriented); // 构造函数
        AdjacencyMatrix(const std::vector<T>& vertexElements, bool oriented); // 构造函数
        virtual ~AdjacencyMatrix(); // 析构函数

        public:
        bool InitializeVertexes(std::vector<T>& vertexElements); // 初始化顶点
        bool InitializeEdges(std::vector<int>& startVertex, 
                             std::vector<int>& endVertexes, std::vector<double>& weights); // 初始化边
        int GetVertexCount(); // 获取顶点数量
        int GetEdgeCount(); // 获取边数
        int FirstNeighbor(int index); // 获取下标为 index 的顶点的第一个邻接顶点的下标
        int NextNeighbor(int index, int neighborIndex); // 获取邻接顶点的下一个邻接顶点下标

        // and so on

    };
}

2.2 邻接表 (Adjacency List)

在图的邻接表中：

• 无向图：

  • 顶点通过边链链接其它顶点，每一个边链结点代表链接了一个其它顶点；
  • 如图所示的，顶点结点含有数据域与链接的第一条边结点，而边结点有链接的结点位置数据和另外一条边的指针。

• 有向图：

  • 出边表（邻接表）：此顶点的边指向了谁

  • 入边表（逆邻接表）：谁指向了此顶点

• 网络：

  • 出边表：

• 根据各边链接顺序不同，邻接表有多个；

• 邻接表更适合稀疏图；

• 假设图中有 $n$n 个顶点， $e$e 条边：

  • 存储无向图：需要 $n$n 个顶点， $2e$2e 个边结点；
  • 存储有向图：不考虑入边表的情况下，需要 $n$n 个顶点， $e$e 个边结点；

• 查找所有顶点的邻接顶点的时间复杂度为 $O(n+e)$O(n+e) 。

其基本结构C++代码为：

// Author: https://blog.csdn.net/DarkRabbit
// Graph -> Adjaceny List

#pragma once

#include <vector>

namespace Graphs
{
    // 边结点
    class ALEdgeNode
    {
        public:
        int destination;    // 目标下标，简写 dest
        double weight;      // 权值，也叫 cost
        ALEdgeNode* next;   // 下一条边

        ALEdgeNode(int dest, double w)
        {
            destination = dest;
            weight = w;
            next = 0;
        }
        ~ALEdgeNode()
        {
            delete next;
            next = 0;
        }
    };

    // 顶点结点
    template<typename T>
    class ALVertexNode
    {
        public:
        T element;                // 数据
        ALEdgeNode* firstEdge;    // 第一条边

        ALVertexNode(const T& e)
        {
            element = e;
            firstEdge = 0;
        }
        ~ALVertexNode()
        {
            delete firstEdge;
            firstEdge = 0;
        }
    };

    // 邻接表
    template<typename T>
    class AdjacencyList
    {
        protected:
        std::vector<ALVertexNode<T>*>* m_Vertexes; // 顶点指针列表，邻接表

        public:
        T GetVertex(int index); // 获取顶点数据
        void PutVertex(int index, const T& vertex); // 设置顶点数据
        double GetWeight(int startVertex, int endVertex); // 获取无向图关系，或有向图权值
        void PutWeight(int startVertext, int endVertex, double weight); // 设置无向图关系，或有向图权值

        public:
        AdjacencyList(); // 构造函数
        virtual ~AdjacencyList(); // 析构函数

        public:
        bool InitializeVertexes(std::vector<T>& vertexElements); // 初始化顶点
        bool InitializeEdges(std::vector<int>& startVertex, std::vector<int>& endVertexes, std::vector<double>& weights); // 初始化边
        int GetVertexCount(); // 获取顶点数量
        int GetEdgeCount(); // 获取边数
        int FirstNeighbor(int index); // 获取下标为 index 的顶点的第一个邻接顶点的下标
        int NextNeighbor(int index, int neighborIndex); // 获取邻接顶点的下一个邻接顶点下标
    };
}

2.3 十字链表 (Orthogonal List)

十字链表是有向图的存储格式 ，它是由邻接表和逆邻接表结合后的产物。在这之中我们称边为弧。

其中弧包括：

• （1）弧头顶点（head）和弧尾顶点（tail），即弧是从头顶点指向尾顶点；

• （2）弧信息（information），一般情况下存储权值；

• （3）弧头指向的下一条弧（right）；

• （4）指向弧尾的下一条弧（down）。

而顶点包括：

• （1）数据；

• （2）第一条入弧；

• （3）第一条出弧；

十字链表举例：

0：element A, firstin NULL, firstout A->B
    A->B: head 0(A), tail 1(B), right A->D, down C->B
    A->D: head 0(A), tail 3(D), right NULL, down NULL

1：element B, firstin A->B, firstout B->C
    B->C: head 1(B), tail 2(C), right NULL, down D->C

2：element C, firstin B->C, firstout C->B
    C->B: head 2(C), tail 1(B), right NULL, down NULL

3：element D, firstin A->D, firstout D->C
    D->C: head 3(D), tail 2(C), right NULL, down NULL

我使用了文字描述，图示与矩阵结构相同，下面用矩阵来说明。

放在矩阵中去看，非常清晰。

$\begin{matrix} &A &B &C &D \\[2ex] A &\infin &1 &\infin &1 \\[2ex] B &\infin &\infin &1 &\infin \\[2ex] C &\infin &1 &\infin &\infin \\[2ex] D &\infin &\infin &1 &\infin \end{matrix}$ABCD​A∞∞∞∞​B1∞1∞​C∞1∞1​D1∞∞∞​

首先是A：

• 第一条出弧，即行中第一条弧：Vertex(A)->firstout = Arc(A, B)

  • 弧头指向的下一条弧，即行中下一个弧：Arc(A, B)->right = Arc(A, D)
  • 指向同一个弧尾的下一条弧，即列中下一个弧：Arc(A, B)->down = Arc(C, B)

• 第一条入弧，即列中第一条弧：Vertex(A)->firstin = NULL

再看B：

• 第一条出弧，即行中第一条弧：Vertex(B)->firstout = Arc(B, C)

  • 弧头指向的下一条弧，即行中下一个弧：Arc(B, C)->right = NULL
  • 指向同一个弧尾的下一条弧，即列中下一个弧：Arc(B, C)->down = Arc(D, C)

• 第一条入弧，即列中第一条弧：Vertex(B)->firstin = Arc(A, B)

其基本结构C++代码为：

// Author: https://blog.csdn.net/DarkRabbit
// Graph -> Orthogonal List

#pragma once

#include <vector>

namespace Graphs
{
    // 弧结点
    class ArcNode
    {
        public:
        int row;            // 邻接矩阵行，头 head
        int col;            // 邻接矩阵列，尾 tail
        double weight;      // 弧信息，或权值 cost
        ArcNode* nextCol;   // 邻接矩阵同一行的下一条边，即头顶点指向的下一条弧，right
        ArcNode* nextRow;   // 邻接矩阵同一列的下一条边，即指向尾顶点的下一条弧，down

        ArcNode(int r, int c, double w)
        {
            row = r;
            col = c;
            weight = w;
            nextCol = 0;
            nextRow = 0;
        }
        ~ArcNode()
        {
            delete nextCol;
            nextCol = 0;
            delete nextRow;
            nextRow = 0;
        }
    };

    // 顶点结点
    template<typename T>
    class OLVertexNode
    {
        public:
        T element;          // 数据
        ArcNode* firstOut;  // 第一条出弧，即此顶点指向的第一条弧
        ArcNode* firstIn;   // 第一条入弧，即指向此顶点的第一条弧

        OLVertexNode()
        {
            firstOut = 0;
            firstIn = 0;
        }
        ~OLVertexNode()
        {
            delete firstOut;
            firstOut = 0;
            delete firstIn;
            firstIn = 0;
        }
    };

    // 十字链表
    template<typename T>
    class OrthogonalList
    {
        protected:
        std::vector<OLVertexNode<T>*>* m_Vertexes; // 顶点指针列表

        // 方法与前面都相同，省略
        // and so on
    };
}

2.4 邻接多重表 (Adjacency Multilist)

类似的，邻接多重表是为了解决邻接表中每条边都存储两次的问题。

其边结点：

• （1）mark：结点标记；

• （2）vertex1与vertex2：边所连接的顶点；

• （3）path1与path2：顶点链接的下一条边；

• （4）weight：有向图中的权值cost。

其顶点结点：

• （1）element：顶点数据

• （2）firstout：无向图的边，有向图的第一条出边

• （3）firstin：有向图的第一条入边

我们以有向图（无向图同理）为例：

以边Edge(A-B)为例：

• vertex1为A，vertex2为B；

• path1为Edge(A->D)；

• path2为Edge(B->C)；

其基本结构C++代码为：

// Author: https://blog.csdn.net/DarkRabbit
// Graph -> Adjaceny Multilist

#pragma once

#include <vector>

namespace Graphs
{
    // 边结点
    class AMLEdgeNode
    {
        public:
        int mark;                   // 顶点标记，有各种用途，典型是判断是否访问过
        int row;                    // 第一个顶点
        int col;                    // 第二个顶点
        double weight;              // 权值 cost
        AMLEdgeNode* nextRow;       // 第一个顶点下一条边
        AMLEdgeNode* nextCol;       // 第二个顶点下一条边

        AMLEdgeNode(int r, int c, double w)
        {
            row = r;
            col = c;
            weight = w;
            nextRow = 0;
            nextCol = 0;
        }
        ~AMLEdgeNode()
        {
            nextRow = 0;
            nextCol = 0;
        }
    };

    // 顶点结点
    template<typename T>
    class AMLVertexNode
    {
        public:
        T element;                 // 数据
        AMLEdgeNode* firstOut;     // 无向图的边，有向图的第一条出边
        AMLEdgeNode* firstIn;      // 有向图的第一条入边

        AMLVertexNode(const T& e)
        {
            element = e;
            firstOut = 0;
            firstIn = 0;
        }
        ~AMLVertexNode()
        {
            firstOut = 0;
            firstIn = 0;
        }
    };

    // 邻接多重表
    template<typename T>
    class AdjacencyMultilist
    {
        protected:
        std::vector<AMLVertexNode<T>*>* m_Vertexes; // 顶点指针列表，邻接表

        // 省略相同内容
        // and so on
    };
}

---

后接 编程基础 - 图 II (Graph II)

---

7 图的应用实例 (Graph Examples)

实例待补充，如果有补充将会在这里更新链接。

• 最小生成树 (Minimum Spanning Tree) ：主要应用在交通规划，电力系统规划，通信领域等需要铺设网络的方向。

  • 克鲁斯卡尔算法 (Kruskal)
  • 普利姆算法 (Prim)

• 最短路径 (Shortest Path) ：这个不用说了，非常常用；

  • 迪杰斯特拉算法 (Dijkstra)
  • 弗洛伊德算法 (Floyed)
  • A星算法 (A Star)
  • 贝尔曼-福特算法的队列优化形式 (Bellman-Ford using queue optimization)

• 活动网络 (Activity Network)

  • AOV网络 (Activity On Vertex network)，拓扑排序 (Topological-Sort)
    常用来表示各种优先级关系；
  • AOE网络 (Activity On Edge Network)，关键路径 (Critical Path)
    常用来描述和分析一项工程的计划和实施过程。

---