Kruskal(克鲁斯卡尔)算法
#include "graph.cpp"
#define MaxSize 100
typedef struct
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
void InsertSort(Edge E[],int n) //对E[0..n-1]按递增有序进行直接插入排序
{
int i,j;
Edge temp;
for (i=1;i<n;i++)
{
temp=E[i];
j=i-1; //从右向左在有序区E[0..i-1]中找E[i]的插入位置
while (j>=0 && temp.w<E[j].w)
{
E[j+1]=E[j]; //将关键字大于E[i].w的记录后移
j--;
}
E[j+1]=temp; //在j+1处插入E[i]
}
}
void Kruskal(MatGraph g)
{
int i,j,u1,v1,sn1,sn2,k;
int vset[MAXV];
Edge E[MaxSize]; //存放所有边
k=0; //E数组的下标从0开始计
for (i=0;i<g.n;i++) //由g产生的边集E
for (j=0;j<=i;j++)
{
if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)
{
E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];
k++;
}
}
InsertSort(E,g.e); //采用直接插入排序对E数组按权值递增排序
for (i=0;i<g.n;i++) //初始化辅助数组
vset[i]=i;
k=1; //k表示当前构造生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<g.n) //生成的边数小于n时循环
{
u1=E[j].u;v1=E[j].v; //取一条边的头尾顶点
sn1=vset[u1];
sn2=vset[v1]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d\n",u1,v1,E[j].w);
k++; //生成边数增1
for (i=0;i<g.n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
int main()
{
MatGraph g;
int A[MAXV][MAXV]={
{0,28,INF,INF,INF,10,INF},
{28,0,16,INF,INF,INF,14},
{INF,16,0,12,INF,INF,INF},
{INF,INF,12,0,22,INF,18},
{INF,INF,INF,22,0,25,24},
{10,INF,INF,INF,25,0,INF},
{INF,14,INF,18,24,INF,0}};
int n=7, e=9;
CreateMat(g,A,n,e); //建立《教程》中图8.27的邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g); //输出邻接矩阵
printf("Kruskal算法结果\n");
Kruskal(g);
return 1;
}
改进的Kruskal(克鲁斯卡尔)算法
#include "graph.cpp"
#define MaxSize 100
//-----并查集算法开始---------------------------------------
typedef struct
{
int u; //边的起始顶点
int v; //边的终止顶点
int w; //边的权值
} Edge;
typedef struct node
{
int rank; //结点对应秩
int parent; //结点对应双亲下标
} UFSTree; //并查集树结点类型
void MAKE_SET(UFSTree t[],int n) //初始化并查集树
{
int i;
for (i=0;i<n;i++) //顶点编号从0到n-1
{
t[i].rank=0; //秩初始化为0
t[i].parent=i; //双亲初始化指向自已
}
}
int FIND_SET(UFSTree t[],int x) //在x所在子树中查找集合编号
{
if (x!=t[x].parent) //双亲不是自已
return(FIND_SET(t,t[x].parent));//递归在双亲中找x
else
return(x); //双亲是自已,返回x
}
void UNION(UFSTree t[],int x,int y) //将x和y所在的子树合并
{
x=FIND_SET(t,x);
y=FIND_SET(t,y);
if (t[x].rank>t[y].rank) //y结点的秩小于x结点的秩
t[y].parent=x; //将y连到x结点上,y作为x的孩子结点
else //y结点的秩大于等于x结点的秩
{
t[x].parent=y; //将x连到y结点上,x作为y的孩子结点
if (t[x].rank==t[y].rank) //x和y结点的秩相同
t[y].rank++; //y结点的秩增1
}
}
//-----并查集算法结束---------------------------------------
//-----堆排序算法开始---------------------------------------
void sift(Edge E[],int low,int high) //筛选算法
{
int i=low,j=2*i; //E[j]是E[i]的左孩子
Edge temp=E[i];
while (j<=high)
{
if (j<high && E[j].w<E[j+1].w) //若右孩子较大,把j指向右孩子
j++; //f变为2i+1
if (temp.w<E[j].w)
{
E[i]=E[j]; //将E[j]调整到双亲结点位置上
i=j; //修改i和j值,以便继续向下筛选
j=2*i;
}
else break; //筛选结束
}
E[i]=temp; //被筛选结点的值放入最终位置
}
void HeapSort(Edge E[],int n)
{
int i;
Edge temp;
for (i=n/2;i>=1;i--) //循环建立初始堆
sift(E,i,n);
for (i=n;i>=2;i--) //进行n-1次循环,完成推排序
{
temp=E[1]; //将第一个元素同当前区间内R[1]对换
E[1]=E[i];
E[i]=temp;
sift(E,1,i-1); //筛选R[1]结点,得到i-1个结点的堆
}
}
//-----堆排序算法结束---------------------------------------
void Kruskal(MatGraph g)
{
int i,j,k,u1,v1,sn1,sn2;
UFSTree t[MaxSize];
Edge E[MaxSize];
k=1; //e数组的下标从1开始计
for (i=0;i<g.n;i++) //由g产生的边集e
for (j=0;j<=i;j++)
if (g.edges[i][j]!=0 && g.edges[i][j]!=INF)
{
E[k].u=i;E[k].v=j;E[k].w=g.edges[i][j];
k++;
}
HeapSort(E,g.e); //采用堆排序对E数组按权值递增排序
MAKE_SET(t,g.n); //初始化并查集树t
k=1; //k表示当前构造生成树的第几条边,初值为1
j=1; //E中边的下标,初值为1
while (k<g.n) //生成的边数小于n时循环
{
u1=E[j].u;
v1=E[j].v; //取一条边的头尾顶点编号u1和v2
sn1=FIND_SET(t,u1);
sn2=FIND_SET(t,v1); //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d\n",u1,v1,E[j].w);
k++; //生成边数增1
UNION(t,u1,v1); //将u1和v1两个顶点合并
}
j++; //扫描下一条边
}
}
int main()
{
MatGraph g;
int A[MAXV][MAXV]={
{0,28,INF,INF,INF,10,INF},
{28,0,16,INF,INF,INF,14},
{INF,16,0,12,INF,INF,INF},
{INF,INF,12,0,22,INF,18},
{INF,INF,INF,22,0,25,24},
{10,INF,INF,INF,25,0,INF},
{INF,14,INF,18,24,INF,0}};
int n=7, e=9;
CreateMat(g,A,n,e); //建立《教程》中图8.27的邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g); //输出邻接矩阵
printf("Kruskal算法结果\n");
Kruskal(g);
return 1;
}
Dijkstra(迪杰斯特拉)算法
#include "graph.cpp"
int count=0;
void Dispath(MatGraph g,int dist[],int path[],int S[],int v)
//输出从顶点v出发的所有最短路径
{ int i,j,k;
int apath[MAXV],d; //存放一条最短路径(逆向)及其顶点个数
for (i=0;i<g.n;i++) //循环输出从顶点v到i的路径
if (S[i]==1 && i!=v)
{ printf(" 从顶点%d到顶点%d的路径长度为:%d\t路径为:",v,i,dist[i]);
d=0; apath[d]=i; //添加路径上的终点
k=path[i];
if (k==-1) //没有路径的情况
printf("无路径\n");
else //存在路径时输出该路径
{ while (k!=v)
{ d++; apath[d]=k;
k=path[k];
}
d++; apath[d]=v; //添加路径上的起点
printf("%d",apath[d]); //先输出起点
for (j=d-1;j>=0;j--) //再输出其他顶点
printf(",%d",apath[j]);
printf("\n");
}
}
}
void disp(int dist[MAXV],int path[MAXV],int n) //输出dis和path
{
int i;
printf(" dist path\n");
for (i=0;i<n;i++)
if (dist[i]!=INF)
printf("%4d",dist[i]);
else
printf("%4s","∞");
printf("\t");
for (i=0;i<n;i++)
printf("%4d",path[i]);
printf("\n");
}
void Dijkstra(MatGraph g,int v) //Dijkstra算法
{ int dist[MAXV],path[MAXV];
int S[MAXV]; //S[i]=1表示顶点i在S中, S[i]=0表示顶点i在U中
int Mindis,i,j,u;
bool flag;
for (i=0;i<g.n;i++)
{ dist[i]=g.edges[v][i]; //距离初始化
S[i]=0; //S[]置空
if (g.edges[v][i]<INF) //路径初始化
path[i]=v; //顶点v到顶点i有边时,置顶点i的前一个顶点为v
else
path[i]=-1; //顶点v到顶点i没边时,置顶点i的前一个顶点为-1
}
disp(dist,path,g.n);
printf("(%d)将顶点%d添加到S集合\n",++count,v);
S[v]=1;path[v]=0; //源点编号v放入S中
for (i=0;i<g.n-1;i++) //循环直到所有顶点的最短路径都求出
{ Mindis=INF; //Mindis置最大长度初值
for (j=0;j<g.n;j++) //选取不在S中(即U中)且具有最小最短路径长度的顶点u
if (S[j]==0 && dist[j]<Mindis)
{ u=j;
Mindis=dist[j];
}
printf(" 求出U中最小的顶点%d\n",u);
printf("(%d)将顶点%d添加到S集合\n",++count,u);
S[u]=1; //顶点u加入S中
flag=false;
for (j=0;j<g.n;j++) //修改不在S中(即U中)的顶点的最短路径
if (S[j]==0)
{
if (g.edges[u][j]<INF)
{
flag=true;
printf(" 考虑顶点%d的邻接点%d:",u,j);
if (dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
printf("修改其最短路径长度dist[%d]为%d,",j,dist[j]);
path[j]=u;
printf("修改最短路径path[%d]为%d\n",j,u);
}
else
printf("顶点%d的最短路径长度没有修改\n",j);
}
}
if (!flag)
printf(" 顶点%d没有未考虑的邻接点(不修改)\n",u);
disp(dist,path,g.n);
}
Dispath(g,dist,path,S,v); //输出最短路径
}
int main()
{
MatGraph g;
int A[MAXV][MAXV]={
{0, 6, INF,INF,2},
{INF,0, INF,INF,INF},
{INF,1, 0, 3, INF},
{2, INF,INF,0, INF},
{INF,3, 1, 3, 0}
};
int n=5, e=8;
CreateMat(g,A,n,e); //建立图的邻接矩阵
printf("图G的邻接矩阵:\n");
DispMat(g); //输出邻接矩阵
int v=0;
printf("从%d顶点出发的最短路径求解过程如下:\n",v);
Dijkstra(g,v);
return 1;
}
拓扑排序算法
#include "graph.cpp"
void TopSort(AdjGraph *G) //拓扑排序算法
{ int i,j;
int St[MAXV],top=-1; //栈St的指针为top
ArcNode *p;
for (i=0;i<G->n;i++) //入度置初值0
G->adjlist[i].count=0;
for (i=0;i<G->n;i++) //求所有顶点的入度
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ G->adjlist[p->adjvex].count++;
p=p->nextarc;
}
}
for (i=0;i<G->n;i++) //将入度为0的顶点进栈
if (G->adjlist[i].count==0)
{ top++;
St[top]=i;
}
while (top>-1) //栈不空循环
{ i=St[top];top--; //出栈一个顶点i
printf("%d ",i); //输出该顶点
p=G->adjlist[i].firstarc; //找第一个邻接点
while (p!=NULL) //将顶点i的出边邻接点的入度减1
{ j=p->adjvex;
G->adjlist[j].count--;
if (G->adjlist[j].count==0)//将入度为0的邻接点进栈
{ top++;
St[top]=j;
}
p=p->nextarc; //找下一个邻接点
}
}
}
int main()
{
AdjGraph *G;
int A[MAXV][MAXV]=
{{0,1,INF,INF,INF,INF},
{INF,0,1,INF,INF,INF},
{INF,INF,0,1,INF,INF},
{INF,INF,INF,0,INF,INF},
{INF,1,INF,INF,0,1},
{INF,INF,INF,1,INF,0}};
int n=6, e=6;
CreateAdj(G,A,n,e); //建立《教程》中图8.44的邻接表
printf("图G的邻接表:\n");
DispAdj(G); //输出邻接表G
printf("拓扑序列:");TopSort(G);printf("\n");
DestroyAdj(G); //销毁邻接表
return 1;
}
求关键路径算法
#include "graph.cpp"
typedef struct
{ int ino; //起点
int eno; //终点
} KeyNode; //关键活动类型
bool TopSort(AdjGraph *G,int topseq[])
//产生含有n个顶点编号的拓扑序列topseq
{
int i,j,n=0;
int st[MAXV]; //定义一个顺序栈
int top=-1; //栈顶指针为top
ArcNode *p;
for (i=0;i<G->n;i++) //所有顶点的入度置初值0
G->adjlist[i].count=0;
for (i=0;i<G->n;i++) //求所有顶点的入度
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ G->adjlist[p->adjvex].count++;
p=p->nextarc;
}
}
for (i=0;i<G->n;i++)
if (G->adjlist[i].count==0) //入度为0的顶点进栈
{ top++;
st[top]=i;
}
while (top>-1) //栈不为空时循环
{ i=st[top];top--; //出栈
topseq[n]=i; n++;
p=G->adjlist[i].firstarc; //找第一个邻接点
while (p!=NULL)
{ j=p->adjvex;
G->adjlist[j].count--;
if (G->adjlist[j].count==0) //入度为0的相邻顶点进栈
{ top++;
st[top]=j;
}
p=p->nextarc; //找下一个邻接点
}
}
if (n<G->n) //拓扑序列中不含所有顶点时
return false;
else
{
printf("拓扑序列:");
for (i=0;i<n;i++)
printf("%c ",(char)(topseq[i]+'A'));
printf("\n");
return true;
}
}
bool KeyPath(AdjGraph *G,int &inode,int &enode,KeyNode keynode[],int &d)
//从图邻接表G中求出从源点inode到汇点enode的关键活动keynode[0..d]
{ int topseq[MAXV]; //topseq用于存放拓扑序列
int i,w;
ArcNode *p;
if (!TopSort(G,topseq))
return false; //不能产生拓扑序列时返回false
inode=topseq[0]; //求出源点
enode=topseq[G->n-1]; //求出汇点
int ve[MAXV]; //事件的最早开始时间
int vl[MAXV]; //事件的最迟开始时间
for (i=0;i<G->n;i++) ve[i]=0; //先将所有事件的ve置初值为0
for (i=0;i<G->n;i++) //从左向右求所有事件的最早开始时间
{ p=G->adjlist[i].firstarc;
while (p!=NULL) //遍历每一条边即活动
{ w=p->adjvex;
if (ve[i]+p->weight>ve[w]) //求最大者
ve[w]=ve[i]+p->weight;
p=p->nextarc;
}
}
for (i=0;i<G->n;i++) //先将所有事件的vl值置为最大值
vl[i]=ve[enode];
for (i=G->n-2;i>=0;i--) //从右向左求所有事件的最迟开始时间
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ w=p->adjvex;
if (vl[w]-p->weight<vl[i]) //求最小者
vl[i]=vl[w]-p->weight;
p=p->nextarc;
}
}
d=-1; //d存放keynode中的关键活动下标,置初置为-1
for (i=0;i<G->n;i++) //求关键活动
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ w=p->adjvex;
if (ve[i]==vl[w]-p->weight) //(i→w)是一个关键活动
{
d++; keynode[d].ino=i; keynode[d].eno=w;
}
p=p->nextarc;
}
}
return true;
}
void DispKeynode(AdjGraph *G)
{
int inode,enode,d,i;
KeyNode keynode[MAXV];
if (KeyPath(G,inode,enode,keynode,d))
{
printf("从源点%c到汇点%c的关键活动:",char(inode='A'),char(enode+'A'));
for (i=0;i<=d;i++)
printf("(%c,%c) ",char(keynode[i].ino+'A'),char(keynode[i].eno+'A'));
printf("\n");
}
else printf("不能求关键活动\n");
}
int main()
{
AdjGraph *G;
int n=9,e=11;
int A[MAXV][MAXV]={
{ 0, 6, 4, 5 ,INF,INF,INF,INF,INF},
{INF, 0, INF,INF, 1 ,INF,INF,INF,INF},
{INF,INF, 0 ,INF, 1 ,INF,INF,INF,INF},
{INF,INF,INF, 0 ,INF,INF,INF, 2 ,INF},
{INF,INF,INF,INF, 0 , 9 , 7 ,INF,INF},
{INF,INF,INF,INF,INF, 0 ,INF,INF, 2 },
{INF,INF,INF,INF,INF,INF, 0 ,INF, 4 },
{INF,INF,INF,INF,INF,INF,INF, 0 , 4 },
{INF,INF,INF,INF,INF,INF,INF,INF, 0 }};
printf("建立图的邻接表:\n");
CreateAdj(G,A,n,e); //创建图8.45的邻接表
printf("图G的邻接表:\n"); DispAdj(G);
DispKeynode(G); //求构成关键路径的关键活动
DestroyAdj(G); //销毁图
return 1;
}