本文将介绍数据结构图论部分中常见的算法

单源最短路径问题(用来计算一个点到其他所有顶点的最短路径)
Dijkstra(n*n)
1. 初始化: 先找出从源点V0到各终点Vk的直达路径(V0,Vk), 即通过一条弧到达的路径
2. 选择: 从这些路径中找出一条长度最短的路径(V0,u)
3. 更新: 然后对其余各条路径进行适当的调整
若在图中存在弧(u,Vk), 且(Vo,u,Vk)<(Vo,Vk), 则以路径(Vo,u,Vk) 代替(Vo,Vk)
4. 把V分成两组:
(1) S: 已求出最短路径的顶点的集合
(2) T=V-S: 尚未确定最短路径的顶点集合
算法步骤:
1.初始时令S={V0}, T={其余顶点}
2.T中顶点对应的距离值用辅助数组D存放
D[i] 初值: 若<V0,Vi>存在, 则为其权值; 否则为无穷注: 从源点V0开始
3.从T中选取一个其距离值最小的顶点Vj, 加入S
4.对T中顶点的距离值进行修改: 若加进Vj 作中间顶点, 从V0到Vi的距离值比不加Vj的路径要短, 则修改此距离值
重复上述步骤, 直到S=V为止
代码实现：
辅助数组:
-- 数组bool S[n]: 记录相应顶点是否已被确定最短距离
-- 数组D[n]: 记录源点到相应顶点路径长度
-- 数组Path[n]: 记录相应顶点的前驱顶点
1. 从D(T集合中)找最小值v 2. 将最小值对应的顶点, 加入S 3.更新D数组, Path数组
注：找最小值的时候要从D数组中为false的点中找, 并且不能为源点

#include<iostream>
using namespace std;
#define MVNum 20
#define MAXNUM 32767
typedef char VerTexType;  //顶点类型
typedef int ArcType;      //弧类型 
typedef struct{VerTexType vexs[MVNum];   //vexs代表顶点,arcs代表邻接矩阵ArcType arcs[MVNum][MVNum];int vexnum,arcnum;  //vexnum表示图中顶点的数量，arcnum表示图中边的数量
}AMGraph;
int LocateVex(AMGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(v==G.vexs[i]){return i;}} return -1;
}
void CreateUDG(AMGraph &G){cin>>G.vexnum>>G.arcnum;for(int i=0;i<G.vexnum;i++){cin>>G.vexs[i];}for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){G.arcs[i][j]=MAXNUM;}}VerTexType v1,v2;ArcType w;for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;int i=LocateVex(G,v1);int j=LocateVex(G,v2);G.arcs[i][j]=w;}
}
bool S[MVNum];
ArcType D[MVNum];
int Path[MVNum];
void ShortestPath_Dijkstra(AMGraph G,VerTexType u){int k=LocateVex(G,u);for(int i=0;i<G.vexnum;i++){S[i]=false;D[i]=G.arcs[k][i];if(D[i]<MAXNUM){Path[i]=k;}else{Path[i]=-1;}}S[k]=true;int min,v;for(int i=1;i<G.vexnum;i++){min=MAXNUM;for(int j=0;j<G.vexnum;j++){if(j!=k){if(!S[j]&&D[j]<min){min=D[j];v=j;}}}S[v]=true;for(int j=0;j<G.vexnum;j++){if(!S[j]&&D[v]+G.arcs[v][j]<D[j]){D[j]=D[v]+G.arcs[v][j];Path[j]=v; }}}}
int main(){AMGraph G;CreateUDG(G);char u;cin>>u;ShortestPath_Dijkstra(G,u);for(int i=0;i<G.vexnum;i++){cout<<D[i]<<" ";}return 0;
}

所有顶点间的最短路径
方法一：每次以一个顶点源点, 重复执行Dijkstra算法n 次
方法二：floyd 算法(n*n*n)
以上两种方法的时间复杂度是一样的
1. 初始时设置一个n阶方阵, 令其对角线元素为0, 若存在弧<Vi,Vj>, 则对应元素为权值; 否则为无穷
2. 逐步试着在原直接路径中增加中间节点, 若加入中间节点后路径变短, 则修改之; 否则, 维持原值. 所有顶点试探完毕, 算法结束
代码实现：
path 数组初始时为-1, 存储的是前驱节点
邻接矩阵, 对角线存储的是0, 有权值就存权值, 没有权值就存储无穷

