拓扑排序算法

㈠ 【讨论】“拓扑排序算法仅适用于有向无环图”，对吗

支持7楼的说法。在书上看到的是一个拓扑排序算法，也许还有其他的方法可以进行拓扑排序。而对一个东西进行拓扑排序是要有结果的。拓扑排序算法只是一个可以进行拓扑排序的方法之一，就像各种排序算法都能排序。

㈡ 编程实现图的拓扑排序算法

typedef struct node
{
int adjvex;
struct node *next;
}edgenode;

typedef struct
{
int vertex;
int id;
edgenode *link;
}vexnode;

vexnode dig[n];

void topsort(vexnode dig[])
{
int i,j,k,m=0,top=-1;
edgenode *p;
for(i=0;i<n;i++)
if(dig[i].id==0)
{
dig[i].id=top;
top=i;
}
while(top!=-1)
{
j=top;
top=dig[top].id;
cout<<dig[j].vertex+1<<"\t";
m++;
p=dig[j].link;
while(p)
{
k=p->adjvex;
dig[k].id--;
if(dig[k].id==0)
{
dig[k].id=top;
top=k;
}
p=p->next;
}
}
if(m<n)
cout<<"The network has a cycle.."<<endl;
}
这个是用栈实现的一个算法，你看下吧

㈢ 数据结构 拓扑排序

【1】拓扑排序
在一个表示工程的有向图中，有顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网。
AOV网中的弧表示活动之间存在的某种制约关系。
所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。
【2】拓扑排序算法
对AOV网进行拓扑排序的基本思路：
从AOV网中选择一个入度为0的顶点输出；
然后删除此顶点，并删除以次顶点为尾的弧；
继续重复此操作.....
直到输出全部顶点或AOV网中不存在入度为0的顶点为止。
由于拓扑排序过程中，需要删除顶点，显然用邻接表更加方便。
因此我们需要为AOV网建立一个邻接表。
另外，考虑到算法过程中始终需要查找入度为0的顶点？
需要在原顶点表节点结构中，增加一个入度域in，in就是入度数字。

㈣ 简单拓扑排序算法C语言

#include <stdio.h>
#include <stdlib.h>
#define TURE 1
#define FALSE 0
//图相关----------------------
typedef int ArcCell; /*对于无权图，用1或0表示是否相邻；对带权图，则为权值类型*/
typedef int booleanType; //状态变量
typedef struct
{
ArcCell **arcs; /*邻接矩阵*/
int vexnum; /*图的顶点数和弧数*/
} MGraph; /*（Adjacency Matrix Graph）*/
//-----------------------------

MGraph G; //图
booleanType *visited; //建立标志数组(全局量）

int GetGraph(MGraph *G); //建立邻接矩阵
int SearchNoEn(MGraph *G); //寻找没有入度的结点。如果没有，返回-1，否则返回其位置
booleanType Iscircle(MGraph *G); //判断是否有环。有则返回1，无返回0
int main()
{
GetGraph(&G);
if(Iscircle(&G))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}

int GetGraph(MGraph *G) //建立邻接矩阵
{
int i, j, v;
scanf("%d", &(G->vexnum));
G->arcs = (ArcCell**)malloc(sizeof(ArcCell*) * G->vexnum);
for(i = 0; i < G->vexnum; i++)
{
G->arcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G->vexnum);
} //建立二维动态数组

for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
scanf("%d", G->arcs[i] + j);
}
} //输入数据

visited = (booleanType*)malloc(sizeof(booleanType) * G->vexnum); //分配标志数组
for(v = 0; v < G->vexnum; v++) //初始化
{
visited[v] = FALSE;
}
return 0;
}//GetGraph

int SearchNoEn(MGraph *G) //寻找没有入度的结点。如果没有，返回-1，否则返回其位置
{
int i, j;
for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
if(G->arcs[j][i] == 1)
{
break;
}
if(visited[i] != TURE && j == G->vexnum - 1)
{
return i;
}
}
}
return -1;
}

booleanType Iscircle(MGraph *G) //判断是否有环。有则返回1，无返回0
{
int i, j;
int count = G->vexnum;
i = SearchNoEn(G);
for(; i != -1; i = SearchNoEn(G))
{
for(j = 0; j < G->vexnum; j++)
{
G->arcs[i][j] = 0;
}
visited[i] = TURE;
count--;
}
if(count != 0)
{
return 1;
}
return 0;
}

㈤ 高手解答 全拓扑排序 c语言算法 或者 算法思想也行啊

拓扑排序，很多时候，会作为算法的预处理。
它是针对有向无环图。
我空间中写过，比较详细。
算法思想：
针对一个有向无环图，求它的拓扑排序的一个简单方法：首先找到这个图中入度为0的顶点。把它放在序列的第一个位置，然后删除改顶点和它的边。得到一个新的有向无环图，在找这个图中入度为0的顶点。放在序列的下一个位置，然后再删除改顶点和它的边。。。，这个步骤重复直到图中所有的顶点都在序列中。

详细请看，有程序代码和相应的图片说明。
http://hi..com/huifeng00/blog/item/667348af89c42e044b36d6a6.html

㈥ 拓扑排序的流程图

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止：选择一个入度为0的顶点并输出之；从网中删除此顶点及所有出边。

循环结束后，若输出的顶点数小于网中的顶点数，则输出“有回路”信息，否则输出的顶点序列就是一种拓扑序列。

