7.1 图的基本概念
7.1.1 图的定义
图G由顶点集v和边集E组成，记为G=(V,E),其中:
V(G)表示图G中顶点的有限非空集;
E(G)表示图G中顶点之间的关系（边）集合。
若V={v1, v2,…, vn}，则用|V|表示图G中顶点的个数，也称图G的阶，E={(u, v)| u∈V, v∈V}，用|E|表示图G中边的条数。
线性表可以是空表，树可以是空树，但图不可以是空，V一定是非空集
7.1.2 有向图和无向图
7.1.2.1 无向图
若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)，因为(v,w)=(w, v)，其中v、w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v、w相关联。
G2=(V2,E2)
V2={A,B,C,D,E}
E2= {(A, B),(B, D),(B,E),(C, D),(C,E),(D,E)}
7.1.2.2 有向图
若E是有向边(也称弧)的有限集合时，则图G为有向图。
弧是顶点的有序对，记为<v,w>, 其中v、w是顶点，v称为
弧尾，w称为弧头，<v, w>称为从顶点v到顶点w的弧，也称.
v邻接到w，或w邻接自v。<v, w>≠<w, v>
G1= (V1, E1)
V1={A, B, C,D, E}
E1={<A,B>,<A,C>, <A, D>, <A,E>,<B,A>, <B,C>, <B,E>, <C, D>}
7.1.3 路径回路概念
路径:顶点vp到顶点vg之间的一条路径是指顶点序列，Vp,V1,V2,…Vq
回路:第一个顶点和最后一个顶点相同的路径称为回路或环
简单路径:在路径序列中，顶点不重复出现的路径称为简单路径。
简单回路:除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
路径长度:路径上边的数目
点到点的距离:从顶点u出发到顶点v的最短路径若存在，则此路径的长度称为从u到v的距离。
若从u到v根本不存在路径，则记该距离为无穷(∞)。
无向图中，若从顶点v到顶点w有路径存在，则称v和w是连通的
有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的
7.1.4 连通图和强连通图
若无向图中任意两个顶点都是连通的，则称图G为
连通图，否则称为非连通图。
常见考点:
对于n个顶点的无向图G,
若G是连通图，则最少有n-1条边
若G是非连通图，则最多可能有(n-1)(n-2)/2条边
若有向图中任何一对顶点都是强连通的，则称此图为
强连通图。
常见考点:
对于n个顶点的有向图G,
若G是强连通图，则最少有n条边(形成回路)
7.1.5 子图和生成子图
设有两个图G=(V, E)和G’=(V’,E’)，若V’是V的子集，且E’是
E的子集，则称G’是G的子图。
若有满足V(G’) = V(G)的子图G’，则称其为G的生成子图
极大连通子图：子图必须连通，且包含
尽可能多的顶点和边
无向图中的极大连通子图称为连通分量。
连通图的生成树:边尽可能的少，但要保持连通
连通图的生成树是包含图中全部顶点的-一个极小连通子图。
若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
7.1.6 带权图
边的权：在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
带权图/网：边上带有权值的图称为带权图，也称网。
带权路径长度：当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度
7.1.7 树与图的关系
树：不存在回路，且连通的无向图
有向树：一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。
n个顶点的树，必有n-1条边。
常见考点: n个顶点的图，若|E|>n-1,则一定有回路
7.2 图的存储结构
7.2.1 邻接矩阵法
#define MaxVertexNum 100//顶点数目的最大值
typedef struct{
char Vex [MaxVertexNum] ;//顶点表
int Edge [MaxVertexNum] [MaxVertexNum] ;
//邻接矩阵，边表
int vexnum, arcnum;//图的当前顶点数和边数/弧数表示边
} MGraph;
邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)
空间复杂度: O(|V|2) ,只和顶点数相关，和实际的边数无关
适合用于存储稠密图
无向图的邻接矩阵是对称矩阵，可以压缩存储(只存储上三角区/下三角区)
7.2.2 邻接表法(顺序+链式存储)
边结点的数量是2|E|，整体空间复杂度为O(|V| + 2|E|);
如果确定节点编号，图的邻接矩阵表示法唯一，邻接表表示方法不唯一。
7.2.3 十字链表法(存储有向图)
空间复杂度: O(|V|+|E|)
如何找到指定项点的所有出边?顺着绿色线路找
如何找到指定顶点的所有入边?顺着橙色线路找
注意:十字链表只用于存储有向图
7.2.4 邻接多重表(存储无向图)
空间复杂度: O(|V|+|E|)
删除边、删除节点等操作很方便
7.2.5 总结
7.3 图的基本操作
Adjacent(G,x,y):判断图G是否存在边<x, y>或(x, y)。
Neighbors(G,x):列出图G中与结点x邻接的边。
InsertVertex(G,x):在图G中插入顶点x。
DeleteVertex(G,x):从图G中删除顶点x。
AddEdge(G,x,y):若无向边(x, y)或有向边<x, y>不存在，则向图G中添加该边。
RemoveEdge(G,x,y):若无向边(x,y)或有向边<x, y>存在，则从图G中删除该边。
FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
NextNeighbor(G,x,y):假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的T个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
Get_edge_value(G,x,y):获取图G中边(x, y)或<x, y>对应的权值。
Set_edge_value(G,x,y,v):设置图G中边(x, y)或<x, y>对应的权值为v。
7.4 图的遍历策略
7.4.1 广度优先遍历
7.4.1.1 定义
从根节点出发，开始找与他相邻近的所有节点，然后依次逐个找到。尽可能多的找同级相邻的节点。
7.4.1.2 代码实现
bool visited [MAX_VERTEX_NUM];//访问标记数组
//广度优先遍历
void BFS(Graph G,int v){//从顶点v出发，广度优先遍历图G
visit(v);//访问初始顶点v
visited[v]=TRUE;//对v做已访问标记
Enqueue(Q,v);//顶点v入队列Q
while(!isEmpty(Q)){
DeQueue(Q,v);//顶点v出队列
for(w=FirstNeighbor(G,v);w>=0; w=NextNeighbor(G,v,
//检测v所有邻接点
if(!visited[w]){// w为v的尚未访问的邻接顶点
visit(w);//访问顶点w
visited[w]=TRUE;//对w做已访问标记
EnQueue(Q,w);//顶点w入队列
}
}// while
}
从顶点1出发得到的广度优先遍历序列:
1，2，5，6，3，7，4，8
从顶点3出发得到的广度优先遍历序列:
3，4，6，7，8，2，1，5
同一个图的邻接矩阵表示方式唯一，因此广度优先遍历序列唯一
同一个图邻接表表示方式不唯一，因此广度优先遍历序列不唯一
对于一个无向图来说，调用BFS函数的次数等于图的连通分量的个数。
如果是非连通图，则无法遍历完所有结点。
7.4.1.3 算法分析
空间复杂度：
最坏情况，辅助队列大小为O(|V|)
时间复杂度：
邻接矩阵存储的图:
访问|V|个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|))的时间，而总共有|V|个顶点
时间复杂度=O(|V2|)
邻接表存储的图：
访问|V|个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(E)的时间,
时间复杂度= O(|V+E|)
7.4.2 深度优先遍历
7.4.2.1 定义
==树的深度优先遍历:==从根节点出发，能往更深处走就尽量往深处走。每当访问一个结点的时候，要检查是否还有与当前结点相邻的且没有被访问过的结点，如果有的话就往下一层钻。图的深度优先遍历类似于树的先根遍历。
7.4.2.2 实现代码
bool visited [MAX__VERTEX__NUM]; //访问标记数组
void DFS(Graph G,int v){//从顶点v出发，深度优先遍历图G
visit(v);//访问顶点v
visited [v]=TRUE;//设已访问标记
for(w=FirstNeighbor(G,v);W>=0;w=NextNeighor(G,V,W))
if(!visited[w] ){/ /w为u的尚未访问的邻接顶点
DFS(G,W);
} //if
}
从2出发的深度遍历序列: 2, 1, 5, 6, 3, 4, 7, 8
7.4.2.3 复杂度分析
空间复杂度：
来自函数调用栈，最坏情况，递归深度为O(|V|)
最好情况，O(1);
时间复杂度：
时间复杂度=访问各节点所需时间+探索各条边所需时间
邻接矩阵存储的图:
访问|V|个顶点需要O(|V|)的时间
查找每个顶点的邻接点都需要O(|V|))的时间，而总共有|V|个顶点
时间复杂度=O(|V2|)
邻接表存储的图：
访问|V|个顶点需要O(|V|)的时间
查找各个顶点的邻接点共需要O(E)的时间,
时间复杂度= O(|V+E|)
7.4.3 图的连通性
对无向图进行BFS/DFS遍历
调用BFS/DFS函数的次数= =连通分量数
对于连通图，只需调用1次BFS/DFS
对有向图进行BFS/DFS遍历
调用BFS/DFS函数的次数要具体问题具体分析
若起始顶点到其他各顶点都有路径，则只需调用1次
BFS/DFS函数
对于强连通图，从任一结点出发都只需调用1次BFS/DFS
7.5 图的应用
7.5.1 最小生成树
Prim算法：
从某一个顶点开始构建生成树;每次将代价最小的新顶点纳入生成树，直到所有顶点都纳入为止。
时间复杂度: O(|V|2)
适合用于边稠密图
Kruskal算法：
每次选择一条权值最小的边，使这条边的两头连通(原本已经连通的就不选)；直到所有结点都连通；
时间复杂度: O(|El|log2|E|)
适合用于边稀疏图
7.5.2 最短路径问题
7.5.2.1 单源最短路径问题
BFS求无权图的单源最短路径
Dijkstra算法求单源最短路径问题
Dijkstra算法不适用于有负权值的带权图
Floyd算法求最短路径
Floyd算法:求出每一对顶点之间的最短路径
使用动态规划思想，将问题的求解分为多个阶段
对于n个顶点的图G，求任意一对顶点Vi到Vj之间的最短路径可分为如下几个阶段:
#初始:不允许在其他顶点中转，最短路径是?
#0︰若允许在V0中转，最短路径是?
#1∶若允许在V0，V1中转，最短路径是?
#2 : 若允许在V0，V1，V2中转，最短路径是?..
#n-1∶若允许在V0，V1，V2…Vn-1中转，最短路径是?
7.5.3 拓扑排序
AOV网:用顶点表示活动的网:
用DAG图(有向无环图)表示一个工程。顶点表示活动，有向边<Vi,Vj>表示活动Vi必须先于活动Vj进行
拓扑排序:在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序:
①每个顶点出现且只出现一次。
②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。
或定义为:拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点A到顶点B的路径，则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。
拓扑排序的实现:
①从AOV网中选择一个没有前驱(入度为0) 的顶点并输出。
②从网中删除该顶点和所有以它为起点的有向边。
③重复①和②直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。
网中不存在无前驱的顶点为止表示存在回路
逆拓扑排序的实现：
对一个AOV网，如果采用下列步骤进行排序，则称之为逆拓扑排序:
①从AOV网中选择一个没有后继(出度为0)的顶点并输出。
②从网中删除该顶点和所有以它为终点的有向边。
③重复①和②直到当前的AOV网为空。
7.5.4 关键路径
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销(如完成活动所需的时间)，称之为用边表示活动的网络，简称AOE网(Activity On Edge NetWork)
AOE网具有以下两个性质:
①只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始;
②只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。另外，有些活动是可以并行进行的.
求解步骤：
①求所有事件的最早发生时间ve( )
②求所有事件的最迟发生时间vl( )
③求所有活动的最早发生时间e( )
④求所有活动的最迟发生时间l()
⑤求所有活动的时间余量d()
方法：
①按拓扑排序序列，依次求各个顶点的ve(k):
ve(源点)= 0
ve(k) = Max{ve(j) + Weight(vk, vj)}，vj为vk 的任意前驱
②按逆拓扑排序序列，依次求各个顶点的vl(k):
vl(汇点)= ve(汇点)
vl(k) = Min{vl(k) - Weight(vk, vj)}，vj为vk的任意后继
③若边<vk, vj>表示活动ai,则有e(i) = ve(k)
④若边<vk, vj>表示活动ai,则有l(i) = vl(j) - Weight(vk, vj)
⑤d(i)= l(i) -e(i)
特性：
若关键活动耗时增加，则整个工程的工期将增长
缩短关键活动的时间，可以缩短整个工程的工期
当缩短到一定程度时，关键活动可能会变成非关键活动
可能有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。