1. 图的定义和基本术语
- 线性结构中，元素仅有线性关系，每个元素只有一个直接前驱和直接后继；
- 树形结构中，数据元素（结点）之间有着明显的层次关系，每层上的元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；
- 图形结构中，数据元素（顶点）之间具有任意关系，图中任意两个数据元素之间都可能相关。
(1) 图的定义
图是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为: G（V，E）， 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
无向边：若顶点Vi到Vj之间的边没有方向，则称这条边为无向边，用无序偶对(Vi，Vj) 来表示。如下左图，G= (V1,{E1})，其中顶点集合V1={A，B，C，D}; 边集合E1={ (A,B) ，（B,C），(C,D)， (D,A) , (A,C) } 。圆括号有向边：若从顶点Vi 到Vj的边有方向，则称这条边为有向边，也称为弧。用有序偶〈Vi,Vj>来表示， Vi称为弧尾， Vj称为弧头。 如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。连接顶点A到D的有向边就是弧，A是弧尾，D是弧头，<A, D>表示弧，注意不能写成<D， A>。如下右图，G= (V2,{E2})，其中顶点集合V2={A，B，C，D}; 弧集合E2={<A，D>，<B，A>，<C，A>，<B，C>}。尖括号
(2) 图的基本术语
- 子图： 假设有两个图G= (V，{E})和G'= (V'，{E'})，如果V'是V的子集，且E'是E的子集，则称G'为G的子图。如下图带底纹的图均为左侧无向图与有向图的子图。
- 无向完全图和有向完全能图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n (n-1) 条边。
- 稀疏图和稠密图：有很少条边或弧的图称为稀疏图，反之称为稠密图，这里的概念是相对而言的。
- 权和网：有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。如下图就是一张带权的图，即标识中国四大城市的直线距离的网，此图中的权就是两地的距离。
- 邻接点：对于无向图G= (V,{E})， 如果边(v,v')属于E， 则称顶点v和v‘互为邻接点，即v和v'相邻接、边(v,v')依附于顶点v和v'，或者说(v,v')与顶点v和v'相关联。
- 度、入度和出度：点v的度是和v相关联的边的数目，记为TD(v)。如上图左侧上方的无向图，顶点A与B互为邻接点，边(A，B) 依附于顶点A 与B 上，顶点A 的度为3。而此图的边数是5，各个顶点度的和=3+2+3+2=10，推敲后发现，边数其实就是各顶点度数和的一半，多出的一半是因为重复两次计数。
对于有向图G= (V,{E})，如果弧<v,v'>属于E，则称顶点v邻接到顶点v'，顶点v'邻接自顶点v的弧<v,v'>和顶点v， v'相关联。以顶点v为头的弧的数自称为v的入度
，记为ID (v); 以v为尾的弧的数目称为v的出度，记为OD (v); 顶点v的度为TD(v) =ID(v) +OD (v)。上图 左侧下方的有向图，顶点A的入度是2 (从B到A的弧，从C到A的弧)，出度是1 (从A到D的弧)，所以顶点A 的度为2+1=3。此有向图的弧有4 条，而各顶点的出度和=1+2+1+0=4，各顶点的入度和=2+0+1+1=4。路径和路径的长度：从顶点v 到顶点v'的路径是一个顶点序列。路径的长度是路径上的边或弧的数目。有向图的路径也是有向的。
8.回路或环：第一个顶点到最后一个顶点相同的路径称为回路或环。
9.简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。如下图，左侧的环因第一个顶点和最后一个顶点都是B，且C、 D、 A没有重复出现，因此是一个简单环。 而右侧的环，由于顶点C的重复，它就不是简单环。
10.连通、连通图和连通分量：在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。 如果对于图中任意两个顶点vi、vj ∈E， vi，和vj都是连通的，则称G是连通图。 下图的图1，它的顶点A到顶点B、 C、 D都是连通的，但显然顶点A与顶点E或F就无路径，因此不能算是连通图。而图2，顶点A、 B、 C、D相互都是连通的，所以它本身是连通图。
无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调:
- 要是子图；
- 子图要是连通的；
- 连通子图含有极大顶点数；
- 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
上图中，图1是一个无向非连通图。 但是有两个连通分量，即图2和图3。而图4，尽管是图1的子图，但是它却不满足连通子图的极大顶点数(图2满足)。 因此它不是图1的无向图的连通分量。
- 强连通图和强分量：在有向图G中，如果对于每一对vi，vj属于E，vi不等于vj，从vi到vj和vj 到vi都有路径，则称G是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。
连通图的生成树：一个极小的连通子图， 它含有图中全部的n 个顶点，但只有足以构成一棵树的n-1条边。比如下图的图1是一普通图，但显然它不是生成树，当去掉两条构成环的边后，比如图2 或图3，就满足n个顶点n-1条边且连通的定义了， 它们都是一棵生成树。从这里也可知道，如果一个图有n 个顶点和小于n-1条边，则是非连通图，如果多于n-1 边条，必定构成一个环， 因为这条边使得它依附的那两个顶点之间有了第二条路径。比如图2 和图3，随便加哪两顶点的边都将构成环。 不过有n-1条边并不一定是生成树，比如图4。
有向树和生成森林：如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向树。对有向树的理解比较容易，所谓入度为0其实就相当于树中的根结点， 其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干棵有向树组成， 含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。 如下图的图1 是一棵有向图。去掉一些弧后，它可以分解为两棵有向树，如图2和图3，这两棵就是图1有向图的生成森林。
2.图的存储结构
(1)邻接矩阵
图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。设图G有n个顶点，则邻接矩阵是一个nxn的方阵，定义为:
如下无向图，
如下有向图
我们知道，每条边上带有权的图叫做网，如果要将这些权值保存下来，可以采用权值代替矩阵中的0、1，权值不存在的元素之间用∞表示，如下图，左图是一个有向网图，右图就是它的邻接矩阵。
邻接矩阵结构：
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MVNum 100 /* 最大顶点数，应由用户定义 */
#define MaxInt 65535 //表示极大值，即∞
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char VerTexType; /* 顶点类型应由用户定义 */
typedef int ArcType; /* 边上的权值类型应由用户定义 */
typedef struct{
VertexType vexs[MVNum]; /* 顶点表 */
EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
int vexnum, arcnum; /* 图中当前的顶点数和边数 */
}AMGraph;
1. 采用邻接矩阵表示法创建无向网
(1) 输入总顶点数和总边数。
(2) 依次输入点的信息存入顶点表中。
(3) 初始化邻接矩阵，使每个权值初始化为极大值。
(4)构造邻接矩阵。依次输入每条边依附的顶点和其权值。确定两个顶点在图中的位置之后，使相应的边赋予相应的权值，同时使其堆成边赋予相同的权值。
该算法的时间复杂度为O(n*n)
Status CreateUDN(AMGraph &G)
{//采用邻接矩阵表示法，创建无向网G
cin>>G.vexnum>>G.arcnum; //输入总顶点数和总边
for(i=0;i<G.vexnum;++i)
{
cin>>G.vexs[i];//依次输入点的信息
}
for(=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j] = MaxInt;//初始化邻接矩阵，边的权值均置为最大值MaxInt
for(k=0;k<G.racnum;++k) //构造邻接矩阵
{
cin>>v1>>v2>>w;//输入一条边依附的顶点及权值
i=LocateVex(G,v1);j=LocateVex(G,v2);que'd
G.arcs[i][j] = w;
G.arcs[j][i] = w;
}
return OK;
}
int LocateVex(AMGraph G,VerTextType u)
{
int i;
for(i=0;i<G.vexnum;i++)
{
if( u == G.vexs[i]) return i;
}
return -1;
}
2.邻接矩阵表示法的优缺点
优点：
（1） 便于判断两个顶点之间是否有 边，即根据A[i][j] = 0或1来判断。
（2） 便于 计算各顶点的度。对于无向图，邻接矩阵的第i行元素之和就是顶点i的度。对于有向图，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度。
缺点：
（1） 不便于增加删除顶点。
（2） 空间复杂度高。如果是有向图，n个顶点需要nn个单元存储边。如果无向图，其邻接矩阵是对称的，所以对规模较大的邻接矩阵可以采用压缩存储的方法，仅存储下三角元素，这样需要n(n-1)/2个单元。无论哪种存储方式，邻接矩阵表示法的空间复杂度均为0(nn)
(2)邻接表
数组与链表相结合的存储方法称为邻接表。
1.图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点vi 的边表，有向图则称为顶点vi作为弧尾的出边表。
如图是一个无向图的连接表结构，有向图则类似。
对于带权值的网图，可以在边表结点定义中再增加一个weight 的数据域，存储权值信息即可，如下图所示。
图的邻接表存储表示
#define MVNum 100 //最大顶点数
typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int OtherType; /* 边上的权值类型应由用户定义 */
typedef struct ArcNode /* 边表结点 */
{
int adjvex; /* 邻接点域,存储该顶点对应的下标 */
OtherType info; /* 用于存储权值,对于非网图可以不需要 */
struct ArcNode *next; /* 链域,指向下一个邻接点 */
}ArcNode;
typedef struct VNode /* 顶点表结点 */
{
VertexType data; /* 顶点域,存储顶点信息 */
ArcNode *firstedge;/* 指向第一条依附顶点的边指针 */
}VNode, AdjList[MVNum];
typedef struct{
AdjList vertices;
int vexnum,arcnum; /* 图中当前顶点数和边数 */
}ALGraph;
1.采用邻接表表示法创建无向图
(1)输入总顶点数和总边数
(2)依次输入点的信息存入顶点表中，使每个表头结点的指针域初始化为NULL。
(3) 创建邻接表。依次输入每条边依附的两个顶点，确定这两个顶点的序号i和j之后，将此边结点分别插入vi 和vj对应的两个链表的头部。
该算法的时间复杂度为O（n+e）
Status CreateUDG(ALGraph &G)
{
cin>>G.vexnum>>G.racnum;//输入总顶点数，总边数
for(i=0;i<G.vexnum;i++)//输入各点，构造表头结点表
{
cin>>G.vertices[i].data;//输入顶点值
G.vertices[i].firstarc = NULL；//初始化表头结点的指针域为NULL
}
for(k=0k<G.arcnum;k++)//输入各边，构造邻接表
{
cin>>v1>>v2;
i = LocateVex(G,v1);j=LocateVex(G,v2);//确定v1和v2在G中位置，即顶点G.vertices中的序号
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->adjvex = i;
p2->nextarc = G.vertices[j].firstarc;G.vertices[j].firstarc=p2;
}
return OK;
}
2. 邻接表表示法的优缺点
优点：
（1） 便于增加和删除结点。
（2） 便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O(n+e)。
（3）空间效率高。对于一个具有n个顶点e条边的图G，若图G是无向图，则在邻接表表示中有n个顶点表结点和2n个边表结点。若G是有向图，则在它的邻接表表示或逆邻接表表示中均有n个顶点表结点和e个边表结点。因此，邻接表的空间复杂度为O(n+e)。
缺点：
（1） 不便于判断顶点之间是否有边，要判断vi 和vj之间是否有边，就需扫描第i个边表，最换情况下要耗费O(n)时间。
（2） 不便于计算有向图各个顶点的度。
3. 图的遍历
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历。
（1） 深度优先遍历
深度优先遍历类似于数的先序遍历，是树的先序遍历的推广。
- 从图中某个顶点v出发，访问v。
- 找到刚访问过得顶点的第一个未被访问的邻接点，访问该顶点。以该顶点为新顶点，重复此步骤，直至刚访问的顶点没有未被访问的邻接点为止。
- 返回前一个访问过得且扔有未被访问的邻接点的顶点，找到该顶点的下一个未被访问的邻接点，访问该顶点。
重复步骤2，3，直至图中所有顶点都被访问过。
1. 深度优先遍历算法的实现
为了在遍历过程中便于区分顶点是否已经被访问，需附设访问标志组visited[i]n],其初值为false，一旦某个顶点被访问，则其相应的分量置为true。
深度优先遍历连通图
- 从图中某个顶点v出发，访问v，并置visited[v]的值为true。
- 依次检查v 的所有邻接点w，如果visited[w]的值为false，再从w出发进行递归遍历，直至图中所有顶点都被访问过。
bool visited[MVNum];//访问标志数组，其初值为false
void DFS(Graph G,int v)
{//从v个顶点出发递归地深度优先遍历图
cout<<v;visited[v]=true;//访问第v个顶点，并置访问标志数组相应分量值为true
for(w=FirstAdjVex(G,v);w>0;w=NextAdjVex(G,v,w))
//依次检查v的所有邻接点w，FirstAdjVex(G,v)表示v第一个邻接点
//NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w>0表示有邻接点。
if(!visited[w]) DFS(G,w);//对于v的尚未访问的邻接顶点w递归调用DFS
}
深度优先遍历非连通图
void DFSTraverse(Graph G)
{
for(v=0;v<G.vexnum;v++) visited[v] = false; //访问标志数组初始化
for(v=0;v<G.vexnum;v++) if(!visited[v]) DFS(G,v);//对尚未访问的顶点调用DFS
}
采用邻接矩阵表示图的深度优先遍历
void DFS_AM(AMGraph G,int v)
{//图G为邻接矩阵类型，从v个顶点出发深度优先遍历图G
cout<<v;visited[v] = true; //访问第v个顶点，并置访问标志数组相应的分量为true
for(w=0;w<G.vexnum;w++) //一次检查邻接矩阵v所在的行
{
if((G.arcs[v][w] !=0)&& (!visited[w])) DFS_AM(G,w);
//G.arcs[v][w] != 0 表示w是v的邻接点，如果w未被访问，则递归调用DFS_AM
}
}
采用邻接表表示图的深度优先遍历
void DFS_AL(ALGraph G ,int v)
{//图G为邻接表类型，从v个顶点出发的深度优先遍历图
cout <<v;visited[v]=true;
p= G.vertices[v].firstarc;//p指向v的边链表的第一个结点
while(P!=NULL)//边结点非空
{
w = p->adjvex;表示w是v 的邻接点
if(!visited[w]) DFS_AL(G,w);//如果w未被访问，则递归调用DFS_AL
p=p->nexttrac;//p指向下一个边结点
}
}
(2)广度优先遍历
图的广度优先遍历就类似于树的层序遍历。
- 从图中某个顶点v出发，访问v。
- 依次访问v的各个未被访问过得邻接点。
分别从这些邻接点出发依次访问他们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问。重复步骤3，直至图中所有已被访问的顶点的邻接点都被访问到。
1.广度优先遍历连通图
- 从图中某个顶点v出发，访问v，并置visited[v]的值为true，然后将v进队。
- 只要队列不为空，则重复下述操作：
- 队头顶点u出队。
- 依次检查u的所有邻接点w，如果visited[w]的值为false，则访问w,并置visited[w]的值为true。然后将w进队。
void BFS(Graph G,int v)
{
cout<<v;visited[v] =true; //访问第v个顶点，并置访问标志数组相应分量值为true
InitQueue(Q);//辅助队列Q初始化，置空
EnQueue(Q,v);//v进队
while(!QueueEmpty(Q))//队列非空
{
DeQueue(Q,u);
for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w))
{//依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接点
//NextAdjVex(G,u,w)表示u相对于w的下一个邻接点，w>=0表示存在邻接点
if(!visited[w])//w为u的尚未访问的邻接顶点
{
cout<<w;visited[w]=true;//访问w
EnQueue(Q,w);//w进队
}
}
}
}
4. 图的应用
(1) 最小生成树
如下图是个带权值的网结构图。要用最小的成本将所有元素连接起来，即n个顶点，用n-1条边把连通图连接起来，并且使得权值的和最小。定义：把构造连通网的最小代价生成树称为最小生成树。这里介绍两种经典算法。
1. 普利姆（Prim）算法
假设N=(V,E)是连通图，TE是N上的最小生成树中边的集合。
- U={u0}(u0∈V)， TE={ }。
- 在所有u∈U，v∈V-U的边(u，v)∈E 中找一条代价(权值)最小的边(u0，v0) 并入集合TE，同时v0并入U。
重复2，直至U=V为止。
此时TE中必有n-1条边，则T= (V,{TE}) 为N的最小生成树。
算法步骤：
为实现这个算法需附设一个辅助数组closedge,以记录从U到V-U具有最小权值的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量closedge[i-1]，他包含2个域：lowcost和adjvex,其中lowcost存储最小边上的权值，adjvex存储最小边在U中的那个顶点。显然closedge[i-1].lowcost = Min{cost(u,vi)|u∈U},其中cost(u,v)表示赋予边（u,v）的权。
struct
{
VerTextType adjvex;//最小边在U中的那个顶点
ArcType lowcost;//最小边上的权值
}closedge[MVNum];
- 首先将初始顶点u加入U中，对于其余的每一个顶点vj,将closedeg[j]均初始化为到u的边信息。
- 循环n-1次，做如下处理：
- 从各组边closedeg中选出最小边closedge[k],输出此边。
- 将k加入U中。
- 更新剩余的每组最小边信息closedeg[j],对于V-U中的边，新增加一条从k到j的边，如果新边的权值比closedeg[j].lowcost小，则将closedge[j].lowcost更新为新边的权值。
void MiniSpanTree_Prim(AMGraph G,VerTexType u)
{//无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树，输出T的各条边
k = LocateVex(G,u);//k为顶点u的下标
for(j=0 ;j<G.vexnum;++j)//对于V-U的每一个顶点vj,初始化closedge[j]
if (j!=k) closedge[j] = {u,G.arcs[k][j]};//{adjvex,lowcost}
closedeg[k].lowcost = 0;//初始，U={u}
for(i=1;i<G.vexnum;++i)
{//选择其余n-1个顶点，生成n-1条边（n = G.vexnum）
k= Min(colsedge);
//求出T的下一个结点，第k个顶点，closedge[k]中存有当前最小边
u0 = closedge[k].adjvex;//u0为最小边的一个顶点，u0 ∈U
v0 = G.vexs[k];//v0为最小边的另一个顶点，v0∈V-U
cout<<u0<<v0;//输出当前最小边（u0,v0）
closedge[k].lowcost = 0;//第k个顶点并入U集
for(j=0;j<G.vexnum;++i)
if(G.arcs[k][j] < closedge[j].lowcost)//新顶点并入U后重新选择最小边
colsedge[j] = {G.vexs[k],G.arcs[k][j]};
}
}
2. 克鲁斯卡算法
假设连通网N=(V,E),将N中的边按权值从小到大的顺序排列。
- 初始状态为只有n个顶点而无边的非连通图T={V，{ }}，图中每个顶点自成一个连通分量。
- 在E 中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中(即不形成回路)，否则舍去此边而选择下一条代价最小的边。
重复2，直至T中所有顶点都在同一个连通分量上为止。
算法的实现要引入以下辅助的数据结构。
- 结构体数组Edge:存储边的信息，包括边的两个顶点信息和权值。
struct
{
VerTexType Head;//边的始点
VerTexType Tail;//边的终点
ArcType lowcost; // 边上的权值
}Edge[arcnum]
- Vexset[i]:标识各个顶点所属的连通分量。对每个顶点vi∈V ,在辅助数组存在一个相应元素Vexset[i]表示该顶点所在连通分量。初始时Vexset[i],表示各个顶点自成一个连通分量。
int Vexset[Mvnum];
算法步骤：
- 将数组Edge中的元素按权值从小到大排序。
- 依次查看数组Edge中的边，循环执行以下操作：
- 依次从排序好的数组Edge中选出一条边（U1,U2）
- 在Vexset中分别查找v1和v2 所在的连通分量vs1 和vs2，并进行判断：
*如果vs1 和vs2不等，表明所选的两个顶点分属不同的连通分量，输出此边，并合并vs1 和vs2两个连通分量。
*如果vs1 和vs2相等，表明所选的两个顶点属于同一个连通分量，舍去此边而选择下一条权值最小的边。
void MiniSpanTree_Kruskal(MGraph G)
{//无向网以邻接矩阵形式存储，构造G的最小数T，输出T的各条边
sort(Edge);//将数组Edge中的元素按权值从小到大排序
for(i=0;i<G.vexnum;i++)//辅助数组，表示各个顶点自成一个连通分量
Vexset[i] = i;
for(i=0;i<G.arcnum;i++)//依次查看数组Edge中的边
{
v1 = LocateVex(G,Edge[i].Head);//v1为边的始点Head的下标
v2 = LocateVex(G,Edge[i].Tail);//v2为边的终点Tail的下标
vs1 = Vexset[v1];//获取边Edge[i]的始点所在的连通分量vs1
vs2 = Vexset[v2];//获取边Edge[i]的终点所在的连通分量vs2
if(vs1 != vs2)//边的两个顶点分属不同的连通分量
{
cout << Edge[i].Head<<Edge[i].Tail;//输出此边
for(j=0 ; j<G.vexnum;j++)//合并vs1 vs2两个分量，即两个集合统一编号
if(Vexset[j] == vs2) Vexset[j] =vs1;//集合编号为vs2的都改为vs1
}
}
}
(2) 最短路径
对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。关于最短路径主要有两种算法，迪杰斯特拉(Dijkstra) 算法和弗洛伊德(Floyd) 算法。
1. 迪杰斯特拉算法
从某个源点到其余各顶点的最短路径
对于网N=（V，E），将N中的顶点分成两组：
第一组S：已求出的最短路径的终点集合（初始时只包含源点v0）。
第二组V-S：尚未求出最短路径的终点集合（初始时V-{v0}）。
算法将各项顶点与v0 间最短路径长度递增的次序，逐个将集合V-S的顶点加入集合S中去。在这个过程中，总保持从v0到集合S中各顶点的路径长度始终不大于到集合V-S中各顶点x 的路径。
算法的实现要引入以下辅助数据结构
- 一位数组S[i]:记录从源点v0到终点vi是否已被确定最短路径长度，true表示确定，false表示尚未确定。
- 一位数组Path[i]：记录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号。其初始值为：如果从v0到vi有弧，则Path[i]为v0,否则为-1。
-
一位数组D[i]:记录从源点v0到终点vi的当前最短路径长度。其初始值为：如果从v0到vi有弧，则D[i]为弧上的权值，否则为∞。
显然，长度最短的一条最短路径必为（v0,vk），满足以下条件：
D[k] = Min{D[i]|vi∈V-S}
求得顶点vk的最短路径后，将其加入到第一组顶点集S中。
每当加入一个新的顶点到顶点集S，对第二组剩余的各个顶点而言，多一个中转顶点，从而多一个中转路径，所以要对第二组剩余的各个顶点的最短路径长度进行更新。
原来v0到vi的最短路径长度为D[i],加入k作为中间顶点的中转路径长度为：D[k]+Garcs[k][i],若D[k]+Garcs[k][i]<D[i],则用D[k]+Garcs[k][i]取代D[i]。
更新后，再选择数组D中值最小的顶点加入到第一组顶点集S中，如此进行下去，直至图中所有顶点到第一组顶点集S中为止。
2. 弗洛伊德算法
每个顶点之间的最短路径
(3) 拓扑排序
在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。AOV网中的弧表示活动之间存在的某种制约关系，且不能存在回路。 设G=(V，E)是一个具有n个顶点的有向图， V中的顶点序列v1，v2，……， vn, 满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。 则称这样的顶点序列为一个拓扑序列。所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。构造时会有两个结果，如果此网的全部顶点都被输出，则说明它是不存在环(回路)的AOV网；如果输出顶点数少了，哪怕是少了一个，也说明这个网存在环(回路)，不是AOV网。
拓扑排序的基本思路是: 从AOV网中选择一个入度为0 的顶点输出，然后删去此顶点，并删除以此顶点为尾的弧，继续重复此步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。整个算法的时间复杂度为O(n+e)。
https://blog.csdn.net/qq_35644234/article/details/60578189
