前言

在軟件開(kāi)發(fā)、施工過(guò)程、教學(xué)安排等等的一系列活動(dòng)中，往往需要一個(gè)有向無(wú)環(huán)圖來(lái)表示其是否成成功進(jìn)行下去。

在一個(gè)有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)中，我們稱(chēng)為AOV網(wǎng)（Activity On Vertex Network）。設(shè)G={V,E}是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中的頂點(diǎn)序列v1,v2,…,vn,滿(mǎn)足若從頂點(diǎn)vi到vj有一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必在vj之前。則我們稱(chēng)這樣的頂點(diǎn)為一個(gè)拓?fù)湫蛄小?/p>

所謂拓?fù)渑判颍鋵?shí)就是對(duì)一個(gè)有向圖構(gòu)造拓?fù)湫蛄械倪^(guò)程。如果所有的頂點(diǎn)被輸出，則說(shuō)明有向圖中不存在回路，反之則是有回路。

一、拓?fù)渑判蛩惴ǖ乃悸?/h2>

拓?fù)渑判蛲迷谟邢蜞徑颖碇?，這里也就只用有向鄰接表來(lái)實(shí)現(xiàn)。

先找出所有節(jié)點(diǎn)的入度。

再在AOV網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)輸出，然后刪除此頂點(diǎn)，將其連接的節(jié)點(diǎn)的入度減一直至輸出所有頂點(diǎn)或者AOV網(wǎng)中不存在入度為0的頂點(diǎn)為止。

二、實(shí)現(xiàn)步驟

1.求個(gè)頂點(diǎn)的入度

設(shè)置一個(gè)indegree數(shù)組來(lái)存放各個(gè)頂點(diǎn)的入度。

int* indegree = (int*)malloc(sizeof(int) * G.vexnum);
//對(duì)單個(gè)節(jié)點(diǎn)p求入度
void CountIndegree(AdjList g, int* indegree, ArcNode* p) {
	while (p != NULL) {
		indegree[p->adjvex]++;
		p = p->nextarc;
	}
	return;
}

2.拓?fù)渑判虻膶?shí)現(xiàn)

這里對(duì)棧的使用還是調(diào)用stl中的stack，比較方便。

bool TopoSort(AdjList g, int* indegree) {
	//先清空申請(qǐng)的indegree數(shù)組，或者也可以在初始化時(shí)采用calloc，就不用在這里置為0了
	for (int i = 0; i < g.vexnum; i++) {
		indegree[i] = 0;
	}
	//遍歷邊表中的每一個(gè)頂點(diǎn)，用CountIndegree()遍歷單個(gè)節(jié)點(diǎn)
	for (int i = 0; i < g.vexnum; i++) {
		ArcNode* p = g.vertexlist[i].firstarc;
		CountIndegree(g, indegree, p);
	}
	stack<int>S;
	//如果該頂點(diǎn)的入度為0，則入棧。
	for (int i = 0; i < g.vexnum; i++) {
		if (indegree[i] == 0) {
			S.push(i);
		}
	}
	//count用來(lái)表示已經(jīng)輸出的節(jié)點(diǎn)個(gè)數(shù)
	//如果所有的頂點(diǎn)被輸出，則count==g.vexnum，無(wú)回路，反之count<g.vexnum,則是有回路。
	int count = 0;
	while (!S.empty()) {
		int top = S.top();
		printf("%c ", g.vertexlist[top].data);
		S.pop();
		count++;
		ArcNode* p = g.vertexlist[top].firstarc;
		for (p; p != NULL; p = p->nextarc) {
			int i = p->adjvex;
			if (--indegree[i] == 0) {
				S.push(i);
			}
		}
	}
	if (count == g.vexnum) {
		return true;
	}
	return false;
}

三、測(cè)試結(jié)果

自己花了一個(gè)看起來(lái)挺復(fù)雜的圖，一下也看不出來(lái)有沒(méi)有環(huán)

首先算一算入度，順帶打印一下。

接下來(lái)是拓?fù)渑判虻慕Y(jié)果

完美！

總結(jié)

每個(gè)頂點(diǎn)進(jìn)棧一次出戰(zhàn)一次，度減一的操作執(zhí)行了e次，所以整個(gè)算法的時(shí)間復(fù)雜度為O(n+e)。

到此這篇關(guān)于C/C++淺析鄰接表拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++拓?fù)渑判騼?nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論