Chapter13 图

图的定义

图可以用G=(V, E)表示。其中，V是顶点集，E是边集。
有向图：如果边是有方向的，称为有向图。
- 有向图的边用<>表示。<A,B>表示从A出发到B的一条边。在有向图中，<A,B>和<B,A>是不一样的。

无向图：如果边是无方向的，称为无向图。无向图的边通常用（）表示。（A，B）表示顶点A和B之间有一条边。无向图也称为双向图。
加权图：边被赋予一个权值的图称为加权图。如果图是有向的，称为加权有向图，如果是无向的，称为加权无向图。

图的基本术语

邻接：若（Vi，Vj）是图中的一条边，则称Vi和Vj是邻接的。如<Vi，Vj>是图中的一条边，则称Vi邻接到Vj，或Vj和Vi邻接。
度：无向图中邻接于某一顶点的边的总数。
入度：有向图中进入某一顶点的边数，称为该顶点的入度
出度：有向图中离开某一顶点的边数，称为该顶点的出度
边与度的关系：度是二分之一边的数目（对于无向图和有向图都适用！）

$e = \dfrac{1}{2} \sum d_i$

子图

设有两个图G=（V，E）和G‘=（V’，E’），如果 $V' \subseteq V,E' \subseteq E$ ，则称G’是G的子图

人话：一个图是另外一个图的一部分

路径

对1<i<N，顶点序列w1,w2,……wN 中的顶点对（wi, wi+1）都有（wi, wi+1）∈ E或<wi, wi+1> ∈ E，那么，w1,w2,……wN是图中的一条路径。
非加权的路径长度就是组成路径的边数，对于路径w1,w2,……wN，非加权路径长度为N-1。
加权路径长度是指路径上所有边的权值之和。
**简单路径和环：**如果一条路径上的所有顶点，除了起始顶点和终止顶点可能相同外，其余的顶点都不相同，则称其为简单路径。一个回路或环是一条简单路径，其起始顶点和终止顶点相同，且路径长度至少为1。

无向图的连通性

连通：顶点v至v’ 之间有路径存在
连通图：无向图 G 的任意两点之间都是连通的，则称 G 是连通图。
连通分量：非连通图中的极大连通子图

有向图的连通性

强连通图：有向图 G 的任意两点之间都是连通的，则称 G 是强连通图。
强连通分量：极大连通子图
弱连通图：如有向图G不是强连通的，但如果把它看成是无向图时是连通的，则称该图是弱连通的

完全图

完全图：每两个顶点之间都有边的无向图称为完全图。完全图有 $C_n^2 = \dfrac{n(n-1)}{2}$ 条边。其中n是顶点个数
有向完全图：每两个顶点之间都有边的无向图称为完全图。完全图有 $P_n^2 = n(n-1)$ 条边。其中n是顶点个数
有向无环图：如果一个有向图中没有环，则称为有向无环图

生成树与最小生成树

生成树是图G的极小连通子图G’，其中V(G’)=V(G)
用一颗树把图中所有的顶点都连起来（没有回路！）
生成树有n个顶点，n-1条边
生成树可以有多个
最小生成树（MST）：最小代价生成树

图的运算

常规操作：
- 构造一个由若干个顶点、若干条边组成的图；
- 判断两个顶点之间是否有边存在；
- 在图中添加或删除一条边；
- 返回图中的顶点数或边数；
- 按某种规则遍历图中的所有顶点。
和应用紧密结合的运算：
- 拓扑排序和关键路径
- 找最小生成树
- 找最短路径等。

图的存储

邻接矩阵和加权邻接矩阵

表示有向图

设有向图具有 n 个顶点，则用 n × n列的布尔矩阵 A 表示该有向图

在物理实现时的考虑：分别用 0、1、2、3 分别标识顶点A、B、C、D。而将真正的顶点数据字段之值放入一个一维数组之中。

注意：

出度: i行之和。
入度: j列之和。

