6 图

图是一种比线性表和树更为复杂的数据结构。

6.1 图的定义和基本术语

6.1.1 图的定义

  • 图：G=（V.E）

    • V：顶点（数据元素）的有穷非空集合；
    • E：边的有穷集合

  • 无向图：每条边都是无方向的

  • 有向图：每条边都是有方向的

  • 完全图：任意两个点都有一条边相连

  • 稀疏图：有很少边或弧的图（$e<nlog_2n$）

  • 稠密图：有较多边或弧的图

6.1.2 图的基本术语

  • 网，边/弧带权的图

  • 邻接：有边/弧相连的两个顶点之间的关系。

    • 存在（$v_i,v_j$）,则称为$v_i和v_j$互为邻接点
    • 存在<$v_i,v_j$>，则称$v_i$邻接到$v_j$,$v_j$邻接于$v_i$,

  • 关联（依附）：边/弧与顶点之间的关系。

    • 存在（$v_i,v_j$）/<$v_i,v_j$>，则称该边/弧关联于$v_i$和$v_j$

  • 顶点的度：与该顶点相关联的边的数目，记为TD（v）

    • 在有向图中，顶点的度等于该顶点的入度和出度之和。

    • 顶点v的入度是以v为终点的有向边的条数，记作ID（v）

    • 顶点v的出度是以v为始点的有向边的条数，记作OD（v）

  • 路径：连续的边构成的顶点序列

  • 路径长度：路径上边或弧的数目/权值之和

  • 回路（环）：第一个顶点和最后一个顶点相同的路径

  • 简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径

  • 简单回路（环）：除路径起点和终点相同外，其余顶点均不相同的路径

  • 连通图（强连通图）：在无（有）向图G=(V,{E})中，若对任意两个顶点v、u都存在从v到u的路径，则称G是连通图（强连通图）

  • 权与网：

    • 图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费。
    • 带权的图称为网

  • 子图：设有两个图$G=（V，{E}）、G_1=(V_1,{E_1})$,若$V_1属于V，E_1属于E$则称$G_1是G$的子图

  • 连通分量（强连通分量）

    • 无向图G的极大联通子图称为G的连通分量

      • 极大连通子图意思是：该子图是G联通子图，将G的任何不在该子图汇总的顶点加入，子图不再连通

    • 有向图G的极大连通子图称为G的强连通分量

      • 极大强连通子图意思是: 该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。

    • 极小联通子图：该子图是G的连通子图，在该子图中删除任何一条边，联通子图不再连通

    • 生成树:包含无向图G所有顶点的极小连通子图

    • 生成森林:对非连通图，由各个连通分量的生成树的集合

6.2 案例引入

6.2.1 六度空间理论

理论又称作六度分隔论 (Six Degrees of Separation)。六度空间理论是20世纪60年代由美国的心理学家米格兰姆(Stanley Milgram)提出的，理论指出：“你和任何一个陌生人之间所间隔的人不会超过六个”

6.3 图的类型定义

图的抽象数据类型定义如下：

1
2
3
4
5
ADT Graph{
    数据对象V：具有相同特性的数据元素的集合，称为顶点集。
    数据关系R：R{VR}
    	VR={<V,W>|<V,W>|V,W属于V^p(v,w)}， <v, w>表示从v到w的弧，P (v, w)定义了弧<v, w>的信息
}

  • 基本操作：

    • CreateGraph{&G,V,VR}

      初始条件：V是图的顶点集，VR是图中弧的集合。

      操作结果：按V和VR的定义构造图G。

    • DFSTraverse(G)

      初始条件：图G存在。

      操作结果：对图进行深度优先遍历，在遍历过程中对每个顶点访问一次。

    • BFSTraverse(G)

      初始条件：图G存在。

      操作结果：对图进行广度优先遍历，在遍历过程中对每个顶点访问一次.

6.4 图的存储结构

  • 图的逻辑结构：多对多
    • 图没有顺序存储结构，可以借助二维数组来表示元素间的关系
  • 数组表示法（邻接矩阵）
  • 链式存储结构：
    • 多重链表
      • 邻接表
      • 邻接多重表
      • 十字链表
  • 重点介绍：
    • 邻接矩阵（数组）表示法
    • 邻接表（链式）表示法

