题目

已知一个图的顶点集V和边集G分别为V={0, 1, 2, 3, 4, 5, 6, 7, 8}，E={<0, 1>, <0, 2>, <1, 3>, <1, 4>, <2, 4>, <2, 5>, < 3, 6>, < 3, 7>, <4, 7>, <4, 8>, <5, 7>, < 6, 7>, <7, 8>}，若采用邻接表存储，并且每个顶点邻接表中的边结点都是按照终点序号从大到小的次序连接的，则按照拓扑排序算法，写出得到的拓扑序列，并编程实现。

实现代码

参考一

#include <iostream>
#include <list>
#include <stack>
#include <algorithm>
using namespace std;
#define NumVertices 9  // 顶点个数
typedef struct  // 图的邻接表
{
	int n;  // 图中当前的顶点个数
	list<int> adj[NumVertices];
}AdjGraph;

void makeNull(AdjGraph& G, int n)
{
	G.n = n;
}

void addEdge(AdjGraph& G, int v, int w)
{
	G.adj[v].push_back(w);
	G.adj[v].sort(greater<int>());
}

void printGraph(AdjGraph G)
{
	for (int i = 0; i < G.n; ++i)
	{
		cout << i << ": ";
		for (auto j = G.adj[i].begin(); j != G.adj[i].end(); ++j)
		{
			cout << *j << ' ';
		}
		cout << endl;
	}
}

void topologicalSortUtil(AdjGraph& G, int v, bool visited[], stack<int>& Stack)
{
	visited[v] = true;

	for (auto i = G.adj[v].begin(); i != G.adj[v].end(); ++i)
	{
		if (!visited[*i])
		{
			topologicalSortUtil(G, *i, visited, Stack);
		}
	}
	Stack.push(v);
}

void topologicalSort(AdjGraph& G)
{
	stack<int> Stack;

	bool* visited = new bool[G.n];
	for (int i = 0; i < G.n; ++i)
	{
		visited[i] = false;
	}

	for (int i = 0; i < G.n; ++i)
	{
		if (visited[i] == false)
		{
			topologicalSortUtil(G, i, visited, Stack);
		}
	}
	while (!Stack.empty())
	{
		cout << Stack.top() << ' ';
		Stack.pop();
	}
	delete[] visited;
}

int main()
{
	AdjGraph adjGrapth{};
	makeNull(adjGrapth, 9);
	addEdge(adjGrapth, 0, 1);
	addEdge(adjGrapth, 0, 2);
	addEdge(adjGrapth, 1, 3);
	addEdge(adjGrapth, 1, 4);
	addEdge(adjGrapth, 2, 4);
	addEdge(adjGrapth, 2, 5);
	addEdge(adjGrapth, 3, 6);
	addEdge(adjGrapth, 3, 7);
	addEdge(adjGrapth, 4, 7);
	addEdge(adjGrapth, 4, 8);
	addEdge(adjGrapth, 5, 7);
	addEdge(adjGrapth, 6, 7);
	addEdge(adjGrapth, 7, 8);
	printGraph(adjGrapth);
	topologicalSort(adjGrapth);
}

参考二

#include<iostream>
#include<stack>
#define NumVertices 40
using namespace std;
int indegree[9];
struct EdgeNode {
	int adjvex;
	EdgeNode* next;
	EdgeNode(int a,EdgeNode* b):adjvex(a),next(b){}
};
struct VertexData {
	string name;
	EdgeNode* next;
};
struct AdjGraph {//邻接表
	VertexData vexlist[NumVertices];
	int n, e;
};
bool TopologicalSort(AdjGraph& G) {
	stack<int> s;
	int count = 0;
	for (int i = 0; i < 9; i++) {
		if (indegree[i] == 0) {
			s.push(i);
		}
	}
	while (!(s.empty())) {
		int i = s.top();
		s.pop();
		count++;
		cout << i << " ";
		for (EdgeNode* p = G.vexlist[i].next; p; p = p->next) {
			if (!(--indegree[p->adjvex])) {
				s.push(p->adjvex);
			}
		}
	}
	if (count < G.n) {
		cout << "There is cycle on the digraph" << endl;
		return false;
	}
	else
		return true;
}
int main() {
	AdjGraph adjGraph = AdjGraph();
	VertexData vertexData0 = VertexData();
	vertexData0.name = "0";
	vertexData0.next = new EdgeNode(2, NULL);
	vertexData0.next->next = new EdgeNode(1, NULL);

	VertexData vertexData1 = VertexData();
	vertexData1.name = "1";
	vertexData1.next = new EdgeNode(4, NULL);
	vertexData1.next->next = new EdgeNode(3, NULL);

	VertexData vertexData2 = VertexData();
	vertexData2.name = "2";
	vertexData2.next = new EdgeNode(5, NULL);
	vertexData2.next->next = new EdgeNode(4, NULL);

	VertexData vertexData3 = VertexData();
	vertexData3.name = "3";
	vertexData3.next = new EdgeNode(7, NULL);
	vertexData3.next->next = new EdgeNode(6, NULL);

	VertexData vertexData4 = VertexData();
	vertexData4.name = "4";
	vertexData4.next = new EdgeNode(8, NULL);
	vertexData4.next->next = new EdgeNode(7, NULL);

	VertexData vertexData5 = VertexData();
	vertexData5.name = "5";
	vertexData5.next = new EdgeNode(7, NULL);

	VertexData vertexData6 = VertexData();
	vertexData6.name = "6";
	vertexData6.next = new EdgeNode(7, NULL);

	VertexData vertexData7 = VertexData();
	vertexData7.name = "7";
	vertexData7.next = new EdgeNode(8, NULL);

	VertexData vertexData8 = VertexData();
	vertexData8.name = "8";
	vertexData8.next = NULL;
	
	adjGraph.vexlist[0] = vertexData0;
	adjGraph.vexlist[1] = vertexData1;
	adjGraph.vexlist[2] = vertexData2;
	adjGraph.vexlist[3] = vertexData3;
	adjGraph.vexlist[4] = vertexData4;
	adjGraph.vexlist[5] = vertexData5;
	adjGraph.vexlist[6] = vertexData6;
	adjGraph.vexlist[7] = vertexData7;
	adjGraph.vexlist[8] = vertexData8;
	adjGraph.n = 9;
	adjGraph.e = 13;

	indegree[0] = 0;
	indegree[1] = 1;
	indegree[2] = 1;
	indegree[3] = 1;
	indegree[4] = 2;
	indegree[5] = 1;
	indegree[6] = 1;
	indegree[7] = 4;
	indegree[8] = 2;

	TopologicalSort(adjGraph);
}