拓扑排序。任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到图中没有无前趋的顶点为止,此情形表明有向图中存在环。
拓扑排序算法思想:
- 在有向图中任选一个没有前趋的顶点输出;
- 从图中删除该顶点和所有以它为尾的弧;
- 重复上述1、2、直到全部顶点都已输出,此时,顶点输出序列即为一个拓朴有序序列;或者直到图中没有无前趋的顶点为止,此情形表明有向图中存在环。
拓扑排序算法伪代码如下:
1. 栈S初始化;累加器count初始化;
2. 扫描顶点表,将没有前驱(即入度为0)的顶点压栈;
3. 当栈S非空时循环
3.1 vj=退出栈顶元素;输出vj;累加器加1;
3.2 将顶点vj的各个邻接点的入度减1;
3.3 将新的入度为0的顶点入栈;
4. if (count<vertexNum) 输出有回路信息;
代码如下:文章来源:https://www.toymoban.com/news/detail-490048.html
#include <stdio.h>
#include <stdlib.h>
#define MAXV 100
#define INF 10000
typedef struct
{
int data[MAXV];
int top;
}SqStack;
typedef struct ANode
{
int adjvex;
struct ANode *nextarc;
int weight;
}ArcNode;
typedef struct
{
int adjvex;
int count;
ArcNode *firstarc;
}VNode;
typedef struct
{
VNode adjlist[MAXV];
int n,e;
}AdjGraph;
void CreateAdj(AdjGraph *&G,int A[MAXV][MAXV],int n,int e)
{
int i,j;
ArcNode *p;
G=(AdjGraph*)malloc(sizeof(AdjGraph));
for(i=0;i<n;i++)
G->adjlist[i].firstarc=NULL;
for(i=0;i<n;i++)
for(j=n-1;j>=0;j--)
if(A[i][j]!=0&&A[i][j]!=INF)
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex =j;
p->weight =A[i][j];
p->nextarc=G->adjlist[i].firstarc;
G->adjlist[i].firstarc =p;
}
G->n =n;
G->e =e;
}
void DispAdj(AdjGraph *G)
{
int i;
ArcNode *p;
for(i=0;i<G->n ;i++)
{
p=G->adjlist[i].firstarc;
printf("%3d:",i);
while(p!=NULL)
{
printf("%3d[%d]->",p->adjvex,p->weight);
p=p->nextarc ;
}
printf("^\n");
}
}
void DestoryAdj(AdjGraph *&G)
{
int i;ArcNode *pre,*p;
for(i=0;i<G->n ;i++)
{
pre=G->adjlist [i].firstarc;
if(pre!=NULL)
{
p=pre->nextarc ;
while(p!=NULL)
{
free(pre);
pre=p;
p=p->nextarc ;
}
free(pre);
}
}
free(G);
}
void InitStack (SqStack *&s)
{
s=(SqStack *)malloc(sizeof(SqStack));
s->top =-1;
}
void DestoryStack(SqStack *&s)
{
free(s);
}
void TopSort(AdjGraph *G)
{
int i,j,flag=0;
int a[MAXV];
int St[MAXV],top=-1;
ArcNode *p;
for(i=0;i<G->n;i++)
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)
{
top++;
St[top]=i;
}
}
while(top>-1)
{
i=St[top];
top--;
a[flag++]=i;
p=G->adjlist [i].firstarc;
while(p!=NULL)
{
j=p->adjvex;
G->adjlist [j].count--;
if(G->adjlist [j].count==0)
{
top++;
St[top]=j;
}
p=p->nextarc;
}
}
if(flag<G->n)
printf("该图存在回路,不存在拓扑序列!\n");
else
{
printf("该图的拓扑序列为:");
for(i=0;i<flag;i++)
printf("%d",a[i]);
printf("\n");
}
}
int main()
{
AdjGraph *G;
int n=7;
int e=8;
int A[100][100]={{0,1},{0,0,1,0,0,1},{0,0,0,0,1},{0,0,1,0,1},{0},{0}};
CreateAdj(G,A,n,e);
printf("图的邻接表:\n");
DispAdj(G);
TopSort(G);
printf("销毁图的邻接表\n");
DestoryAdj(G);
return 0;
}
有问题可以留言文章来源地址https://www.toymoban.com/news/detail-490048.html
到了这里,关于有向图的拓扑排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!