// 圖的相鄰矩陣表示存儲(chǔ)圖，實(shí)現(xiàn)圖的拓?fù)渑判?#include <iostream.h>
#include <queue>
#include "Graphm.h"


// 函數(shù)功能：顯示排序后的序列
void Visit(Graph &G, int v) {
	cout << "C" << v << " ";
}
void Visit(int v) {
	cout << "C" << v << " ";
}

//***************************************************************
//[算法7.7] 隊(duì)列實(shí)現(xiàn)的圖拓?fù)渑判?void TopsortbyQueue(Graph& G)  {      //隊(duì)列方式實(shí)現(xiàn)的拓?fù)渑判?	for(int i=0;i<G.VerticesNum();i++)    //初始化Mark數(shù)組
		G.Mark[i]=UNVISITED;
    using std::queue;
	queue<int> Q;                     //初始化隊(duì)列
	for(i=0; i<G.VerticesNum(); i++)
		if(G.Indegree[i]==0)
			Q.push(i);                //圖中入度為0的頂點(diǎn)入隊(duì)
		while(!Q.empty())  {              //如果隊(duì)列中還有圖的頂點(diǎn)
			int V=Q.front();
			Q.pop();                     //一個(gè)頂點(diǎn)出隊(duì)
			Visit(G,V);
			G.Mark[V]=VISITED;
			for(Edge e= G.FirstEdge(V);G.IsEdge(e);e=G.NextEdge(e))  {
				G.Indegree[G.ToVertex(e)]--;  //所有與之相鄰的頂點(diǎn)入度-1
				if(G.Indegree[G.ToVertex(e)]==0)
					Q.push(G.ToVertex(e));   //入度為0的頂點(diǎn)入隊(duì)
			}
		}
		for(i=0; i<G.VerticesNum(); i++)
			if(G.Mark[i]==UNVISITED)  {
				cout<<" 此圖有環(huán)！";        //圖有環(huán)
				break;
			}	
}


int A[N][N] =  {
      //C0  C1  C2  C3  C4  C5  C6  C7  C8	
	    0,  0,  1,  0,  0,  0,  0,  1,  0, 
		0,  0,  1,  1,  1,  0,  0,  0,  0,   
		0,  0,  0,  1,  0,  0,  0,  0,  0,  
		0,  0,  0,  0,  0,  1,  1,  0,  0,  
		0,  0,  0,  0,  0,  1,  0,  0,  0,  
		0,  0,  0,  0,  0,  0,  0,  0,  0,  
		0,  0,  0,  0,  0,  0,  0,  0,  0,  
		0,  0,  0,  0,  0,  0,  0,  0,  1,  
		0,  0,  0,  0,  0,  0,  1,  0,  0};  //該圖為圖7.18表示課程優(yōu)先關(guān)系的有向無環(huán)圖

void main()
	{
		Graphm aGraphm(N);              // 建立圖
		aGraphm.IniGraphm(&aGraphm, A); // 初始化圖
		cout << "Top sort by Queue is : ";
		TopsortbyQueue(aGraphm);
		cout << "\nOK! " << endl; 
	}