本文将介绍数据结构图论部分中常见的算法
单源最短路径问题(用来计算一个点到其他所有顶点的最短路径)
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中起始节点U0
return 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;
}
感谢大家的点赞和关注，你们的支持是我创作的动力！