第六章 图
本章作为非线性结构中的另一类结构，以多对多的数据结构形式存在，图中结点之间关系可以是任意的，任意两个元素之间都可能相关。相比于树型结构，有更广泛的应用。
本章知识点和考点较为集中，因本章涉及较多算法，所占考分比重较大，常以选择题、综合应用题的形式出现。
【考点】①图的基本概念；
②图的存储及基本操作;
③图的遍历;
④图的基本应用。
【本章大纲】
【目录】
一、图的基本概念
1.1 图的相关定义
【图】图(Graph) G由两个集合V和E组成，记为G=(V,E) , 其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。
V(G)和E(G)通常分别表示图G的顶点集合和边集合，E(G)可以为空集。若E(G)为空，则图G只有顶点而没有边。
【有向图】图G,若边集E(G)为有向边的集合，则称该图为有向图；顶点对<x, y>是有序的，它称为从顶点 x到顶点 y的一条有向边。 因此，注意<x,y>与<y, x>是不同的两条边。顶点对用一对尖括号括起来，表示x是有向边的始点，y是有向边的终点。<x, y>也称作一条弧，则 x为弧尾， y为弧头。
【无向图】若边集E(G)为无向边的集合，则称该图为无向图；在无向图中，顶点对(x, y)是无序的，它称为与顶点x和顶点y相关联的一条边。与有向图不同，这条边没有特定的方向，(x, y)与(y, x)是同一条边。为了有别于有向图，无向图的顶点对用一对圆括号括起来。
1.2 图的基本术语
依照惯例，用n表示图中顶点数目，用e表示边的数目。
【子图】假设有两个图G=(V, E)和G’= (V’, E’), 如果V’∈V且E’∈E, 则称 G’为G的子图。
如下图，都为上图的子图：
【无向完全图】若具有 n(n- 1)/2 条边，则称为无向完全图。即任意两个点都有一条边相连。
【有向完全图】若具有n(n- 1)条弧，则称为有向完全图。即任意两个点都有一条边相连。
【稀疏图、稠密图】有很少边或弧的图，称为稀疏图；有较多边或弧的图，称为稠密图。
【权、网】在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。
【邻接点】边/弧相连的两个顶点之间的关系。存在(vi, vj)，则称vi和vj互为邻接，存在<vi, vj>,则称vi邻接到vj,vj邻接于vi。
【关联(依附)】边/弧与顶点之间的关系。存在(vi, vj)/ <vi, vj>，称该边/弧关联于vi和vj。
【度、入度和出度】与该顶点相关联的边的数目，记为TD(v)。在有向图中, 顶点的度等于该顶点的入度与出度之和。
顶点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v)
顶点 v 的出度是以 v 为始点的有向边的条数, 记作OD(v)
【路径】连续的边构成的顶点序列。
【路径长度】路径上边或弧的数目/权值之和。
【回路(环)】第一个顶点和最后一个顶点相同的路径。
【简单路径】路径中各顶点均不相同的路径。
【简单回路(简单环)】除路径起点和终点相同外，其余顶点均不相同的路径。
【连通图(强连通图)】在无（有）向图G=( V, {E} )中，若对任何两个顶点 v、u 都存在从v 到 u 的路径，则称G是连通图（强连通图）。
【连通分量】无向图G 的极大连通子图称为G的连通分量。极大连通子图意思是：该子图是 G 连通子图，将G 的任何不在该子图中的顶点加入，子图不再连通。
【强连通分量】有向图G 的极大强连通子图称为G的强连通分量。极大强连通子图意思是：该子图是G的强连通子图，将D的任何不在该子图中的顶点加入，子图不再是强连通的。
【权与网】图中边或弧所具有的相关数据称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。
【极小连通子图】该子图是G 的连通子图，在该子图中删除任一条边，子图不再连通。(n-1条边)
【生成树】包含无向图G 所有顶点的极小连通子图。
【生成森林】对非连通图，各个连通分量的生成树构成的集合。
二、图的存储及基本操作
对于图这种多对多的数据结构也有多种存储方式，接下来仔细介绍。
2.1 邻接矩阵
临界矩阵表示法所用的顺序存储结构思想。其主要思想为建立一个顶点表（记录各个顶点信息）和一个邻接矩阵（表示各个顶点之间关系）。设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]，定义如下：
2.1.1 无向图的邻接矩阵表示法
以下图为例，按照邻接矩阵表示法构造无向图的邻接矩阵如图，分析可得：
①无向图的邻接矩阵是对称的；
②顶点i 的度＝第 i 行 (列) 中1 的个数；
③完全图的邻接矩阵中，对角元素为0，其余为1。
2.1.2 有向图的邻接矩阵表示法
以下图为例，按照邻接矩阵表示法构造有向图的邻接矩阵如图，其中第i行表示以结点vi为尾的弧(即出度边），第i列表示以结点vi为头的弧(即入度边），分析可得：
①有向图的邻接矩阵可能是不对称的;
②顶点的出度=第i行元素之和;
③顶点的入度=第i列元素之和;
④顶点的度=第i行元素之和+第i列元素之和。
2.1.3 网（有权图）的邻接矩阵表示法
以下图为例，按照邻接矩阵表示法构造有权网的邻接矩阵如图，其中若两点之间有边则存储其权值，否则记为∞。
2.1.4 邻接矩阵表示法的实现
【优缺点】①优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边等等。
②缺点：n个顶点需要n*n个单元存储边;空间效率为O(n2)。 对稀疏图而言尤其浪费空间。
【算法思想】①输入总顶点数和总边数；
②依次输入点的信息存入顶点表中；
③初始化邻接矩阵，使每个权值初始化为极大值；
④构造邻接矩阵。
【算法描述】
Status CreateUDN(AMGraph &G){
//采用邻接矩阵表示法，创建无向网G
cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数
for(i = 0; i<G.vexnum; ++i)
cin>>G.vexs[i]; //依次输入点的信息
for(i = 0; i<G.vexnum;++i) //初始化邻接矩阵，边的权值均置为极大值
for(j = 0; j<G.vexnum;++j)
G.arcs[i][j] = MaxInt;
for(k = 0; k<G.arcnum;++k){ //构造邻接矩阵
cin>>v1>>v2>>w; //输入一条边依附的顶点及权值
i = LocateVex(G, v1); 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(MGraph G,VertexType u)
{//存在则返回u在顶点表中的下标;否则返回-1
int i;
for(i=0;i<G.vexnum;++i)
if(u==G.vexs[i])
return i;
return -1;
}2.2 邻接表
邻接表表示法所用的链式存储结构思想。其主要思想为对每个顶点vi 建立一个单链表，把与vi有关联的边的信息链接起来，每个结点设为3个域，如下所示。同时，所有单链表的头结点，用顺序存储结构存储，每个单链表有一个头结点（设为2个域），存vi信息。
2.2.1 无向图的邻接表表示法
以下图为例，按照邻接表表示法构造无向图的邻接表如图，其中若两点之间有边，则将于其关联的边的信息链接存储起来。 通过这种方法TD(Vi)表示为单链表中链接的结点个数。
其构造结构，如图所示，分析可得空间效率为O(n+2e)。若是稀疏图(e<<n2)，比邻接矩阵表示法O(n2)省空间。同时，应该注意因各个边结点的链入顺序是任意的，邻接表构造结果不唯一。
2.2.2 有向图的邻接表表示法
以下图为例，按照邻接表表示法构造有向图的邻接表如图，其中若两点之间有边，则将于其关联的边的信息链接存储起来。通过这种方法结点i的出度OD(Vi)＝单链出边表中链接的结点数，结点i的入度ID(Vi)＝邻接点域为Vi的弧个数，而结点i的度TD(Vi) = OD(Vi)+ ID( Vi )
其构造结构，如图所示，分析可得空间效率为O(n+e)。
2.2.3 邻接表的实现
【优缺点】①优点:空间效率高，容易寻找顶点的邻接点；
②缺点:判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。
【算法思想】采用邻接表表示法创建无向网,具体过程如下：
①输入总顶点数和总边数。
②依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。
③创建邻接表。
【算法描述】
Status CreateUDG(ALGraph &G){
//采用邻接表表示法，创建无向图G
cin>>G.vexnum>>G.arcnum; //输入总顶点数，总边数
for(i = 0; i<G.vexnum; ++i){ //输入各点，构造表头结点表
cin>> G.vertices[i].data; //输入顶点值
G.vertices[i].firstarc=NULL; //初始化表头结点的指针域为NULL
}//for
for(k = 0; k<G.arcnum;++k){ //输入各边，构造邻接表
cin>>v1>>v2; //输入一条边依附的两个顶点
i = LocateVex(G, v1); j = LocateVex(G, v2);
p1=new ArcNode; //生成一个新的边结点*p1
p1->adjvex=j; //邻接点序号为j
p1->nextarc= G.vertices[i].firstarc; G.vertices[i].firstarc=p1;
//将新结点*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;
}
2.3 十字链表
十字链表表示法所用的链式存储结构思想，但与邻接表有些差别。
2.3.1 无向图的十字链表表示法
对于无向图结点的存储分为结点表中的结点存储和边结点表中的结点存储。
【结点表中的结点的表示】主要存储两个信息分别为
①data（结点的数据域，保存结点的数据值）；
②firstedge（结点的指针域，给出自该结点出发的的第一条边的边结点的地址）。
【边结点表中的结点的表示】主要存储六个相关信息分别为
①info（边结点的数据域，保存边的权值等）；
②mark（边结点的标志域，用于标识该条边是否被访问过）；
③ivex（本条边依附的一个结点的地址）；
④ilink（依附于该结点（地址由ivex给出）的边中的下一条边的地址）；
⑤jvex: 本条边依附的另一个结点的地址。
⑥jlink: 依附于该结点（地址由jvex给出的边中的下一条的地址）。
【构造方式】
2.3.2 有向图的十字链表表示法
对于有向图结点的存储分为结点表中的结点存储和边结点表中的结点存储。
【结点表中的结点的表示】主要存储三个信息分别为
①data（结点的数据域，保存结点的数据值）；
②firstin（结点的指针域，给出自该结点出发的的第一条边的边结点的地址；
③firstout（结点的指针域，给出进入该结点的第一条边的 边结点的地址）。
【边结点表中的结点的表示】主要存储五个相关信息分别为
①info（边结点的数据域，保存边的权值等）；
②tailvex（本条边的出发结点的地址）；
③headvex（本条边的终止结点的地址）；
④hlink（终止结点相同的边中的下一条边的地址）；
⑤tlink（出发结点相同的边中的下一条边的地址）。
【构造方式】
2.4 邻接多重表
邻接多重表表示法所用的也是链式存储结构思想， 是无向图的另一种链式存储结构。虽然邻接表是无向图的一种很有效的存储结构，但是，在邻接表中，如对已被搜索过的边作记号或删除一条边等，此时需要找到表示同一条边的两个结点。
因此，在进行这一类操作的无向图的问题中采用邻接多重表作存储结构更为适宜。其存储分为结点表中的结点存储和边结点表中的结点存储。
【结点表中的结点的表示】
①data域存储和该顶点相关的信息；
②firstedge域指示第一条依附于该顶点的边。
【边结点表中的结点的表示】
①mark（标志域，可用以标记该条边是否被搜索过）；
② ivex 和 jvex为该边依附的两个顶点在图中的位置；
③ ilink（ 指向下一条依附千顶点 ivex 的边）；
④ jlink( 指向下一条依附千顶点jvex的边);
⑤ info（指向和边相关的各种信息的指针域）。、
【构造方式】在邻接多重表中，所有依附千同一顶点的边串联在同一链表中，由于每条边依附于两个顶点，则每个边结点同时链接在两个链表中。
【分析】对无向图而言，其邻接多重表和邻接表的差别，仅仅在千同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。因此，除了在边结点中增加一个标志域外，邻接多重表所需的存储量和邻接表相同。
2.5 邻接矩阵与邻接表表示法对比
根据有同一无向图，分别使用邻接矩阵和邻接表进行构造，如下图所示，分析可得出邻接表中每个链表对应于邻接矩阵中的一行，而链表中结点个数等于一行中非零元素的个数。
【区别】① 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表不唯一（链接次序与顶点编号无关）。
② 邻接矩阵的空间复杂度为O(n2),而邻接表的空间复杂度为O(n+e)。
【用法】邻接矩阵多用于稠密图；而邻接表多用于稀疏图
三、图的遍历（⭐⭐⭐）
从已给的连通图中某一顶点出发，沿着边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历。
然而，图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。为了解决这些问题，设置辅助数组 visited [n]，用来标记每个被访问过的顶点，初始状态为0，当顶点i被访问时，改 visited [i]为1，防止被多次访问。
3.1 广度优先遍历（BFS）
【算法思想】（1）从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。
（2）只要队列不空，则重复下述处理。
①队头顶点u出队；
②依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w，并置visited[w]的值为true，然后将w进队。
【构造过程】设从顶点A开始出发
①将A结点进队，此时队列非空，队头顶点A出队，其邻接点B、C、D进队；
②此时队列非空，队头顶点B出队，其邻接点E（C已访问过）进队；
③此时队列非空，队头顶点C出队，其邻接点F（A、B已访问过）进队；
④此时队列非空，队头顶点D出队，其邻接点A、F已访问过；
⑤此时队列非空，队头顶点E出队，其邻接点G（B已访问过）进队；
⑥此时队列非空，队头顶点F出队，其邻接点H（D、C已访问过）进队；
⑦此时队列非空，队头顶点G出队，其邻接点E已访问过；
⑧此时队列非空，队头顶点H出队，其邻接点I（F已访问过）进队；
⑨此时队列非空，队头顶点I出队，此时队列空，循环完毕
最终，得到广度优先生成树为
【特点】①与层序遍历结构相同，且没有回退情况；
②邻接矩阵的DFS唯一，邻接表的DFS不唯一。
【算法描述】
void BFS (Graph G, int v){
//按广度优先非递归遍历连通图G
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对于每一个被访问到的顶点，都要循环检测矩阵中的整整一行（n个元素），总的时间代价为O(n2)。
②用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 个结点即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)。
3.2 深度优先遍历（DFS）
【算法思想】访问起始点v;
①若v的第1个邻接点没访问过，深度遍历此邻接点；
②若当前邻接点已访问过，再找v的第2个邻接点重新遍历。
【构造过程】假设从顶点A开始遍历：
①A顶点为被遍历过，从此结点开始深度遍历，并标记为已遍历,得A→B→E→C；
②C→A顶点时，顶点A以访问过，从A邻接的第三个D结点开始，D→F。
③至此，所有结点都被访问过。
【特点】①稠密图适于在邻接矩阵上进行深度遍历；稀疏图适于在邻接表上进行深度遍历。
②邻接矩阵的DFS唯一，邻接表的DFS不唯一。
【算法描述】
void DFS(ALGraph G, int v){ //图G为邻接表类型
cout<<v; visited[v] = true; //访问第v个顶点
p= G.vertices[v].firstarc; //p指向v的边链表的第一个边结点
while(p!=NULL){ //边结点非空
w=p->adjvex; //表示w是v的邻接点
if(!visited[w]) DFS(G, w); //如果w未访问，则递归调用DFS
p=p->nextarc; //p指向下一个边结点
}
}【算法分析】
①用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n2)。
②用邻接表来表示图，虽然有 2e 个表结点，但只需扫描 e 条边即可完成遍历，加上访问 n个头结点的时间，时间复杂度为O(n+e)