6.4.1 邻接矩阵

  • 数组（邻接矩阵）表示法

    • 建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。

      • 设图A=（V，E)有n个顶点，则

      • 顶点表Vexs[n]

        i 1 2 3 …… n-1
        Vexs[n] $V_1$ $V_2$ $V_3$ …… $V_n$

      • 图的邻接矩阵是一个二维数组$A.arcs[n][n]$,定义为：

        • $A.arcs[i][j]=\quad\begin{cases}1,如果<v_i,v_j>或(v_i,v_j)\in E\0，反之\end{cases}$

      • 无向图的邻接矩阵表示法：

        1. 无向图的邻接矩阵是对称的
        2. 顶点i的度=第i行（列）中1的个数；
        3. 完全图的邻接矩阵中，对角元素为0，其余1.

      • 有向图的邻接矩阵表示法：

        1. 有向图的邻接矩阵可能是不对称的
        2. 顶点的出度=第i行元素之和
        3. 顶点的入度=第i列元素之和
        4. 顶点的度=第i行和列的元素之和

      • 网（即有权图）的邻接矩阵表示法

      • 邻接矩阵的存储表示：用两个数组分别存储顶点表和邻接矩阵

        1
        2
        3
        4
        5
        6
        7
        8
        9
        #define Maxint 32767							//表示极大值
        #define MVNum 100 								//最大顶点数
        typedef char VerTexType;						//设顶点的数据类型为字符型
        typedef int ArcType;							//假设边的权值类型为整形
        typedef struct｛ 
            VerTexType vexs [MVNum];					//顶点表
        	ArcType arcs[MVNum) [MVNum];				//邻接矩阵
            int vexnum,arcnum;							//图的当前点数和边数
        }AMGraph;

    • 采用邻接矩阵表示法创建无向网

      1. 输入总顶点数和总边数。
      2. 依次输入点的信息存入顶点表中。
      3. 初始化邻接矩阵， 使每个权值初始化为极大值。
      4. 构造邻接矩阵。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      Status CreateUDN(AMGraph &G){//创建无向网G
          cin>>G.vexnum>>G.arcnum;//输入总顶点数，总边数
          for(i=O;i<G.vexnum;++i)
      		cin>>G.vexs[i];//依次输入点的信息
      	for(i=O;i<G.vexnum;++i)//初始化邻接矩阵呢
      		for (j=0; j<G.vexnum;++j) 
      			G.arcs[i][j]=Maxint;//变得权值均置为最大
      	for(k=O;k<G.arcnum;++k){//构造邻接矩阵
              cin>>vl>>v2>>w;//输入一条边所依附的顶点及边的权值
              i=LocateVex(G,vl);j=LocateVex(G,v2);//确定V1和V2在G中的位置
              G.arcs[i][j]=w;//边<v1,v2>的权值置为w
              G.arcs[j][i]=G.arcs[i][j];//置<v1,v2>的对称边<v2,v1>的权值为w
          }
          return OK;
      }

      补充算法：在图中查找顶点：

      1
      2
      3
      4
      5
      6
      int LocateVex(AMGraph G,VertexType u){
          int i;
          for(i=0;i<G.vexnum;++i)
              if(u==G.vexs[i]) return i;
          return -1;
      }

  • 邻接矩阵的优点

    • 直观简单好理解
    • 方便检查任意一对顶点间是否存在边
    • 方便找任一顶点的所有“邻接点”
    • 方便计算任一顶点的“度”

  • 邻接矩阵的缺点

    • 不便于增加和删除顶点
    • 浪费空间——存稀疏图有大量无效元素
      • 对稠密图来说还是很合算的
    • 浪费时间——统计稠密图中一共有多少条边

