//AOV网络的topu排序
#include < iostream.h >
/******************图的定义********************/
//边表结点定义
template <typename T>
struct Edge
{
int AdjVer;
Edge<T> *next;
};
//顶点表结点定义
template <typename T>
struct Vertex
{
T data;
Edge<T> *next;
};
////////////////
//图用邻接表实现
////////////////
template <typename T>
class Graph
{
private:
int size ;
int *inDegree ;
public:
Vertex<T> *Array;
Graph()
{
cout<<" 构造有向图"<<endl;
cout<<endl;
cout<<"...1..输入节点个数"<<endl;
int n ;
cin >> n ;
size = n;
//
Array = new Vertex<T> [size];
inDegree = new int [size];
for (int p=0;p<size;p++)
{
inDegree[p] = 0;
}
cout<<"...2..构造节点"<<endl;
for (int i=0; i<size; i++)
{
cout<<"输入节点"<<i<<"的值"<<endl;
T temp;
cin >>temp;
Array[i].data = temp ;
Array[i].next = NULL ;
}
//
int edge ;
cout<<"...3..构造边，输入边数"<<endl;
cin>>edge;
cout<<endl;
for ( int k = 0 ; k<edge ; k++ )
{
int i ,j ;
cout<<" 输入边"<<'\t'<<k+1<<endl;
cout<<"由节点 ";
cin >>i;
cout<<"到节点 ";
cin>>j;
inDegree[j] = inDegree[j]+1;
//
Edge<T>* TempEdge = new Edge<T>;
TempEdge->next = NULL;
TempEdge->AdjVer = j;
if ( Array[i].next == NULL )
{
Array[i].next = TempEdge ;
}
else
{
Edge<T>* point = NULL;
point = Array[i].next;
while ( (*point).next != NULL )
{
point = (*point).next;
}
(*point).next = TempEdge;
}
}
}
int InDegree(int V)
{
return inDegree[V];
}
void ShowList()
{
cout<<" ..... 邻接表实现图如下 ....."<<endl;
cout<<endl;
for ( int l=0; l<size; l++ )
{
cout<<"节点 "<<l<<" "<<"数据 "<<Array[l].data<<'\t'<<"相邻节点为 ";
if ( Array[l].next != NULL )
{
Edge<T>* point = Array[l].next ;
while (1)
{
cout<<(*point).AdjVer<<'\t';
if ( (*point).next==NULL ) break ;
point = (*point).next ;
}
cout<<endl;
}
else
{
cout<<endl;
}
}
}
int ReturnSize()
{
return size ;
}
};
/******************Topo排序函数的定义********************/
template <typename T>
void Topo(Graph<T> G)
{
Edge<T>* p;
int i,j,Vnum=0,top,k,n=G.ReturnSize();
int *InDegree = new int [n];
int *Topo = new int [n];
for (i=0;i<n;i++)
InDegree[i] = G.InDegree(i);
//链式栈，每次取出栈顶top所指元素
top = -1;
for (i=0;i<n;i++)
if (InDegree[i]==0)
{
InDegree[i] = top;
top = i ;
}
cout<<endl;
cout<<" ******* 产生的拓扑序列为 ******* "<<endl;
while(top!=-1)
{
j = top;
top = InDegree[top];
cout<<"节点 "<<j<<"数据 "<<G.Array[j].data<<endl;
Vnum++;
p=G.Array[j].next;
while(p!=NULL)
{
k=(*p).AdjVer;
InDegree[k]--;
if ( InDegree[k]==0 )
{
InDegree[k] = top ;
top = k;
}
p=p->next;
}
}
cout<<endl;
if (Vnum<n)
cout<<" 此图不能生成拓扑序列"<<endl;
delete []InDegree;
}
void main()
{
Graph<char> MyGraph;
MyGraph.ShowList();
Topo(MyGraph);
}
