数据结构第六章(上篇)

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 图的类型定义

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

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行和列的元素之和
网（即有权图）的邻接矩阵表示法

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

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

#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;

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

输入总顶点数和总边数。
依次输入点的信息存入顶点表中。
初始化邻接矩阵，使每个权值初始化为极大值。
构造邻接矩阵。

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;
}

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

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 邻接表

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

图的邻接表存储表示：

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

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

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

图的结构定义：

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

邻接表操作举例说明：

无向图的邻接表表示 p118

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 深度优先搜索

甚多有限搜索遍历过程：

从图中某个顶点v出发，访问v。
找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。
返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。
重复步骤 (2)和(3), 直至图中所有顶点都被访问过，搜索结束。

6.5.1.1 采用邻接矩阵表示图的深度优先搜索遍历

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

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 图