0%

数据结构与算法（11）图

发表于 分类于 本文字数： 7.9k
本文主要介绍图结构，相对于此前的线性结构（向量，列表）以及半线性结构（二叉树），图结构对其中元素的限定更少，因此它描述应用问题的能力也就更强

1.概述

1.1.基本术语

  • G = ( V; E) = ( 顶点集; 边集)

  • 顶点（vertex）：n = |V|

    边（edge）|弧（arc）：e = |E|

  • 邻接关系（adjacency）：定义同一条边的两个顶点之间的关系

    自环（self-loop）：同一顶点自我相邻

    简单图（simple graph）：不含自环，这一章讨论的都是简单图

  • 关联关系（incidence）：顶点与其所属的边之间的关系

    度（degree）：于同一顶点关联的边数

此前所学的几种数据结构都可以视作是图的特例，比如在向量和列表等线性结构中只有互为前驱与后继的元素之间才能够定义邻接关系，而树结构中只能在父节点与子节点之间才能够定义邻接关系。

图更为一般化，其中的任何两个节点之间都允许存在这样的一个邻接关系，我们这里讨论的图排除自环的存在。

1.2.无向图/有向图

  • 若关联顶点u和v次序无所谓，则(u, v)为无向边（undirected edge）

    所有边均为无方向的图，即为无向图（undigraph）

  • 反之，有向图（digraph）中均为有向边（directed edge）

    u，v分别称作边(u, v)的尾（tail）、头（head）

  • 无向边、有向边并存的图，称作混合图（mixed graph）

在图这一章我们关注有向图，因为通过有向图完全可以表示并且实现无向图以及混合图，简单的做法是将任何一条无向边转化为彼此对称的一对有向边。

1.3.路径/环路

  • 路径：$\pi$ = <$V_0,V_1,\dots,V_k>$

    长度： | $\pi$ | = k

  • 简单路劲：$V_i=V_j$ 除非$i=j$，即路劲中不含重复顶点

  • 环/环路：$V_0=V_k$

  • 有向无环图（DAG）

  • 欧拉环路：| $\pi$ | = | E |，即各边恰好出现一次

  • 哈密尔顿环路：| $\pi$ | = | V |，即各顶点恰好出现一次

2.基于邻接矩阵实现图结构

2.1. Graph模板类

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
typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus; //顶点状态
typedef enum { UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD } EType; //边在遍历树中所属的类型

template <typename Tv, typename Te> //顶点类型、边类型
class Graph { //图Graph模板类
private:
   void reset() { //所有顶点、边的辅助信息复位
      for ( int i = 0; i < n; i++ ) { //所有顶点的
         status ( i ) = UNDISCOVERED; dTime ( i ) = fTime ( i ) = -1; //状态，时间标签
         parent ( i ) = -1; priority ( i ) = INT_MAX; //（在遍历树中的）父节点，优先级数
         for ( int j = 0; j < n; j++ ) //所有边的
            if ( exists ( i, j ) ) type ( i, j ) = UNDETERMINED; //类型
      }
   }
   void BFS ( int, int& ); //（连通域）广度优先搜索算法
   void DFS ( int, int& ); //（连通域）深度优先搜索算法
   void BCC ( int, int&, Stack<int>& ); //（连通域）基于DFS的双连通分量分解算法
   bool TSort ( int, int&, Stack<Tv>* ); //（连通域）基于DFS的拓扑排序算法
   template <typename PU> void PFS ( int, PU ); //（连通域）优先级搜索框架
public:
// 顶点
   int n; //顶点总数
   virtual int insert ( Tv const& ) = 0; //插入顶点，返回编号
   virtual Tv remove ( int ) = 0; //删除顶点及其关联边，返回该顶点信息
   virtual Tv& vertex ( int ) = 0; //顶点v的数据（该顶点的确存在）
   virtual int inDegree ( int ) = 0; //顶点v的入度（该顶点的确存在）
   virtual int outDegree ( int ) = 0; //顶点v的出度（该顶点的确存在）
   virtual int firstNbr ( int ) = 0; //顶点v的首个邻接顶点
   virtual int nextNbr ( int, int ) = 0; //顶点v的（相对于顶点j的）下一邻接顶点
   virtual VStatus& status ( int ) = 0; //顶点v的状态
   virtual int& dTime ( int ) = 0; //顶点v的时间标签dTime
   virtual int& fTime ( int ) = 0; //顶点v的时间标签fTime
   virtual int& parent ( int ) = 0; //顶点v在遍历树中的父亲
   virtual int& priority ( int ) = 0; //顶点v在遍历树中的优先级数
// 边：这里约定，无向边均统一转化为方向互逆的一对有向边，从而将无向图视作有向图的特例
   int e; //边总数
   virtual bool exists ( int, int ) = 0; //边(v, u)是否存在
   virtual void insert ( Te const&, int, int, int ) = 0; //在顶点v和u之间插入权重为w的边e
   virtual Te remove ( int, int ) = 0; //删除顶点v和u之间的边e，返回该边信息
   virtual EType & type ( int, int ) = 0; //边(v, u)的类型
   virtual Te& edge ( int, int ) = 0; //边(v, u)的数据（该边的确存在）
   virtual int& weight ( int, int ) = 0; //边(v, u)的权重
// 算法
   void bfs ( int ); //广度优先搜索算法
   void dfs ( int ); //深度优先搜索算法
   void bcc ( int ); //基于DFS的双连通分量分解算法
   Stack<Tv>* tSort ( int ); //基于DFS的拓扑排序算法
   void prim ( int ); //最小支撑树Prim算法
   void dijkstra ( int ); //最短路径Dijkstra算法
   template <typename PU> void pfs ( int, PU ); //优先级搜索框架
};

