Question

求C语言高手！数据结构的拓扑排序

写代码，要求：main函数实现有向图的输入,tp函数实现拓扑排序和结果输出。
在线高分等待！

Answer 1

算法

1.无前趋的顶点优先:

(1)算法描述：

(a)从网中选择一个入度为零的顶点输出；

(b)删除该顶点及其于该点有关的所有边；

(c)是否还有入度为零的顶点？若有，执行(a)，否则结束。

算法实现

以邻接表为图的存储结构的算法：

a)扫描顶点表，将入度为零的顶点入栈；

b)当栈非空时：

输出栈顶元素v，出栈；

检查v的出边，将每条出边的终端顶点的入度减1，若该顶点入度为0，入栈；

c)当栈空时，若输出的顶点小于顶点数，则说明AOV网有回路，否则拓扑排序完成。

算法实现：

void Graph::Toplogicasort()//top是入度为0的顶点栈的栈顶指针

{
int top=-1;
for(int i=0;i<n;i++) //建立如度为0顶点的链栈
if (count[i]==0)
{
count[i]=top;
top=i;
}
for(int i=0;i<n;i++)
if(top==-1)
{
cout<<"Network has a cycle"<<endl;
return;
}
else
{
int j=top;top=count[top];//入度为0的顶点出栈
count<<j<<endl;
Edge<float> *l=NodeTable[j].adj;
while(l)
{
int k=l,dest;
if(--count[k]==0)
{
count[k]=top;//入度减至0的顶点进栈
top=k;
}
l=l->link;//取j的下一条出边
}
}
}
/*通常的拓扑算法要用两个数组，一个用来记录每个顶点的入度，当入度为0，则进栈
。另一个数组用作栈数组，记录入度为0的顶点。其实当入度为0的顶点进栈以后，count[i]
＝0就不再有用，所以可以用count[i]记录栈内下一个入度为0的顶点，top指向栈顶顶点号 */

Answer 2

5

Answer 3

这也是我们的作业，保证简单易懂！！
#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;
#define Max 1001
int n,m;
typedef struct Arc*link;
struct Arc
{
char info[15];//存储结点信息
int adjvex;//邻接点编号
link nextarc;//指向下一个邻接点
};
struct Vex
{
char info[15];//顶点信息
int indgree;//顶点入度
link firstarc;//指向下一个邻接点
}v[Max];
int find(char*str)//在顶点集中查找信息为str的定点的编号并返回
{
for(int i=1;i<=n;i++)
if(!strcmp(str,v[i].info))
return i;
}
void creat()//建立邻接表
{
cout<<"课程总数:"<<endl;
cin>>n;
cout<<"请输入各个定点信息（即课程编号）"<<endl;
for(int i=1;i<=n;i++)
{
cin>>v[i].info;
v[i].indgree=0;
v[i].firstarc=NULL;
}
cout<<"请输入有向边数目："<<endl;
cin>>m;
cout<<"输入有向边(先修课程编号在前):"<<endl;
for( i=1;i<=m;i++)
{
char ss[15],tt[12];
cin>>ss>>tt;
int s=find(ss),t=find(tt);
v[t].indgree++;
link p=(link)malloc(sizeof(Arc));
strcpy(p->info,v[t].info);
p->adjvex=t;
p->nextarc=v[s].firstarc;
v[s].firstarc=p;
}
}
void update(int node)//每输出一个顶点时要相应的调用该函数，更新顶点入度信息
{
link p=v[node].firstarc;
while(p)
{
if(v[p->adjvex].indgree>0)
v[p->adjvex].indgree--;
p=p->nextarc;
}
}
int main()
{
int rel[Max],len=0,t;
cout<<"请输入测试数目:"<<endl;
cin>>t;
while(t--)
{
creat();
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if(!v[i].indgree)
{
rel[len++]=i;
v[i].indgree=-1;
update(i);
}
cout<<"-----------------------"<<endl;
if(len<n)
cout<<"Input error!"<<endl;
else
{
for(int i=0;i<len;i++)
cout<<v[i].info<<" ";
cout<<endl;
}
cout<<"------------------------"<<endl;
}
system("pause");
return 0;
}