前言

拓?fù)渑判蚴欠浅Ｖ匾囊徊糠?，希望大家都能夠手撕代碼?。。。ê俸俸伲?/h3>

---

一、拓?fù)渑判蚨x（百度須知嘿嘿嘿）

拓?fù)渑判?br> 拓?fù)渑判蚴且环N對(duì)有向無(wú)環(huán)圖（Directed Acyclic Graph，簡(jiǎn)稱DAG）進(jìn)行的排序過(guò)程，目的是將圖中所有的頂點(diǎn)按照發(fā)生事件的順序排成一條線性序列。這種排序確保了圖中任意兩個(gè)相鄰頂點(diǎn)之間至少有一條邊相連，且在這條邊的方向上，這條邊的終點(diǎn)在前于起點(diǎn)。拓?fù)渑判虻囊粋€(gè)關(guān)鍵特性是，它只包含在一個(gè)頂點(diǎn)在其事件序列中出現(xiàn)的次數(shù)，這意味著每個(gè)頂點(diǎn)只會(huì)出現(xiàn)一次。

要執(zhí)行拓?fù)渑判颍梢詮腄AG圖的任一頂點(diǎn)開始，選擇出度為0的頂點(diǎn)作為“根”，并將它們放入隊(duì)列。然后，從隊(duì)列中取出頂點(diǎn)，將其事件序列中的下一個(gè)頂點(diǎn)加入隊(duì)列，同時(shí)移除與該頂點(diǎn)相關(guān)的所有邊。這個(gè)過(guò)程會(huì)一直持續(xù)直到隊(duì)列為空或者到達(dá)了一個(gè)沒(méi)有前驅(qū)頂點(diǎn)的狀態(tài)，此時(shí)就得到了該DAG的拓?fù)渑判颉?/p>

在實(shí)際應(yīng)用中，拓?fù)渑判蚩梢杂糜诖_定哪些活動(dòng)可以在給定的順序下并發(fā)執(zhí)行，因?yàn)橹挥心切┰谔囟樞蛳聸](méi)有依賴關(guān)系的活動(dòng)才能一起運(yùn)行。例如，在AOV網(wǎng)中，如果沒(méi)有回路，所有活動(dòng)都可以按照拓?fù)湫蛄信帕?，從而形成一個(gè)線性序列，使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都在其前面。1

總結(jié)來(lái)說(shuō)，拓?fù)渑判蚴且环N用于確定有向無(wú)環(huán)圖中頂點(diǎn)順序的方法，確保每個(gè)頂點(diǎn)只出現(xiàn)一次，并且遵循特定的事件發(fā)生順序。這種方法對(duì)于分析并發(fā)執(zhí)行的活動(dòng)順序非常有用。

二、例題

1.有向圖的拓?fù)渑判?/h3>

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-817550.html

2.AC代碼：

//圖的拓?fù)湫蛄兄会槍?duì)有向圖
//有向無(wú)環(huán)圖被稱為拓?fù)鋱D
//一個(gè)點(diǎn)的入度是指有多少條邊是指向自己
//一個(gè)點(diǎn)有幾條邊出去就是這個(gè)點(diǎn)的出度
//一個(gè)有向無(wú)環(huán)圖一定至少存在一個(gè)入度為0的點(diǎn)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
//q是寬搜隊(duì)列,d是這個(gè)點(diǎn)的入度

void add(int a, int b) {//鄰接表
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}

bool topsort() {
	int hh = 0, tt = -1;
	for (int i = 1; i <= n; i++)
		if (!d[i]) //如果這個(gè)點(diǎn)存在入度
			q[++tt] = i;//就把這個(gè)點(diǎn)加到隊(duì)列里
	while (hh <= tt) {
		int t = q[hh++];//取出隊(duì)頭元素
		for (int i = h[t]; i != -1; i = ne[i]) {//拓展隊(duì)頭元素
			int j = e[i];//找到出邊
			d[j]--;//刪掉入邊
			if (d[j] == 0) //如果這個(gè)點(diǎn)的入度全部被刪掉了
				q[++tt] = j;//就讓這個(gè)點(diǎn)入隊(duì)
		}
	}
	//判斷所有點(diǎn)是否已經(jīng)全部入隊(duì)
	return tt == n - 1; //返回隊(duì)列里元素的數(shù)量是否等于n-1
}

int main() {
	cin >> n >> m;
	memset(h, -1, sizeof h);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		add(a, b); //插入一條a->b的有向邊
		d[b]++;//b的入度加一
	}
	if (topsort()) {//如果存在拓?fù)湫?		for (int i = 0; i < n; i++)
			printf("%d ", q[i]);
		puts("");
	} else {
		puts("-1");
	}
	return 0;
}

總結(jié)

拓?fù)渑判蚩赡軙?huì)經(jīng)常用到，希望大家能夠完全掌握?。?！

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