#include<iostream>
using namespace std;
#define MVNum 20
#define MAXNUM 32767
typedef char VerTexType;  //顶点类型
typedef int ArcType;      //弧类型 
typedef struct{VerTexType vexs[MVNum];   //vexs代表顶点,arcs代表邻接矩阵ArcType arcs[MVNum][MVNum];int vexnum,arcnum;  //vexnum表示图中顶点的数量，arcnum表示图中边的数量
}AMGraph;
int LocateVex(AMGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(v==G.vexs[i]){return i;}} return -1;
}
void CreateUDG(AMGraph &G){cin>>G.vexnum>>G.arcnum;for(int i=0;i<G.vexnum;i++){cin>>G.vexs[i];}for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){if(i!=j){G.arcs[i][j]=MAXNUM;}else{G.arcs[i][j]=0;}}}VerTexType v1,v2;ArcType w;for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;int i=LocateVex(G,v1);int j=LocateVex(G,v2);G.arcs[i][j]=w;}
}
ArcType D[MVNum][MVNum];
int P[MVNum][MVNum];
void ShortestPath_Floyd(AMGraph G){for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){D[i][j]=G.arcs[i][j];if(D[i][j]<MAXNUM&&i!=j){P[i][j]=i;}else{P[i][j]=-1;}	 }}for(int k=0;k<G.vexnum;k++){  //我咧个n次尝试 for(int i=0;i<G.vexnum;i++){for(int j=0;j<G.vexnum;j++){if(D[i][j]>D[i][k]+D[k][j]){D[i][j]=D[i][k]+D[k][j];P[i][j]=P[k][j];  //从上一个Path二维表里面找,永远存储的是距离终点最近的前驱顶点(因为k是按顺序进行尝试的) }}	}}
}
void Print(int n){for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(D[i][j]<MAXNUM){printf("%4d(%2d)",D[i][j],P[i][j]);}else{printf("%4c(%2d)",'#',P[i][j]);}}printf("\n");}
} 
int main(){AMGraph G;CreateUDG(G);int n=G.vexnum;ShortestPath_Floyd(G);Print(n);return 0;
}

总结来说第一种算法就是先找最小值, 第二种算法就是n次尝试

关键路径问题：拓扑排序
把工程计划表示为边表示活动的网络, 即AOE网, 用顶点表示事件, 弧表示活动, 弧的权表示活动持续时间
事件(顶点)表示在它之前的活动已经完成，在它之后的活动可以开始
源点：入度为0的顶点汇点：出度为0的顶点
关键路径----路径长度最长的路径
路径长度----路径上各活动持续时间之和
ve(vj)----表示事件vj的最早发生时间
vl(vj)----表示事件vj的最迟发生时间
e(i)----表示活动ai的最早开始时间 l(i)----表示活动ai的最迟开始时间
l(i)-e(i)----表示完成活动ai的时间余量
关键活动----关键路径上的活动，即l(i)==e(i)(即l(i)-e(i)==0) 的活动
如何找到l(i) == e(i) 的关键路径？
设活动ai用弧<j,k>表示，其持续时间记为：Wj,k
则有：(1) e(i)==ve(j) -> 直接查弧尾的最早发生时间
(2) l(i) = vl(k) - Wj,k -> 直接查弧头的最迟发生时间- 权值w
如何求ve(j) 和 vl(j) ？
事件j的最早发生时间？
(1) 从ve(1) = 0 开始向前递推
ve(j) = Max{ve(i)+Wi,j},<i,j>->T, 2=<j<=n
其中T是所有以j为头的弧的集合
事件i的最晚发生时间?
(2) 从vl(n)==ve(n) 开始向后向后递推
vl(i)=Min{vl(j)-Wi,j}, <i,j>->S,1<=i<=n-1
其中S是所有以i为尾的弧的集合
1.第一个是从源点往右算 2. 第二个是从汇点往左算

