课题二拓扑排序
2．1 问题的提出2.1 问题的提出
任务：编写函数实现图的拓扑排序。
程序所实现的功能：建立对应的邻接表，对该图进行拓扑排序，并显示排序
结果。
输入：
顶点数, 边数及各顶点信息(数据格式为整形)
输出：
拓扑排序结果。
2. 2 概要设计
1.拓扑排序是指由某个集合上的一个偏序得到该集合上的一个全序。
更直观地讲，一个偏序是自反的、反对称的，用图表示时每个点都有环且只有单向边。
拓扑排序的任务是在这个偏序上得到一个全序，即得到一个完成整个项目的各步骤的序列。
2．解决拓扑排序的方法如下：
（1）在有向图中选一个没有前驱的顶点且输出之。
（2）从图中删除该顶点和所有以它为尾的弧。
重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。
后一种情况则说明有向图中存在环。
具体的算法实现参照源程序。
3．构造邻接表图：typedef struct{
AdjList vertices;
int vexnum,arcnum;
}Graph;//邻接表图
4.为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点：typedef struct stack{
int *base;
int *top;
int stacksize;
}sqstack;//栈的结构，存储图的顶点序号
2．3 流程图2.根据算法思想，画流程图如下：
2．4 源代码
//采用尾插法创的邻接图
#include<iostream>
using namespace std;
const int MAX=20;
const int STACK_INIT_SIZE=100;
const int ERROR=0;
typedef struct stack{
int *base;
int *top;
int stacksize;
}sqstack;//栈的结构，存储图的顶点序号
typedef struct lnode
{
int adjvex;
struct lnode *next;
}ArcNode;//弧结点
typedef struct node2
{
char data;
ArcNode *fristarc;
}VNode,AdjList[MAX];//顶点数组,fristarc指向与顶点邻接的第一条弧
typedef struct{
AdjList vertices;
int vexnum,arcnum;
}Graph;//邻接表图
void Initstack(sqstack &s)
{
s.base=new int;
if(!s.base)
exit(0);
s.top=s.base;
s.stacksize= STACK_INIT_SIZE;
}
void Push(sqstack &s,int &e)
{
*s.top++=e;
}
int Emptystack(sqstack &s)
{
if(s.base==s.top)
return 1;
else
return 0;
}
int Pop(sqstack &s,int &e)
{
if(s.base==s.top)
return ERROR;
e=*--s.top;
}
void CreatGraph(Graph &G,int *indegree)
{
cout<<"请输入图的顶点数和弧数(且顶点数不能超过"<<MAX<<")"<<endl; cin>>G.vexnum>>G.arcnum;
cout<<"请输入顶点值:"<<endl;
for(int i=0;i<G.vexnum;i++)//输入图的顶点
{
cin>>G.vertices[i].data;
G.vertices[i].fristarc=NULL;
indegree[i]=0;
}
for(i=0;i<G.arcnum;i++)//输入图的弧
{
int m,n;
ArcNode *p;
cout<<"请输入第"<<i+1<<"条弧的弧尾和弧头:"<<endl;
cin>>m>>n;
p=new ArcNode;
if(!p)
exit(0);
indegree[n-1]++;//求每个顶点的入度值
p->adjvex=n-1;
p->next=G.vertices[m-1].fristarc;
G.vertices[m-1].fristarc=p;
}
}
int Toposort(Graph &G,int *indegree)
{
sqstack S;
Initstack(S);
for(int i=0;i<G.vexnum;i++)//0入度顶点入栈
{
if(!indegree[i])
Push(S,i);
}
int count=0;
while(!Emptystack(S))
{
Pop(S,i);
cout<<G.vertices[i].data<<" ";
count++;//记录输出的顶点数
for(ArcNode *p=G.vertices[i].fristarc;p;p=p->next)//把与顶点
{ //相邻接的顶点的入度
int k=p->adjvex;
if(!(--indegree[k]))
Push(S,k);
}
}
if(count<G.vexnum)
return 0;
else
return 1;
}
int main()
{
Graph G;
int *indegree;
indegree=new int;
CreatGraph(G,indegree);
if(!Toposort(G,indegree))
{
cout<<endl;
cout<<"拓扑排序不成功!"<<endl;
}
else
{
cout<<endl;
cout<<"拓扑排序成功!"<<endl;
}
return 0;
}
2．5 结果与分析2.4 测试及性能分析
1．它的时间复杂度是O(G.vexnum+G.arcnum)。
2. 整个程序的关键就是采用尾插法创的邻接表图，运用栈来实现各个数值
的输入输出及存储。
3．注意*的使用，并不是什么情况下都用*，它有时候会造成数据破坏，利用破坏的值进行运算，结果可想而知，所以，如果没返回值时，一般不
要用。
4．为了避免重复检测入度为零的顶点，源程序中设了一个栈，暂存所有入度为零的顶点，此程序段书写如下：
InitStack(S);
for (i=0;i<G.vexnum;++i) //建零入度顶点栈S
if(!indegree[i]) Push(S,i);//入度为0者进栈
count = 0; //对输出顶点计数
while (!StackEmpty(S)){
Pop(S,i);printf(i,G.vertices[i].data);++count; //输出i号顶点并计数
for (p=G.vertices[i].firstarc;p;p=p->next){
k=p->adj; //对i号顶点的每个邻接点的入度减1
if(!(--indegree[k])) Push(S,k); //一旦入度为0，则入栈
}//for
}//while
5．测试的数据如下：
第一组结果（有向无环图）：
第二组结果（有向有环图）：
第一组对应的图如下：
第二组对应的图如下：。