????????拓?fù)渑判蚴且粋€(gè)有向無環(huán)圖（有向圖、弧不形成閉環(huán)）的所有頂點(diǎn)的線性序列。該線性序列中，圖的每個(gè)頂點(diǎn)只出現(xiàn)一次，若頂點(diǎn)A到頂點(diǎn)B之間存在有向弧<v1,v2>,則頂點(diǎn)A一定在頂點(diǎn)B前面。

?

?

????????圖的拓?fù)渑判驅(qū)崿F(xiàn)很簡單，基本操作思想：

? ? ? ? 1、開始時(shí)用一個(gè)輔助數(shù)組記錄各頂點(diǎn)的入度，入度為0的頂點(diǎn)全部入隊(duì)（先進(jìn)先出、輸入頂點(diǎn)）

? ? ? ? 2、將入度為0的頂點(diǎn)逐個(gè)出隊(duì)，出隊(duì)時(shí)，將以他們?yōu)榛∥驳幕〉幕☆^的入度-1，若入度為0，則將弧頭入隊(duì)。重復(fù)入隊(duì)、出隊(duì)，直到所有頂點(diǎn)出隊(duì)完。?

? ? ? ? 圖中只有頂點(diǎn)A的入度為0，將頂點(diǎn)A入隊(duì)；將A出隊(duì)，同時(shí)減少以頂點(diǎn)A為弧尾的弧的弧頭（圖中為頂點(diǎn)2、頂點(diǎn)4）的入度。發(fā)現(xiàn)頂點(diǎn)2的入度為0，將頂點(diǎn)2入隊(duì)。如此重復(fù)入隊(duì)、出隊(duì)，直到所有頂點(diǎn)輸出完。

?

?

?最終的到拓?fù)渑判蚪Y(jié)果：1、2、4、3、5（不唯一）文章來源地址http://www.zghlxwxcb.cn/news/detail-540370.html

// 無回路的有向圖
// 拓?fù)渑判?void TopologicaSort(ALGraph &graph) {
	int Degree[MAX_VERTEX_NUM];	// 記錄各頂點(diǎn)當(dāng)前的入度
	for (int i = 0; i < graph.ver_num; ++i) {
		Degree[i] = 0;
	}
	for (int i = 0; i < graph.ver_num; ++i) {
		ArcNode* T = graph.adj[i].first;
		while (T) {
			++Degree[T->adjIndex];	// 鄰接頂點(diǎn)入度+1
			T = T->Next;
		}
	}
	queue<verType> VERTEX;
	for (int i = 0; i < graph.ver_num; ++i) {
		if (0 == Degree[i]) {
			VERTEX.push(graph.adj[i].vertex);	// 入度為0的頂點(diǎn)入隊(duì)
			break;
		}
	}
	verType vex;
	int index;
	while (!VERTEX.empty()) {
		vex = VERTEX.front();
		VERTEX.pop();
		cout << vex << " ";
		index = LocateVertex(graph, vex);
		if (index < 0) break;
		ArcNode* T = graph.adj[index].first;
		while (T) {
			--Degree[T->adjIndex];
			if (0 == Degree[T->adjIndex]) VERTEX.push(graph.adj[T->adjIndex].vertex);
			T = T->Next;
		}
	}
	cout << endl;
}

到了這里，關(guān)于圖的拓?fù)渑判虻奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！