由AOV网构造出拓扑序列的实际意义是：如果按照拓扑序列中的顶点次序，在开始每一项活动时，能够保证它的所有前驱活动都已完成，从而使整个工程顺序进行，不会出现冲突的情况。

(6)拓扑排序算法扩展阅读

拓扑排序（Topological Sorting）为一个有向无环图（DAG，Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：每个顶点出现且只出现一次。若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面。

拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。例如，在日常工作中，可能会将项目拆分成A、B、C、D四个子部分来完成，但A依赖于B和D，C依赖于D。为了计算这个项目进行的顺序，可对这个关系集进行拓扑排序，得出一个线性的序列，则排在前面的任务就是需要先完成的任务。

㈦ 课程设计 实现拓扑排序算法

#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
typedef struct //构件栈
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack *); //函数声明
int Pop(SqStack *, ElemType *);
void Push(SqStack *,ElemType );
int StackEmpty(SqStack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化栈
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack *S,ElemType *e)//出栈操作
{
if(S->top==S->base)
{return ERROR;}
*e=*--S->top;
//printf("%d\n",e);
// return e;
return 0;
}
void Push(SqStack *S,ElemType e)//进栈操作
{if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}*S->top++=e;
}
int StackEmpty(SqStack *S)//判断栈是否为空
{
if(S->top==S->base)
return OK;
else
return ERROR;}
void CreatGraph(ALGraph *G)//构件图
{int m, n, i;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i = 1; i <= G->vexnum; i++)
{G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
for (i = 1; i <= G->arcnum; i++) //输入存在边的点集合
{
printf("\n请输入存在边的两个顶点的序号:");
scanf("%d%d",&n,&m);
while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{printf("输入的顶点序号不正确 请重新输入:");
scanf("%d%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
printf("建立的邻接表为:\n"); //输出建立好的邻接表
for(i = 1; i <= G->vexnum; i++)
{
printf("%d",G->vertices[i].data);
for(p = G->vertices[i].firstarc; p; p = p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}}
void FindInDegree(ALGraph G, int indegree[])//求入度操作
{
int i;
for (i = 1; i <= G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 1; i <= G.vexnum; i++)
{while (G.vertices[i].firstarc)
{indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G) //进行拓扑排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i <= G.vexnum; i++)
{
printf("第%d个点的入度为%d \n", i, indegree[i]);
}
printf("\n");
for ( i = 1; i <= G.vexnum; i++)
{
if (!indegree[i])
Push(&S,i);
}
printf("进行拓扑排序输出顺序为:"); //输出结果
while(!StackEmpty(&S))
{
Pop(&S,&n);
printf("%4d",G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc)
{
k = p->adjvex;
if (!(--indegree[k]))
{
Push(&S,k);
}
}

}printf("\n");

if (count < G.vexnum)
{
printf("出现错误\n");
}
else
{
printf("排序成功\n");
}
}
int main(void) //主函数
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;
}

㈧ 在用邻接表表示图时，拓扑排序算法时间复杂度为多少

O（n + e）。
对于一个具有n个顶点e条弧的有向图来说，刚开始将入度为0的顶点入栈的时间复杂为O(n)，在之后顶点出栈时，入度减1的操作共执行了e次，所以整个算法的时间复杂度为O(n + e)。

㈨ 图的拓扑排序

拓扑排序是有向图的一个重要操作。在给定的有向图G中，若顶点序列vi1,vi2,...,vin满足下列条件：若在有向图G中从顶点vi到顶点vj有一条路径，则在序列中顶点vi必在顶点vj之前，便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
举例：计算机专业的学生应该学习的部分课程及其每门课程所需要的先修课程。
拓扑排序的方法：
（1）从图中选择一个入度为0的顶点且输出之；
（2）从图中删掉该顶点及其所有以该顶点为弧尾的弧；
反复执行这两个步骤，直到所有的顶点都被输出，输出的序列就是这个无环有向图的拓扑序列。细心的读者可能会发现：在每一时刻，可能同时存在多个入度为0的顶点，选择注：表中c1~c9列表示的是每个顶点的入度。
下面我们讨论一下如何实现拓扑排序的算法。假设有向图以邻接表的形式存储。
下面给出算法实现的基本过程：
{ 将所有入度为0的顶点入栈；
当栈非空时重复执行下列操作：
从栈中退出顶点k；
（1）将k顶点的信息输出；
（2）将与k邻接的所有顶点的入度减1。 }#defineMAX_VERTEX_NUM30//最大顶点个数typestructEdgeLinklist{//边结点intadjvex;structEdgeLinklist*next;}EdgeLinklist;typedefstructVexLinklist{//顶点结点Elemtypeelem;intindegree;//记录顶点的入度EdgeLinklist*firstedge;}VexLinklist,AdjList[MAX_VERTEX_NUM];下面是拓扑排序的完整算法。 StatusTopologicalSort(AdjListadj){InitStack(s);for(i=0;i<MAX_VERTEX_NUM-1;i++)if(adj.indegree==0)Push(s,i);while(!StackEmpty(s)){Pop(s,i);printf(i);for(p=adj.firstedge;p;p=p->next){adj.indegree-=1;if(adj.indegree==0)Push(s,i);}

㈩ 拓扑排序是一种内部排序的算法，对吗

不是，不对的