数据结构课程设计：输出一个AOV图的所有拓扑序列（用c++），高手帮个忙

Question

急啊···马上要用了！~

Answer 1

/////////如何找一条拓扑序列的方法可以去查查书，这个是用递归法求的
/////////所有的排序
//这是一个graph.txt的例子
6
1 2 3 -1
-1
1 4 -1
4 -1
-1
3 4 -1

////递归法求所有的拓扑路径
// aov图输入全部拓扑序列.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <string>
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

#define MAX_VERTEX_NUM 20 //假设的最大顶点数

typedef struct ArcNode { //弧结构
int adjvex; //该弧所指向的顶点位置
struct ArcNode *nextarcs; //指向下一条弧的指针
//InfoArc *info; //该弧相关信息的指针
}ArcNode;

typedef struct VNode{ //顶点结构
//VertexType data; //顶点信息
ArcNode * firstarc; //指向第一条依附该顶点的弧的指针
}VNode, AdjList[ MAX_VERTEX_NUM ]; //邻接表

//typedef VNode[ MAX_VERTEX_NUM] AdjList;

typedef struct { //图结构
AdjList vertics ; //应包含邻接表
int vexnum, arcnum; //应包含顶点总数和弧总数
//int kind; //还应说明图的种类（用标志）
}ALGraph;

ALGraph G;

/////
void CreateAOV(char * pathname)
{
ArcNode *p;
ifstream ifs(pathname);
if(!ifs) cerr<<"open file failed"<<endl;
ifs>>G.vexnum;
for(int i=0;i<G.vexnum;i++)
{
int flag=0;
ifs>>flag;
if(-1==flag)
{
G.vertics[i].firstarc=NULL;
}
else
{
G.vertics[i].firstarc=new ArcNode;
G.vertics[i].firstarc->adjvex=flag;
G.vertics[i].firstarc->nextarcs=NULL;
ifs>>flag;
while(flag!=-1)
{
p=new ArcNode;
p->adjvex=flag;
p->nextarcs=G.vertics[i].firstarc;
G.vertics[i].firstarc=p;
ifs>>flag;
}
}
}
ifs.close();
}

////数组indegree是专门用来存放各个结点的入度的
void findindegree(ALGraph G,int *indegree)
{
ArcNode *p;
for(int i=0;i<G.vexnum;i++)
indegree[i]=0;
for(int i=0;i<G.vexnum;i++)
{
p=G.vertics[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarcs;
}
}
}

/////vec0当前入度为0的结点，indeg当前各个结点的入度，
////pos将要添加到拓扑序中的结点在vec0中的位置
////count当前拓扑序的长度
/////保存当前已经排好的拓扑序
////这里所以用到vector是因为在拷贝时它不像数组那样，vector可以复制所有的元素，
////这正是递归所要求的每一次递归都要有自己的局部变量
////////////////////////////
///
void fun(vector<int> vec0,vector<int> indeg,int pos,int count,vector<int> topo)
{
vector<int>::iterator iter,ibegin,iend;
ArcNode *p;
int k;
int the=vec0[pos];
iter=vec0.begin()+pos;
vec0.erase(iter);
topo.push_back(the+1);
////当pos指向的元素进入序列后，将以它为尾的弧去掉，即入度减1,
for(p=G.vertics[the].firstarc;p;p=p->nextarcs){
k=p->adjvex;
if(!(--indeg[k]))vec0.push_back(k);///入度为0的，就进入vec0
}

if(++count==G.vexnum){
copy(topo.begin(),topo.end(),ostream_iterator<int>(cout,"\t"));
cout<<endl;
return;
}
iend=vec0.end();
///////对vec0里的每一个元素都调用一次fun，以找出所有的拓扑序列
for(ibegin=vec0.begin();ibegin!=iend;ibegin++)
{
fun(vec0,indeg,ibegin-vec0.begin(),count,topo);
}
}

void topoSort(ALGraph G)
{
vector<int> vec0;
int *indegree=new int[G.vexnum];
findindegree(G,indegree);
for(int i=0;i<G.vexnum;++i)
if(!indegree[i])vec0.push_back(i);//入度为0者进入vec0
vector<int> indeg;
indeg.insert(indeg.begin(),indegree,indegree+G.vexnum);
vector<int>::iterator iter,ibegin,iend;
iend=vec0.end();
for(ibegin=vec0.begin();ibegin!=iend;ibegin++)
fun(vec0,indeg,ibegin-vec0.begin(),0,vector<int>());
}

int _tmain(int argc, _TCHAR* argv[])
{
CreateAOV("graph.txt");
topoSort(G);
return 0;
}