生成树：所有定点均由边连接在一起, 但不存在回路的图
- 一个图可以有许多棵不同的生成树
- 所有生成树具有以下共同特点
1. 生成树的顶点个数与图的顶点个数相同
2. 生成树是图的极小连通子图，去掉一条边则非联通
3. 一个有n个顶点的连通图的生成树有n-1 条边
4. 在生成树中再加一条边必然形成回路
5. 生成树中任意两个顶点间的路径是唯一的
最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那颗生成树称为该网的最小生成树，也叫最小代价生成树
已上两种定义简单来说就是：1.生成树就是连通但是内部没有环，有n-1条边. 2. 最小生成树就是权值最小的生成树
MST性质：
在生成树的构造过程中，图中n个顶点分属两个集合：
- 已落在生成树上的顶点集: U
- 尚未落在生成树上的顶点集: V-U
接下来则应在所有连通U中顶点和V-U中顶点的边种选取权值最小的边(作为生成树的一条边,前提是不能有回路)
Prim 算法
设N={V,E} 是连通网, TE是N上最小生成树中边的集合 {a,b} a 代表点, b代表边
1. 初始令U={u0},{u0->V},TE={ }
2. 在所有u->U, v->V-U的边(u,v)->E中，找一条代价最小的边(u0,v0). 注: 就是权值最小的边
3. 将(u0,v0) 这条边并入集合 TE, 同时 v0这个点并入U
4. 重复上述操作直至U=V为止, 则T=(V,TE) 为N 的最小生成树（意思就是把所有的点都选进集合U, 所以前面写的是U=V）

通俗解释：在U集合中选一个点和在U-V集合中选一个点, 使得这个权值的最小, 然后把弧上的顶点加入到集合U中, 直到U=T集合，得到的连通图就是最小生成树