6.4.2 邻接表

  1. 无向图邻接表表示法（链式）

    • 顶点：按编号顺序将顶点数据存储在一维数组中；
    • 关联同一顶点的边（以顶点为尾的弧）：
      • 用线性链表存储
    • 特点：
      • 邻接表不唯一
      • 若无向图中有n个顶点、e条边，则其邻接表需n个头结点和2e个表结点。适宜存储稀疏图
      • 无向图中顶点$V_i$的度为第i个单链表中的结点数

  2. 有向图邻接表表示法

    • 特点：
      • 顶点$V_i$的出度为第i个单链表中的结点个数
      • 顶点的入度为整个链表中领接点域值是i-1的结点个数

  3. 图的邻接表存储表示：

    1
    2
    3
    4
    typedef struct VNode{
        VerTexType data;					//顶点信息
        ArcNode *firstarc;					//指向第一条依附该顶点的边的指针
    }VNode,AdjList[MVNum]					//AdjList表示邻接表类型

    弧（边）的结点结构 adjvex | nextarc | info

    1
    2
    3
    4
    5
    6
    #define MVNum 100						//最大顶点数
    typedef struct ArcNode{					//边结点
        int adjvex;							//该边所指向的顶点的位置
        struct ArcNode * nextarc;			//指向下一条边的指针
        OtherInfo info;						//和边相关的信息
    }ARcNode;

    图的结构定义：

    1
    2
    3
    4
    typedef struct{
        AdjList vertices;//vertices——vertex的复数
        int vexnum,arcnum;//图的当前顶点数和弧数
    }ALGraph;

    邻接表操作举例说明：

  4. 无向图的邻接表表示 p118

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Status CreateUDG(ALGraph &G) {				//采用邻接表表示法， 创建无向图 G
	cin>>G.vexnum>>G.arcnum;				//输入总顶点数，总边数
	for(i=O;i<G.vexnum;++i){				//输入各点，构造表头结点表
		cin»G.vertices[i) .data;			//输入顶点值
		G.vertices[i) .firstarc=NULL;}		//初始化表头结点的指针域
	for(k=O;k<G.arcnum;++k){				//输入各边，构造邻接表
        cin>>vl>>v2;						//输入一条边依附的两个顶点
        i=LocateVex(G,vl);
        j=LocateVex(G,v2);
        pl=new ArcNode;//生成一个新的边结点*p1
        pl->adjvex=j;//邻接点序号为j
        pl->nextarc=G.vertices[i].firstarc;
        G.vertices[i].firstarc=pl;//将新结点*p1插入顶点vi的边表头部（头插法）
        p2=new ArcNode;//生成另一个对称的新的边结点*p2
        p2->adjvex=i;//邻接点序号为i
        p2->nextarc=G.vertices[j].firstarc;
        G.vertices[j].firstarc=p2;//将心结点*p2插入顶点vj的边表头部
    }
     return OK;
}

  • 无向图邻接表特点：

    1. 方便找任一顶点的所有“邻接点”
    2. 节约稀疏图的空间
      1. 需要n个头指针和+2e个结点（每个结点至少2个域）
    3. 方便计算任一顶点的“度”
      1. 对无向图：是的
      2. 对有向图：只能计算“出度”需要构造“逆邻接表”来方便计算“入度”
    4. 不方便检查任意一对顶点间是否存在边

  • 邻接矩阵与邻接表表示法的关系

    1. 联系：邻接表中每个链表对应于接短阵中的一行，链表中结点个数等于一行中非零元素的个数。
    2. 区别：
      1. 对于任一确定的无向图，邻接矩阵是唯一的 (行列号与顶点编号一致)，但邻接表不唯一 (链接次序与顶点编号无关)
      2. 邻接矩阵的空间复杂度为$O（n^2)$,而邻接表的空间复杂度为$O(n+e)$。(e是出于$0到n^2$之间的复杂变量)
    3. 用途：邻接矩阵多用于稠密图；而邻接表多用于稀疏图

6.4.3 十字链表

有向图：

  • 顶点结点：
data firstin firstout
存与顶点相关的信息 入度边 出度边
  • 弧结点：
tailvex headvex hlink tlink
弧尾位置 弧头位置 弧头相同的下一条弧 弧尾相同的下一条弧

弧头是箭头，弧尾是箭尾

6.4.4 邻接多重表

边结点：

mark ivex ilink jvex jlink info
标志域，标记此边是否被搜索过 该边依附的两个顶点在表头数组中的位置 指向依附于ivex的下一条边 该边依附的两个顶点在表头数组中的位置 指向依附于jvex的下一条边

顶点节点

data firstedge
存与顶点有关的信息 指向第一条依附于该顶点的边

6.5 图的遍历

  • 遍历的实质：找每个顶点的邻接点的过程

  • 图常用的遍历：

    • 深度优先搜索(DFS)
    • 广度优先搜索(BFS)

6.5.1 深度优先搜索

甚多有限搜索遍历过程：

  1. 从图中某个顶点v出发， 访问v。
  2. 找出刚访问过的顶点的第一个未被访问的邻接点， 访问该顶点。 以该顶点为新顶点，重复此步骤， 直至刚访问过的顶点没有未被访问的邻接点为止。
  3. 返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点， 访问该顶点。
  4. 重复步骤 (2)和(3), 直至图中所有顶点都被访问过，搜索结束。
