判断一个有向图中是否存在回路，并进行输出拓扑算法

判断一个有向图中是否存在回路，并进行输出（拓扑算法）

#include“AdjGrap.h“
#define INFINITE 32767
using namespace std;
template 
bool ToplogySort（AdjGraph&G int *SortArray）
{
	int n = G.VerticesNum（）;
	int * indegree = new int[n];
	int v;
	Edge e;
	for （v = 0; v < n; v++）
	{
		indegree[v] = 0;
		G.Mark[v] = UNVISITED;
	}
	for （v = 0; v < n; v++）
	{
		//统计各个顶点的入边信息
		for （e = G.FirstEdge（v）; G.IsEdge（e）; e = G.NextEdge（e））
		{
			indegree[e.end]++;
		}
	}
	for （int i = 0; i < n; i++）
	{
		for （v = 0; v < n; v++）
		{
			if （indegree[v] == 0 && G.Mark[v] == UNVISITED）
			{
				break;
			}
		}
		if （v == n &&i!=（n-1）） { 
			cout << “这条回路经过的点为“ << endl;
			for （int i = 0; i < n; i++）
			{
				if （G.Mark[i] == UNVISITED）
					cout << i << “    “;
       
			}
			cout << endl;
			return false; }
		G.Mark[v] = VISITED;
		SortArray[i] = v;
		for （e = G.FirstEdge（v）; G.IsEdge（e）; e = G.NextEdge（e））
		{
			indegree[e.end]--;
		}
	}
	delete[]indegree;
	return true;
}
void main（）
{
	int SortArraay[6];
	AdjGraph graph（6）;
	graph.setEdge（0 0 INFINITE）;
	graph.setEdge（0 1 12）;
	graph.setEdge（0 2 10）;
	graph.setEdge（0 3 INFINITE）;
	graph.setEdge（0 4 30）;
	graph.setEdge（0 5 100	）;
	graph.setEdge（1 0 INFINITE）;
	graph.setEdge（1 1 INFINITE）;
	graph.setEdge（1 2 5）;
	graph.setEdge（1 3 INFINITE）;
	graph.setEdge（1 4 INFINITE）;
	graph.setEdge（1 5 INFINITE）;
	graph.setEdge（2 0 INFINITE）;
	graph.setEdge（2 1 INFINITE）;
	graph.setEdge（2 2 INFINITE）;
	graph.setEdge（2 3 50）;
	graph.setEdge（2 4 INFINITE）;
	graph.setEdge（2 5 INFINITE）;
	graph.setEdge（3 0 INFINITE）;
	graph.setEdge（3 1 INFINITE）;
	graph.setEdge（3 2 INFINITE）;
	graph.setEdge（3 3 INFINITE）;
	graph.setEdge（3 4 INFINITE）;
	graph.setEdge（3 5 10）;
	graph.setEdge（4 0 INFINITE）;
	graph.setEdge（4 1 INFINITE）;
	graph.setEdge（4 2 INFINITE）;
	graph.setEdge（4 3 20）;
	graph.setEdge（4 4 INFINITE）;
	graph.setEdge（4 5 INFINITE）;
	graph.setEdge（5 0 INFINITE）;
	graph.setEdge（5 1 INFINITE）;
	graph.setEdge（5 2 INFINITE）;
	graph.setEdge（5 3 INFINITE）;
	graph.setEdge（5 4 100）;//修改书上5和4点的距离 ，使得成为环
	graph.setEdge（5 5 INFINITE）;
	if （!ToplogySort（graph SortArraay））
	{
		cout << “有回路“ << endl;
		return;
	}
	cout << “没有回路“ << endl;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-12-21 14:15  .vs\
     目录           0  2016-12-21 14:15  .vs\P198T9\
     目录           0  2016-12-21 14:15  .vs\P198T9\v14\
     文件       32768  2016-12-21 18:33  .vs\P198T9\v14\.suo
     目录           0  2016-12-21 18:12  Debug\
     文件       54784  2016-12-21 18:33  Debug\P198T9.exe
     文件      425616  2016-12-21 18:33  Debug\P198T9.ilk
     文件      970752  2016-12-21 18:33  Debug\P198T9.pdb
     目录           0  2016-12-21 18:33  P198T9\
     文件        1784  2016-12-21 18:21  P198T9\AdjGrap.h
     目录           0  2016-12-21 18:33  P198T9\Debug\
     文件         624  2016-12-21 18:12  P198T9\Debug\P198T9.Build.CppClean.log
     文件         141  2016-12-21 18:33  P198T9\Debug\P198T9.log
     目录           0  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\
     文件         558  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\CL.command.1.tlog
     文件       15726  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\CL.read.1.tlog
     文件         296  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\CL.write.1.tlog
     文件         970  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\link.command.1.tlog
     文件        2770  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\link.read.1.tlog
     文件         280  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\link.write.1.tlog
     文件         186  2016-12-21 18:33  P198T9\Debug\P198T9.tlog\P198T9.lastbuildstate
     文件      347136  2016-12-21 18:33  P198T9\Debug\vc140.idb
     文件      356352  2016-12-21 18:33  P198T9\Debug\vc140.pdb
     文件       65691  2016-12-21 18:33  P198T9\Debug\源.obj
     文件         988  2016-12-21 14:19  P198T9\Edge.h
     文件        1150  2016-12-21 18:21  P198T9\Grap.h
     文件        7517  2016-12-21 14:19  P198T9\P198T9.vcxproj
     文件        1236  2016-12-21 14:19  P198T9\P198T9.vcxproj.filters
     文件        2376  2016-12-21 18:33  P198T9\源.cpp
     文件        1300  2016-12-21 14:15  P198T9.sln
     文件     8286208  2016-12-21 18:33  P198T9.VC.db
............此处省略0个文件信息