圖的深度優先搜尋和廣度優先搜尋的總結

昨天讓這兩個搜尋算法搞的萎靡不振的，今天重新來過。其實昨天了解不好的原因還是對圖的存儲結構部了解，上兩篇文章用到的其實圖的鄰接矩陣存儲的。存儲圖一個數組是不夠的需要兩個數組才可以，一個是存儲節點的vex數組，用來控制每個節點都被通路到。第二個就是一個邊關系的二維數組。具體的結構是這樣的

節點數組int vex[] 

1

2

3

4

5

vex[0] = v1;vex[0] = v2;vex[0] = v3;vex[0] = v4;vex[0] = v5;

邊關系數組也就是我們一直說的鄰接矩陣，隻不過是一個二維數組int arc[][],行和列都是代表了節點數組中的節點，是以其最大值也就是vex.length。，arc[i][j]表示的是arc[i]和arc[j]之間的有無邊，若有則等于1，否則為0.了解了這個再去了解DFS和BFS就很輕松了，從DFS開始。

DFS的算法了解思路：

• 開始算法DFSTraverse（），先将每個節點的标記為标記為0
• 周遊節點數組，若通路标記為為0則說明此節點為被通路到，調用DFS(G,I)
• 在DFS中首先通路該節點并将通路為重置為1，此時到了關鍵的地方。現在是已經通路到了節點vi，深度優先搜尋的要求是盡可能深的往下通路，是以這時就用到了鄰接矩陣就是這個二維數組arc[][]，此時我們已經找到了vi，那麼下面就要去找和vi有關的邊，其實就是數組中v[i]這一行，周遊這一行如果有關系則有arc[i][j]=1若此節點未被通路那麼就找到了下一個節點，遞歸調用DFS。

這樣再來分析算法就比較好了解了：

bool visited[max]//通路控制數組
vex[];//頂點元素數組
arc[][];//邊關系矩陣
void DFSTraverse(Grap G){
	for(v=0;v<G.vex.length;++v){
		visited[v] = false;
	}//初始化标記數組

	for(v=0;v<vex.lengthlv++){
		if(!visited[v]){
			DFS(G,v);
		}
	}/周遊每個節點，確定每個節點都被通路到
}

void DFS(Graph G,int v){
	int j;
	visit(v);
	visited[v] = true;

	for(j=0;j<G.vex.length;j++){//周遊arc數組的第i行
		if(G.arc[i][j] == 1 && !visited[j]){
			DFS(G,j);
		}//若vex[j]和vex[i]之間有邊關系，且沒被通路過，則對vex[j]遞歸調用DFS
	}//for
}           

BFS廣度優先搜尋：

和DFS不同廣度優先搜尋類似于層次周遊，直覺的表達就是DFS傾向于找到一個節點就去和這節點有關系（即有邊關系的）的節點，然後再去找和這個新節點有邊關系的節點，是以才得名深度優先搜尋。廣度優先搜尋就是傾向于找到和一點節點有變關系的所有的節點，然後再去找另一個節點有邊關系的所有節點，是以得名廣度優先搜尋。從BFS算法的思路上可以看出，我們要保證先被通路的節點優先，是以選擇輔助隊列。

具體的算法思路如下：

• BFSTraverse開始，初始化标記數組，周遊節點數組，確定每個節點都通路
• 通路該節點的标記為，若為0則通路該節點并重置标記為為1，并入隊列
• 若隊列不空，則說明還有沒周遊的節點則出隊，通路該節點重置标記為，和DFS一樣通路邊關系數組的第i行，當arc[i][j]=1并且未被通路過則通路該節點重置标記為，入棧。

具體的代碼如下：

bollean visited[max];//通路标記數組
Queue Q；//用到的複制隊列
vex[];//頂點數組
arc[][];//邊數組

void BFSTraverse(Graph G){
	for(i=0;i<G.vex.length;i++){
		visisted[i] = false;
	}//初始化标記數組

	for(i=0;i<G.vex.legth;i++){
		if(!visisted[i]){
			BFS(G,i);
		}
	}//周遊節點數組確定每個節點都通路
}//BFSTraverse

void BFS(Graph G,int v){
	visit(v);
	visited[v] = true;
	Q.add(v);

	while(!Q.empty()){
		v = Q.poll();

		for(j=0;j<G.vex.length;j++){
			if(G.arc[i][j]==1 && !visited[j]){
				visited[j] = true;
				visit(G.vex[j]);
				Q.add(j);
			}
		}
	}//while
}//BFS           

這樣算是基本上了解了算法。