# 图的定义

图是由顶点集V和顶点间的关系集合E(边的集合)组成的一种数据结构,可以用二元组定义为:G=(V,E)

# 基本术语

  1. 有向图和无向图
    在图中,若用剪头标明了边是有方向性的,称这样的图为有向图,否则称无向图
  2. 完全图、稠密图、稀疏图
    具有n个顶点,n(n-1)/2条边的图,称为完全无向图
    具有n个顶点,n(n-1)条弧的有向图,称为完全有向图。
    完全无向图和完全有向图都称为完全图。
    对于一般无向图,顶点数为n,边数为e,则0<=e<=n(n-1)/2
    对于一般有向图,项点数为n,弧数为e,则0<=e<=n(n-1)
    当一个图接近完全图时,则称它为稠密图,相反,当一个图含有较少的边或者弧则称为稀疏图
  3. 度、入度、出度
    在图中,一个顶点依附的边或弧的数目,称为该顶点的度。
    在有向图中,一个顶点依附的弧头数目,称为顶点的入度,一个顶点依附的弧尾数目,称为该顶点的出度,某个顶点的入度和出度这和称为该顶点的度。

# 图的遍历

两条遍历图的算法:深度优先搜索、广度优先搜索

# 深度优先搜索

深度优先搜索采用的思想🔖:类似于树的先序遍历(根左右)

  1. 首先访问顶点i,并将其访问标记置为访问过,即 visited[i]=1;
  2. 然后搜索与顶点i有边相连的下一个顶点j,若j未被访问过则访问它,并将j的访问标记置为已访问过,visited[j]=1,然后从j开始重复此过程,若j已访问,再看与i有边连的其它顶点;
  3. 若与i有边相连的顶点都被访问过,则退回到前一个访问顶点并重复刚才过程,直到图中所有顶点都被访问过为止。

# 广度优先搜索

广度优先搜索采用的思想🔖:队列

  1. 开始时要将其置空
  2. 在每访问一个顶点时,要将其入队
  3. 在访问一个顶点的所有后继时,要将其出队。
  4. 若队列为空时,说明每个访问过的顶点的所有后继均已访问完毕,因而本次遍历可以结束。若此时还有未访问的顶点,需要另选起点进行遍历。

# 图的应用(四大应用)

# 👉应用1️⃣:生成树

在图论中,常常将树定义为一个无回路的连通图
两种遍历的算法可以获得生成树:
深度优先(搜索)生成树、广度优先(搜索)生成树
在一般情况下,图中的每条边若给定了权,这时,我们所关心的不是生成树,而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小,称为最小生成树。

# 👉应用2️⃣:最小生成树

# 最小生成树的两种方法

第一种最小生成树:普里姆算法(prim)
第二种最小生成树:克鲁斯卡尔算法(kruskal)

# 1️⃣最小生成树算法:普里姆算法(prim)

普里姆算法思想:在图中任取一个顶点K作为开始点,令U={k},W=V-U,其中V为所有顶点集,然后找一个顶点在U中,另一个顶点在W中的边中最短的一条,找到后,将该边作为最小生成树的树边保存起来,并将该边顶点全部加入U集合中,并从W中删去这些顶点,然后重新调整U中顶点到W中顶点的距离,使之保持最小,再重复此过程直到W为空集为止。

undirected-graph

例: V={1,2,3,4,5,6} 则 U={} W={1,2,3,4,5,6}
过程:

u w
{1} {2,3,4,5,6}
{1,3} {2,4,5,6}
{1,3,6} {2,4,5}
{1,3,6,4} {2,5}
{1,3,6,4,2} {5}
{1,3,6,4,2,5} {}
# 2️⃣最小生成树算法:克鲁斯卡尔算法(kruskal)

克鲁期卡尔算法的基本思想是:将图中所有边按权值递增顺序排列,依次选定取权值最小的边,但要求后面选 取的边不能与前面选取的边构成回路,若构成回路,则放弃该条边,再去选后面权值较大的边,n个顶点的图中,选够n-1条边即可。

undirected-graph 克鲁斯卡尔最小生成树过程 kruskal

# 👉应用3️⃣:最短路径