6.5.1.1 采用邻接矩阵表示图的深度优先搜索遍历
1
2
3
4
5
6
void DFS(AMGraph G,int v){//图G为邻接矩阵类型
    cout<<v;visited[v]=true;//访问第v个顶点
    for(w=0;w<G.vexnum;w++)//依次检查邻接矩阵v所在行
        if((G.arcs[v][w]!=0)&&(!visited[w]))
            DFS(G,w);//w是v邻接点，如果w未访问，则递归调用DFS
}
  • DFS算法效率分析
    • 用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为$O(n^2)$
    • 用邻接表来表示图，虽然有2e个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为$O(n+e)$
  • 结论
    • 稠密图适合在邻接矩阵上进行深度遍历
    • 稀疏图适合在邻接表上进行深度遍历

6.5.2 广度优先搜索

  • 用队列实现广度优先遍历，累次层次遍历那样
6.5.2.1 按广度优先非递归遍历连通图G
1
2
3
4
5
6
7
8
9
10
11
12
void BFS (Graph G,int v){
    cout<<v;visited[v]=true;//访问第v个顶点
    initQueue(Q);//辅助队列Q初始化，置空
    EnQueue(Q,v);//v进队
    while(!QueueEmpty(Q)){//队列非空
        DeQueue(Q,u);//队头元素出队并置为u
        for(W=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
            if(!visited[w]){//w为u的尚未访问的邻接顶点
                cout<<w;visited[w]=true; EnQueue(Q,w);//w进队
            }
    }
}
  • BFS算法效率分析
    • 如果邻接矩阵，则BFS对于每一个背访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为$O(n^2)$
    • 用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为$O(n+e)$
  • DFS和BFS算法效率比较
    • 空间复杂度相同，都是O(n)（借用了堆栈或队列）；
    • 时间复杂度只与存储结构（邻接矩阵或邻接表）有关，而与搜索路径无关。

6.6 图的应用

6.6.1 最小生成树

  • 生成树：所有顶点均由边连接在一起，但不存在回路的图

    • 一个图可以有许多棵不同的生成树

    • 所有生成树具有以下共同特点

      • 生成树的顶点个数与图的顶点个数相同
      • 生成树是图的极小连通子图，去掉一条边则非连通
      • 一个有n个顶点的连通图的生成树有n-1条边
      • 在生成树中再加一条边必然形成回路
      • 生成树中任意两个顶点间的路径是唯一的

  • 无向图的生成树：

    • 设图G=(V,E)是个连通图，当从图任一顶点出发遍历图G时，将边集E(G)分成两个集合T(G) 和B(G)。其中 T(G)是遍历图时所经过的边的集合，B(G)是遍历图时未经过的边的集合。显然，G1(V,T)是图G的极小连通子图。即子图G1 是连通图G的生成树

  • 最小生成树

    • 给定一个无向网络，在该网络的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。

    • 最小生成树的典型用途

      • 要在n个城市间建立通信网，则n个城市应铺设n-1条路，每条路也有对应的经济成本
      • 建立数学模型：
        • 顶点 代表城市 有n个
        • 边 代表线路 有n-1条
        • 边的权值 表示线路的经济代价
        • 连通网 表示n个城市间的通信网

  • 构造最小生成树

    • 构造最小生成树的算法很多，其中多数算法都利用了MST的性质
    • MST性质：设N=（V,E) 是一个连通网，U是顶点集V的一个非空子集。若边(u,v) 是一条具有最小权值的边，其中$u\in U，v \in V-U$则必存在一棵包含边(u,v)的最小生成树
    • 在生成树的构造过程中，图中n个顶点分属两个集合：
      • 已落在生成树上的顶点集: U
      • 尚未落在生成树上的顶点集: V-U
    • 接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边

6.6.1.1 普利姆(prim)算法

  • 算法思想：

    1. 设N=（V,E)是连通网，TE是N上最小生成树 中边的集合

    2. 初始令$U={u_0}，(u_0 \in V),TE=${}

    3. 在所有$u\in U，v \in V-U$的边$（u,v）\in E$中找一条代价最小的边$(u_0,v_0)$.

    4. 将$(u_0,v_0)$并入集合TE，同时$v_o$并入U

    5. 重复上述操作直至U=V为止，则T=（V，TE）为N的最小生成树

