数据结构 - 图 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\times (n-1)÷2$ 条边；完全有向图： $n$ 个顶点的有向图有 $n\times (n-1)$ 条边；

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

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

网络：带有权的图；

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

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

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

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

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

连通图： 无向图中，任意两个顶点都是连通的；有向图中，路径中任意两个顶点的边必须同向； 强连通图：有向图中，任意两个顶点都存在互通的路径，即双向路径。生成树：连通图的极小连通子图，如果有 $n$ 个顶点，则有 $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表示右连接。 例如：

A B E D F C

其矩阵为：

$$\begin{array}{ccccccc}& A& B& C& D& E& F\\ A& 0& 1& 0& 0& 1& 0\\ B& 1& 0& 0& 1& 1& 1\\ C& 0& 0& 0& 1& 0& 1\\ D& 0& 1& 1& 0& 0& 0\\ E& 1& 1& 0& 0& 0& 0\\ F& 0& 1& 1& 0& 0& 0\end{array}$$

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

没有权值依然存储0或者1；有权值的话存储的是权值，其矩阵也叫网络邻接矩阵，如果无连接用无穷符号（ $\infty$ ）表示。 6 2 3 1 9 0 0 2 3 A B E D F C

其矩阵为：

$$\begin{array}{ccccccc}& A& B& C& D& E& F\\ A& \infty & 6& \infty & \infty & 3& \infty \\ B& 2& \infty & \infty & 1& 9& 0\\ C& \infty & \infty & \infty & 2& \infty & 0\\ D& \infty & \infty & \infty & \infty & \infty & \infty \\ E& \infty & \infty & \infty & \infty & \infty & \infty \\ F& \infty & \infty & \infty & \infty & 3& \infty \end{array}$$

顶点的度：

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

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

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

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

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

其基本结构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)

在图的邻接表中：

无向图：

无向图 A C D B first edge next first edge first edge next first edge 0: element A dest 2 dest 3 1: element B dest 2 2: element C dest 0 dest 1 3: element D dest 0 顶点通过边链链接其它顶点，每一个边链结点代表链接了一个其它顶点；如图所示的，顶点结点含有数据域与链接的第一条边结点，而边结点有链接的结点位置数据和另外一条边的指针。

有向图：

有向图 A B C

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

first edge first edge next 0: element A dest 1 1: element B dest 0 dest 2 2: element C

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

first edge first edge first edge 0: element A dest 1 1: element B dest 0 2: element C dest 1

网络：

网络 5 3 9 A B C

出边表：

first edge first edge next 0: element A dest 1, weight 5 1: element B dest 0, weight 3 dest 2, weight 9 2: element C

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

邻接表更适合稀疏图；

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

存储无向图：需要 $n$ 个顶点， $2e$ 个边结点；存储有向图：不考虑入边表的情况下，需要 $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）第一条出弧；

十字链表举例：

A B D C 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{array}{ccccc}& A& B& C& D\\ A& \infty & 1& \infty & 1\\ B& \infty & \infty & 1& \infty \\ C& \infty & 1& \infty & \infty \\ D& \infty & \infty & 1& \infty \end{array}$$

首先是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：有向图的第一条入边

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

有向图 A B D C

以边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) 常用来描述和分析一项工程的计划和实施过程。

---