图

图的定义和术语

• 1.图： 图G由顶点集V和关系集E组成,记为: G=(V,E)， V是顶点(元素)的有穷非空集， E是两个顶点之间的关系的集合。
• 2.有向图、弧（有向边）：若图G任意两顶点a,b之间的关系为有 序对,∈E, 则称为从a到 b的一条弧/有向边； 其中： a是的弧尾， b是的弧头； 称该图G是有向图。 例 G1={V1,E1}, V1={A,B,C,D,E} E1={<A,C>,<A,D>,<C,D>,<B,E>,<E,B>}

• 3. 无向图、边（无向边）： 若图G的任意两顶点a,b之间的关系为 无序对(a,b), 则称(a,b)为无向边(边）, 称该图G是无向图。 无向图可简称为图。 (a,b)依附于a和b, (a,b)与a和b相关联 例 G2={V2,E2}, V2={1,2,3,4,5,6}, E2={(1,3),(1,5),(3,5),(4,6)}

• 4. 完全图: 有n个顶点和n(n-1)/2条边的无向图
     
• 5. 有向完全图: 有n个顶点和n(n-1)条弧的有向图。

• 6. 网(Network): 边(弧)上加权(weight)的图。

• 7. 子图： 对图 G=(V,E)和G’ =(V’ ,E’)，若V’是V子集 且 E’ 是E的子集， 则称G’是G的一个子图

• 8. 度： 与顶点x相关联的边(x,y)的数目,称 为x的度， 记作TD(x) 或D(x)， TD(1)=1 TD(2)=3 TD(3)=0

• 9.出度: 以顶点x为弧尾的弧的数目, 称为x的 出度，记作OD(x)。 OD(A)=1 OD(B)=2 OD(C)=0

• 10.入度： 以顶点x为弧头的弧的数目,称为x的 入度，记作ID(x)。 ID(A)=1 ID(B)=1 ID(C)=1 TD(A)=OD(A)+ID(A)=2 TD(B)=OD(B)+ID(B)=3
  
• 11.连通图及连通分量: (无向图G)
  Ø 若从顶点vi到vj有路径,则称vi和vj是连通的。

Ø 若图G中任意两顶点是连通的,则称G是连通图。

若图G’是G的一个极大连通子图,则称G’是G的一个连通分量

• 12.强连通图及强连通分量: (有向图G)
  Ø 若在图G中,每对顶点vi和vj之间, 从vi到vj,且从 vj到vi 都存在路径,则称G是强连通图。

Ø 若图G’是G的一个极大强连通子图,则称G’是G的一个强连通分量。(强连通图的强连通分量是自身)

• 13.生成树: 设G=(V,E),G’ =(V’ ,E’),V=V’ ,若G是连通图,G’是G的一个极小连通子图, 则G’是G的一棵生成树。

图的存储结构

数组表示法/邻接矩阵(顺序+顺序)

顶点数组—用一维数组存储顶点(元素) 邻接矩阵—用二维数组存储顶点(元素)之间的关系(边 或弧)

无向图

有向图

邻接表、逆邻接表(顺序+链式)

（1） 无向图的邻接表 : 为图G的每个顶点建立一个单链表，第i个单链 表中的结点表示依附于顶点vi的边。

若无向图G有n个顶点和e条边，需n个表头结点和2e个表结点。 Ø 无向图G的邻接表，顶点vi的度为第i个单链表的长度。

（2）有向图的邻接表 : 第i个单链表中的表结点，表示以顶点vi为尾的弧 (vi,vj)的弧头。

1. 若有向图G有n个顶点和e条弧，则需n个表头结点和e个表结点。
2. 有向图G的邻接表，顶点vi的出度为第i个单链表的长度。
3. 求顶点vi的入度需遍历全部单链表，统计结点值为i的结点数

（3）有向网的邻接表

（4）有向图的逆邻接表 第i个单链表中的表结点，表示以顶点vi为尾的弧 (vi,vj)的弧头。

1. 若有向图G有n个顶点e条弧，则需n个表头结点和e个表结点。
2. 有向图G的逆邻接表，顶点vi的入度为第i个单链表的长度。
3. 求顶点vi的出度需遍历全部单链表，统计结点值为i的结点数。

有向图的十字链表

将邻接表和逆邻接表合并而成的链接表。

邻接多重表

（无向图的）的另一种链式存储结构

（1）图的一个顶点用一个“头结点”表示， 其中： data域 存储和该顶点相关的信息， firstedge域 存储第一条依附于该顶点的边。

（2）图的一条边或弧用一个“结点”表示。

其中： mark—-标志域，可用以标记该条边是否被搜索过； vi和vj—-该条边依附的两个顶点在图中的位置； vilink—-指向下一条依附于顶点vi的边； vjlink—-指向下一条依附于顶点vj的边。 避免了无向图邻接表的一条边用两个结点。

图的遍历

从图G的某定点vi出发，访问G的每个顶点一次且一次的过程。

网的最小生成树

在网G的各生成树中，其中各边的权之和最小的生 成树称为G的最小生成树

MST性质： 设G=（V，E）是一个连通网，U是V的一个非空子集。 如果边（u,v)是G中所有一端在U中（即u∈U）而另一端在 V-U中（即v∈V-U）具有最小值的一条边，则存在一棵包 含边（u,v)的最小生成树。