6.6.1.2 克鲁斯卡尔(Kruskal)算法
  • 算法思想：
    1. 设连通网 N=(VE)，令最小生成树初始状态为只有 n个顶点而无边的非连通图T=（V，{}),每个顶点自成一个连通分量。
    2. 在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上(即:不能形成环），则将此边加入到 T中;否则，舍去此边，选取下一条代价最小的边。
    3. 依此类推，直至T中所有顶点都在同一连通分量上为止。
  • 最小生成树可能不唯一
算法名 普里姆算法 克鲁斯卡尔算法
算法思想 选择点 选择边
时间复杂度 O（n^2)(n为顶点数) O(eloge)（e为边数）
适应范围 稠密图 稀疏图

6.6.2 最短路径

  • 两种最常见的最短路径问题：
    1. 单源最短路径——用Dijkstra（迪杰斯特拉）算法
    2. 所有顶点间的最短路径——用Floyd——（弗洛伊德）算法
6.6.2.1 迪杰斯特拉算法
  1. 初始化：从源点$v_0$到各终点$v_k$的直达路径 $（v_o,v_k）$，即通过一条弧到达的路径。
  2. 选择：从这些路径中找出一条长度最短的路径$（v_0,u）$.
  3. 更新：然后对其余各条路径进行适当调整：
    1. 若在图中存在弧$(u，v_k)$,且$(v_0,u)+（u，v_k）<(v_0,v_k),则以路径（v_0,u,v_k）代替（v_0，v_k)$
  4. 在调整后的各条路径中，再找长度最短的路径，依此类推

时间复杂度为 $O(n^3)$

6.6.2.2 弗洛伊德算法

6.6.3 拓扑排序

  • 有向无环图：无环的有向图，简称DAG图

    • 有向无环图常用来描述一个工程或系统的进行过程。
    • 一个工程可以分为若干个子工程，只要完成了这些子工程，就可以导致整个工程的完成

  • AOV网 拓扑排序

    • 用一个有向图表示一个工程的各子工程及其相只制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称 AOV网(Activity On Vertex network)。

  • AOE网 关键路径

    • 有向图表示一个工程的各子工程及其相互制约的关系，以弧表示活动，以顶点表示活动的开始或结束事件，称这种有向图为边表示活动的网，简称为AOE网 (Activity On Edge)

  • AOV网的特点：

    1. 若从i到j有一条有向路径，则i是j的前驱j是i的后继
    2. 若<i,j>是网中有向边，则i是j的直接前驱;j是i的直接后继
    3. AOV网中不允许有回路，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。

  • 拓扑排序

    • 在AOV 网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若 AOV 网中有弧 <i,j>存在，则在这个序列中，i一定排在的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序

  • 拓扑排序方法：

    1. 在有向图中选一个没有前驱的顶点且输出
    2. 在图中删除该顶点和所有以他为尾的弧
    3. 重复1和2直到全部顶点均已输出；当图中不存在无前驱的顶点位置
      • 一个AOV网的拓扑序列不是唯一的

  • 拓扑排序的一个重要应用：

    • 检测AOV网中是否存在环的方法：
      • 对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该 AOV 网必定不存在环。

  • 关键路径

  • 假设一个工程有11项活动，9个事件

    • 事件V1——表示整个工程开始（源点：入度为0的顶点）
    • 事件v9——表示整个工程结束（汇点：出度为0的顶点）

  • 关键路径——路径长度最长的路径
  • 路径长度——路径上各活动持续时间之和
    • ve(vj)——表示事件vj的最早发生时间
    • vl(vj)——表示事件vj的最迟发生时间
    • e(i)——表示活动ai的最早开始时间
    • l(i)——表示活动ai的最迟开始时间
    • l(i)-e(i)——表示完成活动ai的时间余量
    • 关键活动——关键路径上的活动，即l(i)==e(i)的活动（即没有时间余量的活动）

  • 其中√的为关键活动，而包含关键活动的路径为关键路径
    • 需要加快同时在几条关键路径上的关键活动
      • 如：a11,a10,a8,a7
    • 如果一个活动处于所有关键路径上，那么提高这个活动的速度，就能缩短整个工程的完成时间
      • 如：a1,a4
    • 处于所有关键路径上的活动完成时间不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时必须重新寻找关键路径