表示无向图

设无向图具有 n 个顶点，则用 n × n的布尔矩阵 A 表示该无向图：

注意：

无向图的邻接矩阵是一个三角对称矩阵
顶点i的度: 第i行或第i列之和。

表示加权图

设有向图具有 n 个顶点，则用 n × n 的矩阵 A 表示该有向图；如果i 至 j 有一条有向边且它的权值为a ，则A[i,j] = a 。如果 i 至 j 没有一条有向边。则A[i,j] = 空或其它标志

特点

优点：判断任意两点之间是否有边方便，仅耗费 O(1) 时间。
缺点：即使 << n2 条边，也需内存 n2 单元，太多; 仅读入数据耗费 O( n2 ) 时间，太长。而大多数的图的边数远远小于n2。
适合稠密网不适合增加删除顶点

邻接表

设有向图或无向图具有 n 个顶点，则用顶点表和边表表示该有向图或无向图。
顶点表：用数组或单链表的形式存放所有的顶点。
- 如果顶点数n已知，则采用数组形式，否则应采用单链表的形式。每个元素包含两个部分：顶点值和指向该顶点对应的边表的首地址。
边表（边结点表）：每条边用一个结点进行表示。同一个顶点出发的所有的边形成它的边结点单链表。

特点

邻接表是图的标准存储方式
优点：内存＝顶点数＋边数，处理时间也是顶点数＋边数，即为O(|V|+|E|)，适合稀疏网。
当谈及图的线性算法时，一般指的是O(|V|+|E|)
缺点：
- 确定 i --> j 是否有边，最坏需耗费 O(n) 时间。
- 无向图同一条边表示两次。边表空间浪费一倍。
- 有向图中寻找进入某结点的边，非常困难（逆邻接表）。

图的遍历

对有向图和无向图进行遍历是按照某种次序系统地访问图中的所有顶点，并且使得每个顶点需且只能被访问一次。在图中某个顶点可能和图中的多个顶点邻接并且存在回路，因此在图中访问一个顶点u之后，在以后的访问过程中，又可能再次返回到顶点u，所以需对访问过的顶点加以标记。

深度优先搜索（dfs）

选中第一个被访问的顶点；
对顶点作已访问过的标志；
依次从顶点的未被访问过的第一个、第二个、第三个…… 邻接顶点出发，进行深度优先搜索。

这是一个递归的过程，如果相邻顶点都被访问过时，则需要回溯，返回到前面的顶点进行搜索。回溯以栈的记忆功能实现。

深度优先搜索的实现

深度优先搜索DFS的实现方法和树的前序遍历算法类似，但必须对访问过的顶点加以标记
dfs函数不需要参数，也没有返回值。它从编号最小的结点出发开始搜索，并将对当前对象的深度优先搜索的序列显示在显示器上。
以邻接表为例
- 设置一个数组visited，记录顶点是否被访问过
- 设计一个私有的深度优先搜索的函数，从某一顶点出发访问所有可达顶点
- 如果是无向非连通图的或有向非强连通，则对图中尚未访问的顶点反复调用深度优先搜索，形成深度优先搜索的森林。

公有的dfs函数