普里姆(prim)算法 以选顶点为主

对n个顶点的连通网，初始时， T=（U，TE），U为一 个开始顶点，TE=φ，以后根据MST性质，每次增加一个顶 点和一条边，重复n-1次。Ｕ不断增大，Ｖ－Ｕ不断减小 直到为空。

克鲁斯卡尔（Kruskai)算法，以选边为主

管梅谷破圈法

有向无环图及其应用

一个无环的有向图称为有向无环图（directed acycline graph), 简称DAG图

拓扑排序

• 拓扑排序算法思想：重复下列操作，直到所有顶点输出完。
• （1）在有向图中选一个没有前驱的顶点输出(选择入度为0的顶点)；
• （2）从图中删除该顶点和所有以它为尾的弧(修改其它顶点入度) 。

有回路的有向图不存在拓扑排序

关键路径

AOE网（Activity On Edge）： 是一个带权的有向无环图，其中以顶点表示事件，弧表示活 动，权表示活动持续的时间。 当AOE网用来估算工程的完成时间时，只有一个开始点（入 度为0,称为源点）和一个完成点（出度为0，称为汇点）

AOE网研究的问题： （1） 完成整项工程至少需要多少时间； （2） 哪些活动是影响工程进度的关键。 在AOE网中，部分活动可并行进行，所以完成工程 的最短时间是从开始点到完成点的最长路径长度。路径 长度最长的路径称为关键路径（Critical Path）

(顶点）事件vi的最早发生时间ve(i)：
从开始点到vi的最长路径长度。（ve(v1)=0） 既表示事件vi的最早发生时间，也表示所有以vi为尾的 弧所表示的活动ak的最早发生时间e(k)。(如下例的a7,a8)

• 仅有一个前驱顶点：
• ve(v2)=ve(v1)+6=0+6=6
• ve(v3)=ve(v1)+4=0+6=4
• ve(v4)=ve(v1)+6=0+5=5
  有多个前驱顶点： ve(v5)=max{ve(前驱顶点)+ 前驱活动时间} =max{6+1,4+1,5+5}=10
  完成点（汇点）的ve(vn)为工程完成所需要的时间。

关键路径算法步骤

• （1）从开始点v1出发，令ve(1)=0,按拓朴排序序列求其它各 顶点的最早发生时间 Ve(k)=max{ve(j)+dut()} (vj为以顶点vk为弧头的所有弧的弧尾 对应的顶点集合)
• （2）从完成点vn出发，令vl(n)=ve(n),按逆拓朴排序序列求 其它各顶点的最迟发生时间 Vl(j)=min{vl(k)-dut()} (vk为以顶点vj为弧尾的所有弧的弧头 对应的顶点集合
• （3）求每一项活动ai(vj,vk): e(i)=ve(j) l(i)=vl(k)-dut(ai)

最短路径

• 算法1（Dijkstra算法）： 以每一个顶点为源点，重复执行Dijkstra算法n次， 即可求出每一对顶点之间的最短路径。

假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。这个可以用反证法证明，假设此路径上有一个顶点不在S中，则说明存在一条终点不在S中而长度比此路径短的路径。但是这是不可能的。因为我们按长度递增的顺序来产生各最短路径，所以长度比此路径还短的所有路径均已产生，他们的终点一定在S中。故假设不成立

因此，下一条长度次短的最短路径的长度必是D[j]=Min{D[i] | vi∈V-S}    其中，D[i]或者是弧(v,vi)上的权值，或者是Dk和弧(vk,vi)上的权值之和

• 算法2（Floyd算法）： 算法思想： 假设求Vi到Vj的最短路径，如果从Vi到Vj有弧，则存在 一条长度为arcs[i][j]的路径，该路径不一定是最短路径， 尚需进行n次试探