6.1 图的概念
####6.1.1 图的定义
图(Graph)G由顶点集合V(G)和边集合E(G)构成。
G=(V,E)
V={0,1,2,3,4}
E={(0,1),(0,4),(1,2),(1,3),(2,3),(3,4)}
图抽象数据类型 = 逻辑结构 + 基本运算
图的基本运算如下：
- InitGraph(&g)：图初始化
- ClaerGraph(&g)：销毁图
- DFS(G,v)：从顶点v出发深度优先遍历
- BFS(G,v)：从顶点v出发广度优先遍历
在图G中，如果代表边的顶点对是无序的，则称G为无序图。用圆括号序偶表示无向边。(0,1)
如果表示边的顶点对是有序的，则称G为有向图。用尖括号序偶表示有向边。<0,1>
6.1.2 图的基本术语
1.端点和邻接点
无向图：若存在一条边(i,j) → 顶点 i 和顶点 j 为端点，它们互为邻接点。
有向图：若存在一条边<i,j> → 顶点 i 为起始端点(简称为起点)，顶点 j 为终止端点(简称终点)，他们互为邻接点。
2.顶点的度、入度和出度
无向图：以顶点 i 为端点的边数成为该顶点的度。
有向图：以顶点 i 为终点的入边的数目，成为该顶点的入度。以顶点 i 为起始点的出边的数目，成为该顶点的出度。一个顶点的入度与出度的和为该顶点的度。
3.完全图
无向图：每两个顶点之间都存在着一条边，成为完全无向图，包含有 n(n-1)/2 条边。
有向图：每两个顶点之间都存在着方向相反的两条边，成为完全有向图，包含 n(n-1) 条边。
4.稠密图、稀疏图
当一个图接近完全图时，则称为稠密图。
相反，当一个图含有较少的边数时，则称为稀疏图。
5.子图
设有两个图G=(V,E)和G’=(V’,E’)，若V’是V的子集 且 E’是E的子集，则称G’是G的子图。
6.路径和路径长度
路径长度是指一条路径上经过的边的数目。
若一条路径上除开始点和结束点可以相同外，其余顶点均不相同，则称此路径为简单路径。
7.回路或环
若一条路径上的开始点与结束点为同一个顶点，则此路径被称为回路或环。
开始点与结束点相同的简单路径被称为简单回路或简单环。
8.连通、连通图和连通分量
无向图：若从顶点 i 到顶点 j 有路径，则称顶点 i 和 j 是连通的。
若图中任意两个顶点都连通，则称为连通图，否则称为非连通图。
无向图G中的极大连通子图称为G的连通分量。显然，任何连通图的连通分量只有一个，即本身，而非连通图有多个连通分量。
9.强连通图和强连通分量
有向图：若从顶点 i 到顶点 j 有路径，则称从顶点 i 到 j 是连通的。
若图G中的任意两个顶点 i 和 j 都连通，即从顶点 i 到 j 和从顶点 j 到 i 都存在路径，则称图G是强连通图。
在一个非强连通中找强联通分量的方法：
① 在图中找有向环。
② 扩展该有向环：如果某个订单到该环中任一顶点有路径，并且该环中任一顶点到这个顶点也有路径，则加入这个顶点，
10.权和网
图中每一条边都可以附带有一个对应的数值，这种与边先关的数值成为权。权可以表示从一个顶点到另一个顶点的距离或花费的代价。
边上带有权的图成为带权图，也称作网。
6.2 图的存储结构
图的两种主要存储结构：邻接矩阵、邻接表。
6.2.1 邻接矩阵存储方法
无序图的邻接矩阵一定是对称的，有序图的邻接矩阵不一定对称。
邻接矩阵的主要特点：
① 一个图的邻接矩阵表示是唯一的。
② 特别适合稠密图的存储，存储空间为O(n^2)。
图的邻接矩阵存储类型定义如下：
#define MAXV<最大顶点个数>
typedef struct{
int no; //顶点编号
InfoType info; //顶点其他信息
}VertexType;
//声明的邻接矩阵类型
typedef struct{ //图的定义
int edges[MAXV][MAXV]; //邻接矩阵
int n,e; //顶点数，边数
VertexType vexs[MAXV]; //存放顶点信息
}MGraph;
6.2.2 邻接表存储方法
① 对图中么个顶点 i 建立一个单链表，将顶点 i 的所有邻接点链起来。
② 每个单链表上添加一个表头节点（表示顶点信息）。并将所有表头节点构成一个数组，下标为 i 的元素表示顶点 i 的表头节点。
图的邻接表存储方法是一种顺序分配与链式分配相结合的存储方法。
有两类节点：头节点、边节点
邻接表的特点如下：
- 邻接表表示不唯一。
- 特别适合稀疏图存储，存储空间为O(n+e)。
//声明边界点类型
typedef struct ANode{
int adjvex; //该边的终点编号
struct ANode *nextarc; //指向下一条边的指针
InfoType info; //该边的权值等信息
}ArcNode;
//声明邻接表头节点类型
typedef struct VNode{
Vertex data; //顶点信息
ArcNode *firstarc; //指向第一条边
}
//声明图邻接表类型
typedef struct{
VNode adjlist[MAXV]; //邻接表
int n,e; //图中顶点数n和边数e
}ALGraph;
6.3 图的遍历
6.3.1 图的遍历的概念
从给定图中任意指定的顶点出发，按照某种搜索方法沿着图的边访问图中的所有顶点，使每个顶点仅被访问一次，这个过程称为图的遍历。
图的遍历得到的顶点序列称为图遍历序列。
根据搜索方法的不同，图的遍历方法分为两种：深度优先遍历（DFS）、广度优先遍历（BFS）
6.3.2 深度优先遍历算法
深度优先遍历过程：
(1)从图中某个初始顶点v出发，首先访问初始顶点v。
(2)选择一个与顶点v相邻且没有被访问过的顶点w，再从w出发进行深度优先搜索，直到图中与当前顶点v邻接的所有顶点都被访问过为止。
算法设计思路：
(1)深度优先遍历的过程体现出后进先出的特点：用栈或递归方式实现。
(2)如何确定一个顶点是否访问过？设置一个visited[]全局数组，visited[i]=0表示顶点i没有访问；visited[i]=1表示顶点i已经访问过。
void DFS(ALGraph *G,int v){
ArcNode *p;int w;
visited[v] = 1; //置已访问标记
printf("%d",v); //输出被访问顶点的编号
p=G->adjlist[v].firstarc; //p指向顶点v的第一条边的边头节点
while(p!=NULL){
w=p->adjvex;
if(visited[w]==0)
DFS(G,w); //若w顶点未访问，递归访问它
p=p->nextarc; //p指向顶点v的下一条边的边头节点
}
}
6.3.3 广度优先遍历算法
广度优先遍历的过程：
(1) 访问初始点v，接着访问v的所有未被访问过的邻接点。
(2) 按照邻接点的次序访问每一个顶点的所有未被访问过的邻接点。
(3) 依次类推，知道图中所有和初始点v有路径相同的顶点都被访问过为止。
算法设计思路：
(1) 广度优先搜索遍历体现先进先出的特点，用队列实现。
(2) 如何确定一个顶点是否访问过？设置一个visited[]数组，visited[i]=0表示顶点 i 没有访问；visited[i]=1表示顶点 i 已经访问过。
采用邻接表的BFS算法：
void BFS(ALGraph *G,int v){
ArcNoed *p;int w,i;
int queue[MAXV],front=0,rear=0; //定义循环队列
int visited[MAXV];
for(i=0;i<G->n;i++)
visited[i]=0; //访问标志数组初始化
printf("%2d",v); //输出被访问顶点的编号
visited[v]=1; //置已访问标记
rear=(rear+1)%MAXV;
queue[rear]=v; //v进队
while(front!=rear){ //队列不空时循环
front=(front+1)%MAXV;
w=queue[front]; //出队并赋给w
p=G->adjlist[w].firstarc; //找w的第一个的邻接点
while(p!=NULL){
if(visited[p->adjvex]==0){
printf("%2d",p->adjvex)； //访问之
visited[p->adjvex]=1;
rear=(rear+1)%MAXV; //相邻顶点进队
queue[rear]=p->adjvex;
}
p=p->nextarc; //找下一个邻接顶点
}
}
}
6.3.4 非连通图的遍历
无向连通图：调用一次DFS或BFS，能够访问到图中的所有顶点。
无向非连通图：调用一次DFS或BFS，只能访问到初始点所在连通分量中的所有顶点，不可能访问到其他连通分量中的顶点。
可以分别遍历每个连通分量，才能够访问到图中的所有顶点。
采用深度优先遍历方法遍历非连通图的算法如下：
void DFS1(ALGraph *G){
int i;
for(i=0;i<G->n;i++) //遍历所有未访问过的顶点
if(visited[i]==0)
DFS(G,I);
}
采用广度优先遍历方法遍历非连通图的算法如下：
void BFS1(ALGraph *G){
int i;
for(i=;i<G->n;i++) //遍历所有未访问过的顶点
if(visited[i]==0)
BFS(G,I);
}
6.4 图遍历的应用
6.4.1基于深度优先遍历算法的应用
例6-2
假设图G采用邻接表存储，设计一个算法，判断顶点 u→v 是否有简单路径。
解：从顶点u开始进行深度优先遍历，当搜索到顶点v时表名从顶点u到v有路径，用形参has表示顶点 u→v 是否有路径。
void ExistPath(AGraph *,int u,int v,bool &has){
//has表示u到v是否有路径，初值为false;
int w;ArcNode *p;
visited[u]=1; //置以访问标记
if(u==v){ //找到了一条路径
has=true; //置has为true并结束算法
return
}
p=G->adjlist[u].firstarc; //p指向顶点u的第一个相邻点
while(p!=NULL){
w=p->adjvex;
if(visited[w]==0) //若w顶点未访问，递归访问它
ExistPath(G,w,v,has)
p=p->nextarc; //p指向顶点u的下一个相邻点
}
}
6.5 生成树和最小生成树
6.5.1 生成树的概念
一个连通图的生成树是一个极小连通子图，它含有图中全部n个顶点和构成一棵树的(n-1)条边。
深度优先生成树、广度优先生成树
最小生成树的概念：
(1) 对于带权连通图G（每条边上的权均为大于0的实数），可能有多棵不同生成树。
(2) 每棵生成树的所有边的权值之和可能不同。
(3) 其中权值之和最小的生成树成为图的最小生成树。
6.5.2 非连通图和生成树
连通图：仅需调用遍历过程一次，从图中任一顶点出发，便可以遍历图中的各个顶点，产生相应的生成树。
非连通图：需多次调用遍历，生成森林。
6.5.3 最小生成树与普里姆算法
Prim算法是一种构造性算法，用于构造最小生成树，更适合稠密图求最小生成树。
(1) 初始化U={v}。v到其他顶点的所有边为候选边。
(2) 重复以下步骤n-1次，使得其他n-1个顶点被加入到U中：
① 从候选变中挑选权值最小的边输出，设该边在V-U中的顶点是k，将k加入U中；
② 考察当前V-U找那个的所有顶点j，修改候选变：若(j,k)的权值小于原来和顶点k关联的候选边，则用(k,j)取代后者作为候选边。
算法设计（解决4个问题）：
(1) 如何求U、V-U两个顶点集之间的最小边？
答：只考虑V-U中顶点 j 到 U 顶点集的最小边（无向图），比较来找最小边。
(2) 如何存储顶点 j 到 U 顶点集的最小边？
答：closes[j]表示顶点 j 到 U 集合的最小顶点，(j,closest[j])是顶点j的最小边，权值为lowcost[j]。
(3) 一个顶点属于哪个集合
答：lowcost[k]=0 表示属于U集合，lowcost[k]!=0 表示属于V-U集合。
(4) 图采用哪种存储结构更合适？
答：邻接矩阵。
void Prim(MGraph g,int v){
int lowcost[MAXV];
int min;
int closest[MAXV],i,j,k;
for(i=0;i<g.n;i++){ //初始化
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for(i=1;i<g.n;i++){ //输出n-1条边
min=INF;
for(j=0;j<g.n;j++) //在V-U中找出离U最近的顶点k
if(lowcost[j]!=0 && lowcost[j]<min){
min=lowcost[j];
k=j; //k记录最近顶点编号
}
printf(" 边(%d,%d)权为:%d\n",closest[k],k,min); //这里可以建树
lowcost[k]=0; //标记k已经加入U
for(j=0;j<g.n;j++) //修改数组lowcost和closest
if(lowcost[j]!=0 && g.edges[k][j]<lowcost[j]){
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
6.5.4 求最小生成树的克鲁斯卡尔算法
Kruskal算法也是一种求带权无向图的最小生成树的构造性算法。
按权值的递增次序选择合适的边来构造最小生成树的方法。
Kruskal算法过程：
(1) 置U的初值等于V，表示最小生成树的边集TE的初值为空集。
(2) 将图G中的边按权值从小到大的顺序依次选取：
① 若选取的边未使生成树T形成回路，则加入TE；
② 否则舍弃，直到TE中包含(n-1)条边为止。
算法设计（解决3个问题）:
(1) 图采用哪种存储结构更合适？ 邻接矩阵
(2) 边的排序问题？ 这里采用直接插入排序算法
(3) 如何解决加入一条边后是否出现回路？ 采用连通分量编号或顶点集合编号
假设给定一个加权连通图G，G的边集合为E，顶点个数为n，要求其一棵最小生成树T。
假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。
1）将所有顶点涂成红色；
2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红；
3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。
注意到在算法执行过程中，红色顶点和红色边会形成一个或多个连通分支，它们都是G的子树。一条边与红色边形成圈当且仅当这条边的两个端点属于同一个子树。因此判定一条边是否与红色边形成圈，只需判断这条边的两端点是否属于同一个子树。
上述判断可以如此实现：给每个子树一个不同的编号，对每一个顶点引入一个标记t，表示这个顶点所在的子树编号。当加入一条红色边，就会使该边两端点所在的两个子树连接起来，成为一个子树，从而两个子树中的顶点标记要改变成一样。综上，可将Kruskal算法细化使其更容易计算机实现。
6.6 最短路径
6.6.1 路径的概念
考虑带权有向图，把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。
从源点到终点可能不止一条路径，把路径长度最短的那条路径 称为最短路径。
6.6.2 从一个顶点到其余各顶点的最短路径
问题描述：给定一个带权有向图G与源点v，求从v到G中其 他顶点的最短路径，并限定各边上的权值大于或等于0。
单源最短路径问题：Dijkstra算法
求解思路：
把图中顶点集合V分成两组：
(1) 第1组为已求出最短路径的顶点集合，用S表示。
(2) 第2组为其余未求出最短路径的顶点集合，用U表示。
每一步求出v到U中一个顶点u的最短路径，并将u移动到S中，直到U为空。
算法过程：
(1) 初始化：S只包含源点即S={v}，v的最短路径为0。U包含除 v 外的其他顶点，U中顶点 i 距离为边上的权值或无穷大。
(2) 从U中选取一个距离 v 最小的顶点 u，把 u 加入S中(该选定的距离就是v→u的最短路径长度)。
(3) 以u为新考虑的中间点，修改U中各顶点 j 的最短路径长度：若从源点 v 到顶点 j 的最短路径长度(经过顶点u)比原来最短路径长度(不经过顶点u)短，则修改顶点 j 的最短路径长度。
顶点 v→j 的最短路径长度 = MIN(Cvk+Wkj,Cvj)
(4) 重复步骤(2) 和(3) 知道所有顶点都包含在S中。
算法设计：
(1) 如何存放最短路径长度：
用一维数组dist[j]存储！
源点v默认，dist[j]表示源点→顶点j的最短路径长度。
如dist[2]=12表示源点→顶点2的最短路径长度为12。
(2) 如何存放最短路径：
从源点到其他顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点0→5的最短路径为0、2、3、5，表示为path[5]={0,2,3,5}。
所有n-1条在最短路径可以用二维数组path[][]存储。
改进：用一维数组path[]记录每个顶点到源点的最短路径中的前驱节点。
狄克斯特拉算法如下(v为源点编号)，复杂度为O(n^2):
void Dijkstra(MGraph g,int v){
int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
//dist和path数组初始化
for(i=0;i<g.n;i++){
dist[i]=g.edges[v][i]; //距离初始化
s[i]=0; //s[]置空
if(g.edges[v][i]<INF) //路径初始化
path[i]=v; //顶点v到i有边时
else path[i]=1; //顶点v到i没边时
}
s[v]=1; //源点v放入S中
for(i=0;i<g.n;i++){
mindis=INF;
for(j=0;j<g.n;j++)
if(s[j]==0&&dis[j]<mindis){
u=j;
mindis=dist[j];
}
s[u]=1; //顶点u加入S中
for(j=0;j<g.n;j++) //修改不在s中的顶点的距离
if(s[j]==0)
if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j]){
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v); //输入最短路径
}
6.6.3 每对顶点之间的最短路径
问题表述：对于一个各边权值均大于零的有向图，对每一对顶点i!=，求出顶点 i 与 顶点 j 之间的最短路径和最短路径长度。
多源最短路径问题：Floyd算法
| Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行 | V | 次Dijkstra算法，也要高于执行V次。 |
优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。
缺点：时间复杂度比较高，不适合计算大量数据。
算法：迭代(递推)思路
假设有向图G=(V,E)采用邻接矩阵存储。设置一个二维数组A用于存放当前顶点之间的最短路径长度，分量A[i][j]
表示当前顶点i→j的最短路径长度。
A[i][j]：i→j的路径上所经过的顶点编号不大于k的最短路径长度。
(1) 初始时，有A-1[i][j]=g.edges[i][j]。
(2) 考虑从 i→j 的最短路径进过编号为k顶点的情况：
Ak[i,j]=MIN{Ak-1[i,j]，Ak-1[i,k]+Ak-1[k,j]}
算法设计（解决2个问题）：
(1) 用二维数组A存储最短路径长度：
Ak[i][j]表示考虑顶点0~k后得出的 i→j的最短路径长度。
An-1[i][j]表示最终的 i→j的最短路径长度。
(2) 用二维数组path存放最短路径：
pathk[i][j]表示考虑顶点0~k后得出的i→j的最短路径。
pathn-1[i][j]表示最终 i→j 的最短路径。
弗洛伊德算法如下(算法复杂度为O(n^3))：
void Floyd(MatGraph g){ //求每对顶点之间的最短路径
int A[MAXVEX][MAXVEX]; //建立A数组
int path[MAXVEX][MAXVEX]; //建立path数组
int i,j,k;
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++){
A[i][j]=g.edges[i][j];
if(i!=j ^ g.edges[i][j]<INF)
path[i][j]=i; //i和j顶点之间有一条边时
else path[i][j]=-1; //i和j顶点之间没有一条边时
}
for(k=0;k<g.n;k++) //求Ak[i][j]
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
if(A[i][j]>A[i][k]+A[k][j]){ //找到更短路径
A[i][j]=A[i][k]+A[k][j]; //修改路径长度
path[i][j]=path[k][j]; //修改最短路径为经过顶点k
}
}
Floyd算法共享前面路径比较所得到的信息A
6.7 拓扑排序
设G=(V,E)是一个具有n个顶点的有向图，V中顶点序列v1，v2,…,vn称为一个拓扑序列，当且仅当该顶点蓄力满足下列条件：若<i,j>是图中的边(或从顶点i→j有一条路径)：则在拓扑序列中顶点i必须排在顶点j之前。
在一个有向图中找一个拓扑序列的过程称为拓扑排序。
拓扑排序步骤：
(1) 从有向图中选择一个没有前驱的顶点并且输出它。
(2) 从图中删去该顶点，并且删去从该顶点发出的全部有向边。
(3) 重复上述两步，直到剩余的图中不再存在没有前驱的顶点为止。
拓扑排序算法设计：
将邻接表定义中的VNode类型修改如下：
typedef struct{ //表头节点类型
Vertex data; //顶点信息
int count; //存放顶点入度
ArcNode *firstarc; //指向第一条边
}
拓扑排序算法如下：
void TopSort(VNode adj[],int n){
int i,j;int St[MAXV],top=-1; //栈St的指针为top
ArcNode *p;
for(i=0;i<n;i++)
if(adj[i].count==0){ //入度为0的顶点进栈
top++;
St[top]=i;
}
while(top>-1){ //栈不为空时循环
i=St[top];top--; //出栈
printf("%d",i);
p=adj[i].firstarc;
while(p!=NULL){
j=p->adjvex;adj[j].count--;
if(adj[j].count==0){
top--;
St[top]=j;
}
p=p->nextarc; //找下一个相邻顶点
}
}
}
6.8 AOE网与关键路径
1.什么是AOE网
(1) 用一个带权有向图(DAG)描述工程的预计进度。
(2) 顶点表示事件，有向边表示活动，边e的权c(e)表示完成活动e所需的时间。
(3) 图中入度为0的顶点表示工程的开始时间，出度为0的顶点表示工程的结束事件。
2.什么是关键路径
从AOE网中源点到汇点的最长路径，具有最大长度的路径叫关键路径。
关键路径是由关键活动构成的，关键路径可能不唯一。
关键路径为源点到汇点的最长路径，这样转变为查找图中最长路径问题。
求解方法：求一个AOE的关键路径→求AOE的关键活动
3.求关键路径的过程
(1) 事件的最早开始和最迟开始时间
事件v的最早开始时间：规定源点事件的最早开始时间为0。定义图中任一事件v的最早开始时间，ee(v)等于x、y、z到v所有路径长度的最大值：
ee(v)=0; //当v为源点时
ee(v)=MAX{ee(x)+a，ee(yy)+b，ee(z)+c} //否则
事件v的最迟开始时间：定义在不影响整个工程进度的前提下，事件v必须发生的时间成为v的最迟开始时间。le(v)应等于ee(y)与v到汇点的最长路径长度之差：
le(v)=ee(v) //当v为汇点时
le(v)=MIN{le(x)-1，le(y)-b，le(z)-c} //否则
(2) 活动的最早开始时间和最迟开始时间
活动a的最早开始时间e(a)指该活动起点x事件的最早开始时间，即：e(a)=ee(x)
活动a的最迟开始时间l(a)指该活动终点y事件的最迟开始时间与该活动所需时间之差，即：l(a)=le(y)-c
(3) 求关键活动
对于每个活动a，求出d(a)=l(a)-e(a)，若d(a)为0，则称活动a为关键活动。
对于关键活动来说，不存在富余时间。