有向無回路圖拓撲排序C++實現

 

// 有向無回路圖拓撲排序.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include<iostream>

#define MAX 100

using namespace std;

enum Color{white,gray,black};

struct edgeNode

{

 int no; //邊尾端的序號

 char info; //邊端的名稱

 struct edgeNode * next; //下一個

};

struct vexNode

{

 char info;  //節點名稱

 struct edgeNode *link; //與之相連的端點

};

//存儲節點信息

vexNode adjlist[MAX];

//訪問層次

//還沒訪問為white，訪問了但是還沒完成它的所有後裔的搜索為gray

//完成它的所有後裔的搜索為black

Color color[MAX];

//訪問的開始時間

int d[MAX];

//訪問的完成時間

int f[MAX];

//前驅節點

int parent[MAX];

//拓撲排序後的數組，按照f[]的大小排序，即先完成搜索的節點排在前面

int topu[MAX];

//建立鄰接表存儲

//adjlist為節點集，n為節點個數，e為邊數目

void createGraph(vexNode *adjlist,int n,int e)

{

 int i;

 for(i=1;i<=n;i++)

 {

  cout<<"請輸入節點"<<i<<"的名稱：";

  cin>>adjlist[i].info;

  adjlist[i].link = NULL;

 }

 edgeNode *p1;

   int v1,v2;

 for(i=1;i<=e;i++)

 {

  cout<<"請輸入邊"<<i<<"的起始節點序號：";

  cin>>v1;

  cout<<"請輸入邊"<<i<<"的尾節點序號：";

  cin>>v2;

  p1 = (edgeNode*)malloc(sizeof(edgeNode));

  p1->no = v2;

  p1->info = adjlist[v2].info;

  p1->next = adjlist[v1].link;

  adjlist[v1].link = p1;

 }

}

//深度優先搜索有向無權圖

//parent[i]為節點i前驅節點，time為一個全局時間戳，v是第幾個節點，index是topu數組的全局偏移

void DFS(vexNode *adjlist,int *parent,int &time,int v,int &index)

{

 color[v] = gray;

 time += 1;

 d[v] = time;

 int i;

 edgeNode *p;

 p = adjlist[v].link;

 while(p != NULL)

 {

  if(color[p->no]==white)

  {

   parent[p->no] = v;

   DFS(adjlist,parent,time,p->no,index);

  }

  p = p->next;

 }

 color[v] = black;

 time += 1;

 f[v] = time;

 topu[index++] = v;

}

int _tmain(int argc, _TCHAR* argv[])

{

 int cases;

 cout<<"請輸入案例的個數：";

 cin>>cases;

 while(cases--)

 {

  int n,e;

  cout<<"請輸入節點數：";

  cin>>n;

  cout<<"請輸入邊數：";

  cin>>e;

  //訪問節點的時間戳

  int time = 0;

  //index是topu數組的全局偏移

  int index = 1;

  //訪問標志清空與前驅節點都初始化為0

  int i;

  for(i=1;i<=n;i++)

  {

   color[i] = white;

   parent[i] = 0;

  }

  //創建鄰接表

  createGraph(adjlist,n,e);

  for(i=1;i<=n;i++)

  {

   if(color[i]==white)

    DFS(adjlist,parent,time,i,index);

  }

  cout<<"輸出拓撲排序結果："<<endl;

  for(i=1;i<=n;i++)

   cout<<adjlist[topu[i]].info<<"  ";

  cout<<endl;

 }

 system("pause");

 return 0;

}

----------------------------------------------------程序測試---------------------------------------------------

                                                             

 

請輸入案例的個數：1

請輸入節點數：9

請輸入邊數：9

請輸入節點1的名稱：a

請輸入節點2的名稱：b

請輸入節點3的名稱：c

請輸入節點4的名稱：d

請輸入節點5的名稱：e

請輸入節點6的名稱：f

請輸入節點7的名稱：g

請輸入節點8的名稱：h

請輸入節點9的名稱：i

請輸入邊1的起始節點序號：1

請輸入邊1的尾節點序號：2

請輸入邊2的起始節點序號：1

請輸入邊2的尾節點序號：4

請輸入邊3的起始節點序號：2

請輸入邊3的尾節點序號：3

請輸入邊4的起始節點序號：4

請輸入邊4的尾節點序號：3

請輸入邊5的起始節點序號：5

請輸入邊5的尾節點序號：6

請輸入邊6的起始節點序號：5

請輸入邊6的尾節點序號：8

請輸入邊7的起始節點序號：6

請輸入邊7的尾節點序號：4

請輸入邊8的起始節點序號：6

請輸入邊8的尾節點序號：8

請輸入邊9的起始節點序號：7

請輸入邊9的尾節點序號：8

輸出拓撲排序結果：

c  d  b  a  h  f  e  g  i

請按任意鍵繼續. . .

 

作者 heyongluoyao8