2.2.邻接矩阵与关联矩阵

  • 邻接矩阵（adjacency matrix）：用二维矩阵记录顶点之间的邻接关系，矩阵元素与图中存在的边一一对应

    $A(i, j)=1$，若顶点$i$与$j$之间存在一条边；否则为0 （可以推广到带权图，即网络）

    既然只考察简单图，则对角线元素统一设置为0

    空间复杂度为$\Theta(n^2)$，与图中实际的边数无关

  • 关联矩阵（incidence matrix）：用二维矩阵记录顶点与边之间的关联关系

    空间复制度为$\Theta(n*e)=O(n^3)$

    空间利用率 < 2/n

下面是几个实例：

2.3. Vertex

下面是顶点（vertex）的一种实现方式：

1
2
3
4
5
6
7
8
9
10
11
12
typedef enum { UNDISCOVERED, DISCOVERED, VISITED } VStatus; //顶点状态

template <typename Tv> struct Vertex { //顶点对象（为简化起见，并未严格封装）
   Tv data; int inDegree, outDegree;//数据、出入度数
   VStatus status; //（如上三种）状态
   int dTime, fTime; //时间标签
   int parent;   //在遍历树中的父节点
   int priority; //在遍历树中的优先级数（最短通路、极短跨边等）
   Vertex ( Tv const& d = ( Tv ) 0 ) : //构造新顶点
      data ( d ), inDegree ( 0 ), outDegree ( 0 ), status ( UNDISCOVERED ),
      dTime ( -1 ), fTime ( -1 ), parent ( -1 ), priority ( INT_MAX ) {} //暂不考虑权重溢出
};

边（Edge）的一种实现方式：

1
2
3
4
5
6
7
8
typedef enum { UNDETERMINED, TREE, CROSS, FORWARD, BACKWARD } EStatus; //边在遍历树中所属的类型

template <typename Te> struct Edge { //边对象（为简化起见，并未严格封装）
   Te data;        //数据
   int weight;     //权重
   EStatus status; //（如上五种）状态
   Edge ( Te const& d, int w ) : data ( d ), weight ( w ), status ( UNDETERMINED ) {} //构造
};

2.4. GraphMatrix