#include<stdio.h>
#define max 32767
typedef struct
{char *date;int **array;int nodenumber,edgenumber;
} Graph;
struct close   //保存节点的权值和字符
{char date;int wed;
};
int LocateNode(Graph L,char ch)
{for(int i=0; i<L.nodenumber; i++)if(L.date[i]==ch) return i;return -1;
}
void CreatUDG(Graph &L)
{scanf("%d %d",&L.nodenumber,&L.edgenumber);//输入图的节点数和边数getchar();L.date=new char[L.nodenumber];   //节点数组L.array=new int*[L.nodenumber];  //邻接矩阵for(int i=0; i<L.nodenumber; i++){L.date[i]=getchar();getchar();L.array[i]=new int[L.nodenumber];}for(int i=0; i<L.nodenumber; i++)for(int j=0; j<L.nodenumber; j++)L.array[i][j]=max;for(int k=0; k<L.edgenumber; k++){char ch1,ch2;int w;scanf("%c %c %d",&ch1,&ch2,&w);getchar();int i=LocateNode(L,ch1);int j=LocateNode(L,ch2);L.array[i][j]=w;L.array[j][i]=w;}
}
int min(struct close *clos,int n)
{int k;for(int i=1; i<n; i++)if(clos[k].wed==0||(clos[i].wed!=0&&clos[i].wed<clos[k].wed)) k=i;return k;
}
void Prim(Graph L,char v)
{struct close clos[L.nodenumber];int k=LocateNode(L,v);for(int i=0; i<L.nodenumber; i++){clos[i].date=v; 	//类似于一种前驱节点的感觉clos[i].wed=L.array[k][i];}//起始节点与其他节点建立联系clos[k].wed=0; //将起始节点的权值设置为0，表示起始节点已经被选中for(int i=1; i<L.nodenumber; i++){k=min(clos,L.nodenumber);char u0=clos[k].date;   //存储的是k的前驱节点char v0=L.date[k];      //索引k下的节点字符printf("(%c,%c)\n",u0,v0);clos[k].wed=0;          //将选中节点的权值设置为0,表示已经加入到最小生成树for(int j=0; j<L.nodenumber; j++)  //这个循环遍历图中的所有节点。变量 j 表示当前正在检查的节点的索引//如果当前被选中的节点(索引为k),到其他(未被选入最小生成树)节点的权值比原来更小,那么if(L.array[k][j]<clos[j].wed)  {clos[j].date=L.date[k];  //更新前驱// 更新 clos 数组中节点 j 的字符为当前选中节点的字符clos[j].wed=L.array[k][j]; //更新权值//更新 clos 数组中节点 j 的权值为当前选中节点与节点 j 之间的边的权重}}
}
int main(){Graph L;CreatUDG(L);Prim(L,L.date[0]);  //传到Prim函数集合U中起始节点U0return 0;
}

Kruskal算法
1.设连通网 N=(V,E), 令最小生成树初始化状态为只有n个顶点而无边的非联通图 T={V,{ }}, 每个顶点自成一个联通分量
2. 在E中选取代价最小的边, 若该边依附的顶点落在 T中不同的连通分量上(即: 不能成环), 则将此边加入到T中; 否则, 舍去此边, 选取下一条代价最小的边
3.依次类推, 直至T中所有顶点都在同一连通分量上为止
注：通俗来讲就是, 直接把所有顶点都先加入到生成树T中, 然后从所有的边中一次找最短, 次短的边....进行连通,(但是不能成环)

注：最小生成树可能有很多个，同时Kruskal算法在寻找最小边的时候, 可以使用小顶堆{priority_queue<int,vector<int>,greater<int>> pq}, s所以Kruskal算法的时间复杂度就是堆排序的时间复杂度
两种算法比较:
算法名 Prim算法 Kruskal算法
算法思想选择点选择边
时间复杂度 O(n^2)(n为顶点数) O(eloge)(e为边数)
适应范围 (稠密图)(点多的) 稀疏图(边多的)

#include<algorithm>
#include<iostream>
using namesapce std;
#define MVNum 20    //定点数的最大值
#define MANum 20    //边数的最大值
typedef char VerTexType;
typedef int ArcType;
typedef struct{VerTexType vexs[MVNum];int vexnum,arcnum;
}AMGraph;
typedef struct{VerTexType Head; //边的起始点VerTexType Tail; //边的终止点ArcType lowcost; //边上的权值
}Edge; //边的类型
Edge edges[MANum] //存储边信息的辅助数组
//辅助数组 VexSet,记录每个顶点所在联通分量编号
int VexSet[MVNum];
//确定顶点v在G中位置, 即顶点数组的下标
int LocateVex(AMGraph G,VerTexType v){for(int i=0;i<G.vexnum;i++){if(v==G.vexs[i]){return i;}}return -1;
}
void CreateAMGraph(AMGraph &G){cin>>G.vexnum>>G.arcnum;for (int i = 0; i <G.vexnum; i+){cin>>G.vexs[i];}VerTexType v1,v2;ArcType w;for(int k=0;k<G.arcnum;k++){cin>>v1>>v2>>w;edges[k].Head=v1;edges[k].Tail=v2;edges[k].lowcost=w;}
}
//按边上的权值Lowcost进行排序
bool cmp(Edge a,Edge b){if(a.lowcost<b.lowcost){return true;}
}
void MiniSpanTree_Kruskal(AMGraph G){//按边上的权值Lowcost进行排序sort(edges,edges+G.arcnum,cmp);//初始化,每个顶点都是一个独立的连通分量for(int i=0;i<G.vexnum;i++){VexSet[i]=i;}//反复执行，获取G.vexnum-1边for(int i=0;i<G.arcnum;i++){int v1=LocateVex(G.edges[i].Head); //边的起始顶点存储位置的序号,那个顶点    通俗讲：就是找顶点存储在数组的那个位置int v2=LocateVex(G.edges[i].Tail); //边的终止顶点存储位置的序号,那个顶点int vs1=VexSet[v1];  //边的起始顶点所在联通分量的编号int vs1=VexSet[V2];  //边的终止顶点所在连通分量的编号if(vs1!=vs2){printf("(%c,%c)\n",edges[i].Head,edges[i].Tail);//同时将起始顶点所在联通分量和终止顶点所在的连通分量进行(合并)统一编号，变为起始顶点所在连通分量//经过多次统一编号之后, 每个连通分量中就会包含多个顶点for(int j=0;j<G.vexnum;j++){if(VexSet[j]==vs2){VexSet[j]=vs1;}}}}
}
int main(){AMGraph G;CreateAMGraph(G);MiniSpanTree_Kruskal(G)return 0;
}