資料結構與算法：圖的BFS及性能分析

一. 圖的廣度優先周遊

圖的廣度優先周遊可以聯系二叉樹的層序周遊，其基本思想是：首先，通路起始節點v，之後，通路與起始節點v相連的各個未被通路過的節點w1,w2,...,wi，之後，再對這些節點，進行上面的操作。

在分析其算法的時間和空間開銷之前，我們必須知道算法的實作流程：

廣度優先周遊是一種分層查找的過程，與深度優先周遊的不同之處在于，它不需要有退回的情況，是以，它不是一個遞歸的算法。但是，為了實作逐層的通路，我們必須借助輔助隊列來實作

void BFS(Graph G,int v){//從頂點v出發，廣度優先周遊圖G
	visit(v);
	visited[v] = true;
	EnQueue(Q,v);
	while(!isEmpty(Q)){
		DeQueue(Q,v);
		for(w = FirstNeighbor(G,v);w>=0;w = NextNeighbor(G,v,w)){//不斷找到與v節點相鄰的節點
			if(!visited[w]){
				visit(w);
				visited[w] = true;
				EnQueue(Q,w);
			}
		}
	}

void BFSTraverse(Graph G){
	for(int i = 0;i<G.vexnum;i++){//初始化visit數組
		visited[i] = false;
	}
	InitQueue(Q);
	for(int i = 0;i<G.vexnum;i++){
		if(!visited[i]){
		BFS(G,i);
		}
	}
}
           

二. 圖的常見存儲模式

常見的圖的存儲方式有鄰接矩陣存儲和鄰接表存儲，鄰接矩陣是用一維數組存儲節點資訊，用二維數組存儲邊的資訊，時間複雜度為O(V2)，而鄰接表是采用順序存儲圖的節點資訊（頂點表），鍊式存儲圖的邊的資訊（邊表），對于無向圖的情況，由于一條邊會增加節點的兩個度，是以鄰接表存儲無向圖的情況，邊節點的個數為邊數的兩倍，即2E，加之有V個節點，是以鄰接表存儲的空間開銷是O(V+2E)

三. 基于鄰接矩陣和鄰接表的查找

1. FirstNeighbor(G,v)：查找節點v的第一個鄰接點，對于無向圖和有向圖是相同的情況。第一，如果圖是采取鄰接矩陣的存儲模式，那麼最好的情況，就是周遊序列的第一個元素就符合情況，是以，最好情況下的時間複雜度為O(1)，最壞的情況則是要周遊整個圖的節點，此時的時間複雜度為O(n)，而對于鄰接表的存儲，因為邊節點直接展現了節點相連的節點，是以，通過鄰接表查找第一個鄰接點的時間開銷為O(1)（對于有向圖僅是查找出邊的情況）

2. NextNeighbor(G,v,w)：假設節點w是v的第一個鄰接點，該函數傳回除了w以外，與v相連的下一個鄰接點，其時間和空間開銷同上

四. BFS的複雜度分析：

1. 時間複雜度：

首先，我們需要确定BFS周遊的時間開銷來源是什麼，這是最重要的，BFS周遊的時間開銷有二：通路節點+探索邊。通路節點需要周遊整個圖，是以時間複雜度為O(V)，而周遊邊，需要在二維數組中檢視每一個節點與其相連的邊。是以對于鄰接矩陣存儲模式，總的時間開銷為O(V+V2)，保留最大項，為O(V2)，而對于鄰接矩陣存儲，周遊節點的時間複雜度為O(V)，周遊邊則直接周遊邊節點即可，是以周遊邊的時間複雜度為O(E)，故總的時間複雜度為O(V+E)

2. 空間複雜度：

使用了輔助隊列，n個節點均需要入隊一次，故空間複雜度為O(V)