现在就可以给出基于邻接矩阵实现图结构的一种可行方式，GraphMatrix类派生于此前所定义的Graph模板类，将顶点集实现为向量结构，其长度恰好等于顶点的规模即n；将边集实现为向量的向量，相当于一个n×n的矩阵，它恰好就是此前所构思的邻接矩阵。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename Tv, typename Te> //顶点类型、边类型
class GraphMatrix : public Graph<Tv, Te> { //基于向量，以邻接矩阵形式实现的图
private:
   Vector< Vertex< Tv > > V; //顶点集（向量）
   Vector< Vector< Edge< Te > * > > E; //边集（邻接矩阵）
public:
   GraphMatrix() { n = e = 0; } //构造
   ~GraphMatrix() { //析构
      for ( int j = 0; j < n; j++ ) //所有动态创建的
         for ( int k = 0; k < n; k++ ) //边记录
            delete E[j][k]; //逐条清除
   }
   /* 操作接口：顶点查询、顶点修改、边查询、边修改 */
};

由于我们此前对向量所重载的方括号操作符[]，这里只需用E[i][j]这样一种形式即可指代在顶点i与 j 之间的一条边，既可以读出这条边的信息，也可以反过来修改其中的某些信息。

2.5.顶点操作

按照这种实现方式，我们可以简明实现顶点操作中的大部分基本操作：

1
2
3
4
5
6
7
8
9
// 顶点的基本操作：查询第i个顶点（0 <= i < n）
   virtual Tv& vertex ( int i ) { return V[i].data; } //数据
   virtual int inDegree ( int i ) { return V[i].inDegree; } //入度
   virtual int outDegree ( int i ) { return V[i].outDegree; } //出度
   virtual VStatus& status ( int i ) { return V[i].status; } //状态
   virtual int& dTime ( int i ) { return V[i].dTime; } //时间标签dTime
   virtual int& fTime ( int i ) { return V[i].fTime; } //时间标签fTime
   virtual int& parent ( int i ) { return V[i].parent; } //在遍历树中的父亲
   virtual int& priority ( int i ) { return V[i].priority; } //在遍历树中的优先级数

对于任意顶点i，如何枚举其所有的邻接顶点neighbor？为此首先需要实现一个名为nextNbr的接口，它的功能语义是如果我们现在已经枚举到顶点i的编号为 j 的邻居，那么它将返回接下来的下一个邻居。与顶点 i 潜在的可以相邻的点，无非就是它在邻接矩阵中所对应的那一行中数值为1的单元，对应于与i邻接的一个顶点。而第一个有效的邻居是通过firstNbr接口实现，它调用了nextNbr，将顶点n（并不实际存在）作为上一个有效的邻居。

1
2
3
4
5
6
7
virtual int nextNbr ( int i, int j ) {//相对于顶点j的下一邻接顶点
   while ( ( -1 < j ) && ( !exists ( i, --j ) ) ); //逆向线性试探，O(n)
   return j; 
}  //改用邻接表可提高至O(1 + outDegree(i))
virtual int firstNbr ( int i ) { 
    return nextNbr ( i, n ); 
} //首个邻接顶点

2.6.边操作

同样地，利用邻接矩阵我们也可以便捷地实现很多边的基本操作

1
2
3
4
5
6
7
// 边的确认操作
   virtual bool exists ( int i, int j ) //边(i, j)是否存在
   { return ( 0 <= i ) && ( i < n ) && ( 0 <= j ) && ( j < n ) && E[i][j] != NULL; }
// 边的基本操作：查询顶点i与j之间的联边（0 <= i, j < n且exists(i, j)）
   virtual EStatus & status ( int i, int j ) { return E[i][j]->status; } //边(i, j)的状态
   virtual Te& edge ( int i, int j ) { return E[i][j]->data; } //边(i, j)的数据
   virtual int& weight ( int i, int j ) { return E[i][j]->weight; } //边(i, j)的权重

边插入：

假设我们需要在顶点i与顶点j之间连接一条有向边，假设这条边尚不存在，那么只需要将待插入的那条边的信息比如它的权重等等，封装为一个具体的边记录，然后将这个新的边记录地址存入于邻接矩阵中对应的那个单元，也可以说这个单元将指向这个新的边记录。

