ds_3.cpp

有向无环图的拓扑排序 用邻接矩阵保存图

// top 拓扑排序
#include "iostream.h"

struct node{
	char c;     
	int inDegree;	// 入度
	int flag;  //标志位(将队列的接点串起来）
};
typedef struct node Node;

int search(char c,Node *a,int n);

int main()
{
	int n,i;
	cout<<"Input the Number of nodes: ";
	cin>>n;

	Node * a;    // save the name of nodes
	a=new Node[n];
	cout<<"Input the name of nodes: ";
	for(i=0;i<n;i++){
		cin>>a[i].c;
		a[i].inDegree=0;   // 入度初值为0
		a[i].flag=-1;// 标志位初值为-1
	}
	
	//邻接矩阵
	char *b;    // 
	b=new char[n*n];
	for(i=0;i<n*n;i++) b[i]=0;//无弧	
	cout<<"Input the Arc using (a b)==>a to b, a\b is the name of node, '#' is end."<<endl;
	char c1,c2;
	int  i1,i2;
	// 输入邻接矩阵
	do{
	
		cin>>c1>>c2;
		if(c1=='#') break;
		i1=search(c1,a,n);
		i2=search(c2,a,n);
		if(i1>=0 && i2>=0) b[i1*n+i2]=1;  //有弧
		a[i2].inDegree++;   // c2入度加1
	}while(1);
	
	//top排序
	int curLoc=-1;//标志队首
	int m=0;  //已经出队结点数目
	int t=0;
	//初始化栈
	for(i=0;i<n;i++){
		if(a[i].inDegree==0){
			a[i].flag=curLoc;
			curLoc=i;
		} 
	} 
	do{		
		
		if(curLoc==-1) break;//表示栈空
		else{
			cout<<" "<<a[curLoc].c;
			m++;
			t=curLoc;
			curLoc=a[curLoc].flag;//出栈
			for(i=0;i<n;i++){
				if(b[t*n+i]==1){
					a[i].inDegree--;
					if(a[i].inDegree==0){	// 入栈
						a[i].flag=curLoc;
						curLoc=i;
					} 
				}
			} 
		}
	}while(1);
	if(m<n-1) cout<<"图中存在环！"<<endl;
	else cout<<endl<<"拓扑排序成功！"<<endl;
	return 0;
}


int search(char c,Node *a,int n)
{
	int i;
	i=0;
	while(i<n && a[i].c!=c) i++;
	if(i>=n) return -1;
	else return i;
}