有向图的拓扑排序算法

A. 数据结构题。有向图，给出该图的一种拓扑排序序列

拓扑排序的方法和步骤：

（1）在图中选一个没有前趋的顶点并输出之

（2）删除该顶点及由它发出的各边，直到图中不存在没有前趋的顶点为止。

答案：1，3，2，4，5

B. 数据结构用什么方法来判断有向图是否存在回路

数据结构中用拓扑排序来判断有向图是否存在回路。

用顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网（AOV网）。一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行。

在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，数据结构中把此序列叫做拓扑序列，由AOV网构造拓扑序列的过程叫做拓扑排序。

综上，若一个有向图中存在拓扑排序，则有向图中不存在回路。

(2)有向图的拓扑排序算法扩展阅读：

在有向图进行拓扑排序的算法思想：

由AOV网构造拓扑序列的拓扑排序算法主要是循环执行以下两步，直到不存在入度为0的顶点为止。

1、选择一个入度为0的顶点并输出之；

2、从网中删除此顶点及所有出边。

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

参考资料来源：网络-拓扑排序

参考资料来源：网络-有向图

C. n 个顶点的有向图用邻接矩阵 array 表示，下面是其拓扑排序算法，试补充完整。

（1） 0
（2） array[j][i]
（3）0
（4）indegree[i] == 0
（5）vex
（6）array[k][i] == 1
（7）indegree[i] == 0
（8） count < n

D. 数据结构 拓扑排序

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

E. 数据结构课设 题目：拓扑排序算法

//首先是用邻接表表视图,下面是邻接表的数据结构定义
const int MaxVertexNum = {图的最大顶点数，要大于等于具体图的顶点数n};
const int MaxEdgetNum = {图的最大边数，要大于等于具体图的边数e};

typedef VertexType vexlist[MaxVertexNum]; //定义vexlist为存储顶点信息的数组类型

struct edgenode //定义邻接表中的边结点类型
{
int adjvex; //邻接点域
int weight; //权值域
edgenode* next;//指向下一个边结点的链域
};

typedef edgenode* adjlist[MaxVertexNum]; //定义adjlist为存储n个表头指针的数组类型

//通过从键盘上输入的n个顶点信息和e条有向边信息建立顶点数组GV和邻接表GL
void Create2(vexlist GV, adjlist GL, int n, int e)
{
int i,j,k;
//建立顶点数组
cout<<"输入"<<n<<"个顶点的值："<<endl;
four(i = 0; i<n; i++)
cin>>GV[i];
//初始化邻接表
for(i=0; i<n; i++)
GL[i] = NULL;
//建立邻接表
cout<<"输入"<<e<<"条边："<<endl;
for(k=1; k<=e; k++)
{
//输入一条边<i,j>
cin>>i>>j;
//分配新结点
edgenode* p = new edgenode;
//将j值赋给新结点的邻接点域
p->adjvex = j;
//将新结点插入到邻接表表头
p->next = GL[i];
GL[i] = p;
}
}

//对邻接表GL表示的有n个顶点的有向图拓扑排序
void TopoSort(adjlist GL, int n)
{
int i,j,k,top,m=0; //m统计拓扑排序中的顶点数
edgenode* p;
//定义存储图中每个顶点入度的一维整型数组d
int* d = new int[n];
//初始化数组d中每个元素值为0
for(i=0; i<n; i++)
d[i] = 0;
//利用数组d记录每个顶点的入度
for(i = 0; i < n; i++)
{
p = GL[i];
while(p != NULL)
{
j = p->adjvex;
d[j]++;
p = p->next;
}
}
//初始化用于链接入度为0的栈顶指针top为-1
top = -1;
//建立初始栈
for(i = 0; i < n; i++)
if(d[i] == 0)
{
d[i] = top;
top = i;
}
//每循环一次删除一个顶点及所有出边
while(top != -1)
{
j = top; //j的值为一个入度为0的顶点序号
top = d[top]; //删除栈顶元素
cout<<j<<' '; //输出一个入度为0的顶点
m++; //输出顶点个数加1
p = GL[j]; //p指向邻接点表的第一个结点
while(p != NULL)
{
k = p->adjvex;
d[k]--;
if( d[k] == 0) //把入度为0的元素进栈
{
d[k] = top;
top = k;
}
p = p->next;
}
}
cout<<endl;
if(m<n)
cout<<"存在回路！"<<endl;
delete []d;
}

F. 采用邻接矩阵存储结构对有向图进行拓扑排序的算法

lint topsort( ALGraph *G) /*拓扑排序*/
{ int i,j,k,top =-1;
EdgeNode *ptr;
for(i=0;i<G->n;i++) /*入度为0入栈*/
{ if(G->adjlist[i].indegree==0)
{ G->adjlist[i].indegree=top;
top=i; }
}
{if(top==-1) return -1; /*网中有回路*/
j=top;
for(i=0;i<G->n;i++)
{ if(top==-1) return -1;/*AOV网中有回路*/
j=top;
top=G->adjlist[top].indegree; /*从栈中退出一个入度为0的顶点并输出*/
printf("->%s",G->adjlist[j].vertex);
ptr=G->adjlist[j].firstedge;
{ k=ptr->adjvex;
G->adjlist[k].indegree--; /*修改其他顶点的入度*/
if(G->adjlist[k].indegree==0) /*为0入栈*/
while(ptr!=NULL)
{
G->adjlist[k].indegree=top;
top=k;
}
ptr=ptr->next;
}
}
}

G. 任意给定一个有向图，设计一个算法，对它进行拓扑排序(C++实现)

LS的方法可行，但是比较麻烦，我来说一种特别简单的方法！

我们for每个点，每次碰到一个未处理过的点就 处理（深搜） 这个点，并 处理（深搜） 这个点连向的所有点，处理完每个点连向的所有点后，在堆栈中加入这个点。

差不多就是这样：

dfs(点h)
{
visit[h]=true
for(所有h连向的点)
if(!visit[h连向的点])
dfs(h连向的点)
stack[++top]=h
}

for(所有点)
if(!visit[这个点])
dfs(这个点)

然后按栈输出即可，这个一定是对的，因为我们每次把这个点加入栈之前都已经把这个点连向的点加入栈了，所以满足拓扑序！

H. 数据结构拓扑排序序列

拓扑排序序列有6种。先找到第一个没有被指的，就是C1，加入序列。然后擦掉跟C1有关的边，此时C2和C3都满足没有被指，选一个，比如选C2，加入序列，擦掉和C2有关的边，这个时候可以选C3,C4,C5或C6，如此而已。

I. 数据结构中 关于图拓扑排序算法 有个地方不太明白 希望能得到解答

我知道你哪里不明白了，你没看见上面的for循环，1，如果不为0，则不执行if了，但执行for循环。2，执行for循环的目的就是把所有的入度减1，减为0的入栈。