讨论最短路径的方法有两种:单源点最短路径、所有顶点对的最短路径

# 单源点最短路径:迪杰斯特拉(Dijkstra)算法

定义:单源点最短路径是指:给定一个出发点(单源点)和一个有向网G=(V,E),求出源点到其它各顶点之间的最短路径。
问题:怎样求出单源点的最短路径呢?
解答:将源点到终点的所有路径都列出来,然后在里面选最短的一条即可。但是这样做用手工方式可以,当路径特别多,显的特别麻烦,并且没有什么规律,不能用计算机算法实现。
方法: 迪杰斯特拉(Dijkstra)在做了大量观察后,首先提出了按路长度递增序产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法
算法思想:设V为网中所有顶点集合,设置并逐步扩充一个集合S,存放已求出其最短路径的顶点,则尚未确定最短路径的顶点集合V-S:按路径长度递增的顺序逐个把V-S中的顶点加到S中,直到S中包含全部顶点,而V-S为空。通俗的讲就是每次在全部中选最小值放进去,再对比再找最小值。

dijkstra
终点 从V0到各终点的最短路径
i=1 i=2 i=3 i=4 i=5
V1
V210(V0,V2)
V360(V0,V2,V3)50(V0,V4,V3)
V430(V0,V4)30(V0,V4)
V5100(V0,V5)100(V0,V5)90(V0,V4,V5)60(V0,V4,V3,V5)
VKV2V4V3V5
PathV0-V2V0-V4V0-V4-V3V0-V4-V3-V5
S{V0,V2}{V0,V2,V4}{V0,V2,V4,V3}{V0,V2,V4,V3,V5}

# 所有顶点对之间的最短路径:Floyd算法

所有顶点对之间的最短路径是指:对于给定的有向网G=(V,E),要对G中任意对顶点有序对V、W(V<>W),找出V到W的最短距离和W到V的最短距离。
解决此问题有效的方法:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次,可求得每一对顶点之间的最短路径,总的时间复杂度为O(n^3),效率太低,于是出现了Floyd算法。
Floyd算法思想:
将V1到Vj的最短路径长度初始化,即D[i][j]为项点i到j的路径长度,然后进行n次比较和更新。通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。

floyd

floyd 在滑块法中就是等于0的时候 那一行一列不动。看其它的最小的是哪个然后更新。上面的矩阵更新了,下面的矩阵也要跟着更新。从0到3 依次更新,每次更新时候加入一个顶点。然后看看整个矩阵有没有新的最短路径生成。有的话就更新没有的话就不更新。

# 👉应用4️⃣:拓扑排序

通常我们把计划、施工过程、生产流程等都当成一个工程,一个大工程常常被划分成许多较小的子工程,这些子工程称为活动,这些活动完成时,整个工程也就完成了。

# AOV网介绍

在这种有向图中,顶点表示活动,有向边表示活动的优先关系,这有向图叫做顶点表示活动的网络(Actrie On Vertices)简称AOV网。
在AOV网中,<i,j>有向边表示i活动应先于j活动开始,即i活动必须完成后,j活动才可以列始,并称i为j的直接前驱,j为i的直接后继。这种前驱与后继的关系有传递性,此外,任何活动i不能以它自己作为自己的前驱或者后继,这叫做反自反性。从前驱和后继的传递性和反自反性来看,AOV网中不能出现有向回路(或称有向环),对工程而言,将无法进行:对程序流程而言,将出现死循环。

拓扑排序的步骤:

  1. 在AOV网中选一个入度为0的顶点且输出
  2. 在AOV网中删除此顶点及该顶点发出来的所有有向边
  3. 重复1,2两步,直到AOV网中所有顶点都被输出或网中不存在入度为0的顶点。

# 👉应用5️⃣:关键路径

若以带权有向图的顶点代表事件(event)或工程进展状态,用弧表示活动,弧上的权值表示完成该活动所需要的时间,则这样的带权有向图称为AOE网(Activity On Edge Network)
(1)只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始。
(2)只有在进入某点的各有向边所代表的活动都已结束,该顶点所代表的时事件才能发生。
关键路径(临界路径):在AOE网络中从源点到汇点(结束顶点)的最长路径。关键路径上的活动为关键活动。