void dfs( )
{ 
    对每个节点 v
        visited [v] = false;
  
    while (v = 尚未访问的节点）
       dfs(v，visited);  
}

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::dfs() const
{
   bool *visited = new bool[Vers]; 

   for (int i=0; i < Vers; ++i) visited[i] = false;

   cout << "当前图的深度优先遍历序列为：" << endl;
   for (i = 0; i < Vers; ++i) {
	   if (visited[i] == true) continue;
	   dfs(i, visited);
	   cout << endl;
   }
}

私有的dfs函数

访问从结点v出发可以访问到的所有结点

void dfs( v，visited )
{
    visited[v] = true;
    for 每个 v的邻接点w
        if( ! visited[w] )
            dfs( w,visited );
}

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::dfs
                              (int start, bool visited[]) const
{ 
    edgeNode *p = verList[start].head;
  
    cout << verList[start].ver << '\t';  
    visited[start] = true;
    while (p != NULL){ 
	    if (visited[p->end] == false) dfs(p->end, visited);
	    p = p->next;
    }
}

时间性能分析

dfs函数将对所有的顶点和边进行访问，因此它的时间代价和顶点数 |V| 及边数 |E| 是相关的，即是O(|V|+|E|)。
如果图是用邻接矩阵来表示，则所需要的时间是O（|V|2）。

广度优先搜索（bfs）

选中第一个被访问的顶点；
对顶点作已访问过的标志；
依次访问已访问顶点的未被访问过的第一个、第二个、第三个……第 m 个邻接顶点 W1 、W2、W3…… Wm ，进行访问且进行标记，转向3；
如果还有顶点未被访问，则选中一个起始顶点，转向2；
所有的顶点都被访问到，则结束。

广度优先搜索一般使用队列实现

广度优先搜索的实现

广度优先搜索和树的层次遍历算法类似

需要记录每个顶点是否已被访问
需要记住每个已被访问的顶点的后继顶点，然后依次访问这些后继顶点。这可以用一个队列来实现
过程：
- 将序号最小的顶点放入队列重复取队列的队头元素进行处理，直到队列为空。
- 对出队的每个元素，首先检查该元素是否已被访问。如果没有被访问过，则访问该元素，并将它的所有的没有被访问过的后继入队
- 检查是否还有顶点未被访问。如果有，重复上述两个步骤

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::bfs() const
{ 
   bool *visited = new bool[Vers];
   int currentNode;
   linkQueue<int> q;
   edgeNode *p; 
   for (int i=0; i < Vers; ++i) visited[i] = false; 
   cout << "当前图的广度优先遍历序列为：" << endl; 
   for (i = 0; i < Vers; ++i) {
	 if (visited[i] == true) continue;
	 q.enQueue(i);
      while (!q.isEmpty()) {
		 currentNode = q.deQueue();
		 if (visited[currentNode] == true) continue;
		 cout << verList[currentNode].ver << '\t';
		 visited[currentNode] = true;
		 p = verList[currentNode].head;
		 while (p != NULL){
	        if (visited[p->end] == false) q.enQueue(p->end);
	        p = p->next;
		 }      
     }
	 cout << endl;
  }
}

图遍历的应用

无向图的连通性

如果无向图是连通的，则从无向图中的任意顶点出发进行深度优先搜索或广度优先搜索都可以访问到每一个顶点。访问的次序是一棵深度/广度优先生成树。

如果图是非连通的，深度/广度优先搜索可以找到一片深度/广度优先生成森林。每棵树就是一个连通分量。对无向图来说，深度/广度优先搜索可以找到了它的所有连通分量。

前面介绍的讨论的深度优先和广度优先遍历中，都已实现了这个功能。在这两个函数的输出中，每一行代表一个连通分量。

有向图的连通性

对有向图，深度优先搜索可以测试是否强连通，并找出所有强连通分量：

从任意顶点开始深度优先遍历G；
对森林中的每棵树进行后序遍历，并按遍历的顺序给每个顶点编号；
将G的每条边逆向，形成Gr；
从编号最大的顶点开始（按编号从大到小的顺序）深度优先遍历Gr，得到的深度优先遍历森林的每棵树就是G的强连通分量。

欧拉回路

如果都是偶数桥，从任意地方出发都能回到原点（欧拉回路）。

如果只有两个地方有奇数桥，可以从这两个地方之一出发，经过所有的桥一次，再回到另一个地方（欧拉路径）。如果有奇数桥的地方不止两个，满足要求的路径是找不到的。

寻找欧拉回路的思想

执行一次深度优先的搜索。从起始顶点开始，沿着这条路一直往下走，直到无路可走。而且在此过程中不允许回溯。
找出路径上的另外一个尚有未访问的边的顶点，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。

具体方法

检查存在性
找出回路：
- 执行一次深度优先的搜索。
- 从起始顶点开始，沿着这条路一直往下走，直到无路可走。而且在此过程中不允许回溯。
- 路径上是否有一个尚有未访问的边的顶点。如果有，开始另一次深度优先的搜索，将得到的遍历序列拼接到原来的序列中，直到所有的边都已被访问。

欧拉回路的实现

拓扑排序

设G=（V，E）是一个具有n个顶点的有向无环图。
V中的顶点序列V1，V2，…，Vn称为一个拓扑序列，当且仅当该序列满足下列条件：若在G中，从Vi到Vj有一条路径，则序列中Vi必须排在Vj的前面。
拓扑排序将图转化为线性序，相对前驱后继关系保持不变。

顶点活动网络（Activity On Vertex network）

顶点表示各项子任务（活动）
有向边表示具有先决条件关系，仅当作为某一子任务的所有作为先决条件的子任务实施完成后，该项子任务才能得以实施。
AOV的特点：
1. 有起始顶点
2. 无回路

找出拓扑排序的过程

第一个输出的顶点（序列中的第一个元素）：必须无前驱，即入度为0
后继：它的前驱全部输出之后才能输出。
无前驱及后继的顶点：任何时候都可输出。
逻辑删除法：
- 当某个顶点被输出后，该顶点以及从该顶点出发的边都被删除，所有以该顶点作为前驱的所有顶点的入度减1。
- 实现的时候，不需要真正去删边，只需要维护一个存储每个节点入度的数组，然后输出顶点时，将所有以该顶点作为前驱的所有顶点的入度减1即可

for example

有可能一次操作有多个节点的入度变成0，但实现的时候一次只能输出一个值，故使用一个队列来处理输出操作

拓扑排序的实现

计算每个顶点的入度，保存在数组inDegree中；
检查inDegree中的每个元素，将入度为0的顶点入队；
不断重复以下操作，直到队列为空
- 从队列中将入度为0的顶点出队
- 输出此顶点，并将该顶点的后继顶点的入度减1；
- 如果某个邻接点的入度为0，则将其入队。

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>::topSort( ) const
{  
   linkQueue<int> q;
   edgeNode *p;
   int current, *inDegree = new int[Vers];
   for (int i = 0; i < Vers; ++i)   inDegree[i] = 0;
   for ( i = 0; i < Vers; ++i){
     for (p = verList[i].head; p != NULL; p = p->next)
	   ++inDegree[p->end];
   }//计算入度
   for (i = 0; i < Vers; ++i)
       if (inDegree[i] == 0) q.enQueue(i);//入度0节点入队
   cout << "拓扑排序为：" << endl;
   while( !q.isEmpty( ) ){
        current = q.deQueue( );
        cout << verList[current].ver << '\t';
        for (p = verList[current].head; p != NULL; p = p->next)
            if( --inDegree[p->end] == 0 )  q.enQueue( p->end );
    }//出队，删除关联的边
   cout << endl;
}

时间复杂度分析

如果图以邻接表表示
总的执行时间也是O（|V|+|E|）
- 计算入度需要O（|V|+|E|）的时间
- 搜索入度为0的顶点需要O（|V|）的时间
- 每个顶点入一次队、出一次队。每出一次队，需要检查它的所有后继顶点，因此也需要O（|V|+|E|）的时间。

关键路径

边活动网络AOE(Activity on Edge)

AOE网络：加权有向无环图。
顶点表示事件，边表示活动，有向边的权值表示活动的持续时间，有向边的方向表示事件发生的先后次序。
顶点的进入边表示事件发生的条件
顶点的发出边表示事件发生后允许开始的活动。有一个源点、一个终点。

最早发生时间

设顶点x的最早发生时间记为ee(x)，边<u,v>的长度记为Luv；
首先设所有顶点的最早发生时间是0；
对每个被遍历的顶点u检查它的后继v。如果ee(u)+Luv > ee(v)，则更新ee(v)为ee(u)+Luv。终点的最早发生时间即关键路径的长度。

找关键路径的思路

计算每个顶点的活动时间余量：最迟发生时间-最早发生时间余量为0的顶点就是关键路径上的顶点
- 最早开始时间：记为ee(x)，每个直接前驱的最早发生时间加上从该前驱到该顶点的活动时间的最大者
- 最迟发生时间：记为le(x) ，每个直接后继的最迟发生时间减去顶点到该直接后继的活动时间的最小者就是该顶点的最迟发生时间。

关键路径算法

按照从头到尾遍历拓扑序列，计算每个顶点的最早发生时间；
按照从尾到头遍历逆向遍历拓扑序列，计算每个顶点的最迟发生时间；
从头到尾遍历拓扑序列，找出最早发生时间和最迟发生时间相等的顶点，组成关键路径。

最早发生时间计算方法

设顶点x的最早发生时间记为ee(x)，边<u,v>的长度记为Luv；
首先设所有顶点的最早发生时间是0；
对每个被遍历的顶点u检查它的后继v。如果ee(u)+Luv > ee(v)，则更新ee(v)为ee(u)+Luv。终点的最早发生时间即关键路径的长度。

最迟发生时间计算方法

设顶点x的最迟发生时间记为le(x)；
首先设所有顶点的最迟发生时间是关键路径的长度
对每个被遍历（从尾到头）的顶点u检查它的后继v。如果le(v) - Luv < le(u)，则更新le(u)为le(v)-Luv。

代码实现

template <class TypeOfVer, class TypeOfEdge>
void adjListGraph<TypeOfVer, TypeOfEdge>
                                        ::criticalPath( ) const
{ 
    TypeOfEdge *ee = new TypeOfEdge[Vers],*le = new TypeOfEdge[Vers];
    int *top = new int[Vers], *inDegree = new int[Vers];      
    linkQueue<int> q;
    int i;
    edgeNode *p;
    // 找出拓扑序列，放入数组top
    for (i = 0; i < Vers; ++i) {      //计算每个结点的入度
	      inDegree[i] = 0;
	      for (p = verList[i].head; p != NULL; p = p->next)
		     ++inDegree[p->end]; 
    }
    for (i = 0; i < Vers; ++i)          //将入度为0的结点入队
	     if (inDegree[i] == 0) q.enQueue(i); 
    i = 0;
	while( !q.isEmpty( ) ) {
	      top[i] = q.deQueue( );		  
	      for (p = verList[top[i]].head; p != NULL; p = p->next)
               if( --inDegree[p->end] == 0 )    q.enQueue( p->end );
	       ++i;
     }
        // 找最早发生时间
   for (i = 0; i < Vers; ++i) ee[i] = 0;
   for (i = 0; i < Vers; ++i) {         // 找出最早发生时间存于数组ee
      for (p = verList[top[i]].head; p != NULL; p = p->next)
	   if (ee[p->end] < ee[top[i]] + p->weight )  
                 ee[p->end] = ee[top[i]] + p->weight; // ee(u)+Luv > ee(v)
    }

     // 找最晚发生时间
    for (i = 0; i < Vers; ++i) le[i] = ee[Vers -1];
    for (i = Vers - 1; i >= 0 ; --i)        // 找出最晚发生时间存于数组le
        for (p = verList[top[i]].head; p != NULL; p = p->next)
	   if(le[p->end] - p->weight < le[top[i]]  )
                    le[top[i]] = le[p->end] - p->weight; // le(v) - Luv < le(u)
    // 找出关键路径
    for (i = 0; i < Vers; ++i)
        if (le[top[i]] == ee[top[i]]) 
	   cout << "(" << verList[top[i]].ver 
                   << ",  " << ee[top[i]] << ")  ";
}