1
2
3
4
5
6
7
virtual void insert ( Te const& edge, int w, int i, int j ) { //插入权重为w的边e = (i, j)
   if ( exists ( i, j ) ) return; //确保该边尚不存在
   E[i][j] = new Edge<Te> ( edge, w ); //创建新边
   e++;   //更新边计数
   V[i].outDegree++;  //更新关联顶点i的出度
   V[j].inDegree++;   //更新关联顶点i的入数
}

边删除：

不妨假设从顶点 i 通往顶点 j 之间存在一条边，因此在邻接矩阵中对应的那一项就非空，而且这一项将指向一个对应的边记录。为了删除这条边，只需将这条边对应的记录释放并且归还给系统，然后令在邻接矩阵中对应于这一项的引用指向空。

1
2
3
4
5
6
7
8
virtual Te remove ( int i, int j ) { //删除顶点i和j之间的联边（exists(i, j)）
   Te eBak = edge ( i, j ); 
   delete E[i][j]; E[i][j] = NULL; //备份后删除边记录
   e--; 
   V[i].outDegree--; 
   V[j].inDegree--; //更新边计数与关联顶点的度数
   return eBak; //返回被删除边的信息
}

2.7.顶点插入与删除

顶点的插入与删除相对于边的操作要更为复杂，原因在于在此前的边操作中整个矩阵的规模并不会发生变化，而顶点的插入以及稍后的删除则会改变。为了在其中引入一个新的顶点，首先要将邻接矩阵中已有的各行分别向后扩展一个单元，即增加一列；接下来针对新引入的顶点还需在邻接矩阵中增加对应的一行；当然还需在第一级的边表中增加一个相应地单元用来指示或者说记录新引入的行向量；最后对应于这个新引入的顶点还需要在顶点向量中加入一个新的对应元素。

这样的四个步骤可以实现为这段代码：

1
2
3
4
5
virtual int insert ( Tv const& vertex ) { //插入顶点，返回编号
   for ( int j = 0; j < n; j++ ) E[j].insert ( NULL ); n++; //各顶点预留一条潜在的关联边
   E.insert ( Vector<Edge<Te>*> ( n, n, ( Edge<Te>* ) NULL ) ); //创建新顶点对应的边向量
   return V.insert ( Vertex<Tv> ( vertex ) ); //顶点向量增加一个顶点
}

顶点删除就是上述步骤的逆过程。

1
2
3
4
5
6
7
8
9
10
11
virtual Tv remove ( int i ) { //删除第i个顶点及其关联边（0 <= i < n）
   for ( int j = 0; j < n; j++ ) //所有出边
      if ( exists ( i, j ) ) 
         { delete E[i][j]; V[j].inDegree--; e--; } //逐条删除
   E.remove ( i ); n--; //删除第i行
   Tv vBak = vertex ( i ); V.remove ( i ); //删除顶点i
   for ( int j = 0; j < n; j++ ) //所有入边
      if ( Edge<Te> * x = E[j].remove ( i ) ) 
         { delete x; V[j].outDegree--; e--; } //逐条删除
   return vBak; //返回被删除顶点的信息
}

2.8.优缺点

邻接矩阵的优点有：

  • 直观，易于理解和实现

  • 适用范围广泛：digrah / network / cyclic / …

    尤其适用于稠密图（dense graph）

  • 判断两点之间是否存在联边：$O(1)$

  • 获取顶点的（出/入）度数：$O(1)$

    添加、删除边后更新度数：$O(1)$

  • 扩展性（scalability）：

    得益于Vector良好的空间控制策略，空间溢出等情况可“透明地”予以处理

邻接矩阵的缺点则是：

  • 空间利用率，它始终是需要$\Theta(n^2)$空间，与边数无关

在实际问题中的图通常不会有$n^2$级的边数，不妨考虑下平面图（planar graph），即可嵌入平面的图，其中不相邻的边不相交。根据欧拉推导的公式：对于所有的平面图有，$v-e+f-c=1$，各字母分别表示顶点数、边数、区域面片数、连通域数。因此平面图的边数有：$e\le 3\times n-6=O(n) \ll n^2$，此时空间利用率$\approx 1/n$。而对于一般的稀疏图（sparse graph），空间利用率同样很低，因此可以采用压缩存储技术予以改进。