廣度優先演算法的復雜度

『壹』 急！！C++深度優先演算法和廣度優先演算法

以搜索為例，下面兩種介紹了深搜與廣搜的具體實現。
演算法博大精深，望樓主好好學習啊
1. 深度搜索
void Graph::DFS(const int v, int visited[])
{
cout<<GetValue(v)<<"";//訪問頂點 v
visited[v] = 1; //頂點 v 作訪問標記
int w = GetFirstNeighbor(v););//取 v 的第一個鄰接頂點 w
while(w != -1) //若鄰接頂點 w 存在
{
if(!visited[w])//若頂點 w 未訪問過, 遞歸訪問頂點 w
DFS(w, visited);
w = GetNextNeighbor(v, w);//取頂點 v 的排在 w 後面的下一個鄰接頂點
}
}
void Graph::UseDFS()
{
visited = new Boolean[n];
for(int i = 0; i < n; i++)
visited[i] = 0;
DFS(0);
delete[] visited;
}
演算法分析：
(1)圖中有 n 個頂點，e 條邊。
(2)如果用鄰接表表示圖，沿 link 鏈可以找到某個頂點 v 的所有鄰接頂點 w。由於總共有 2e 個邊結點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復雜性為O(n+e)。
(3)如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。
2. 廣度優先搜索
void BFS(Graph G, int visited[])
{//按廣度優先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數組visited.
for(v = 0; v < G.vexnum; v++)
visited[v] = false;
Quene q;
for(v = 0; v < G.vexnum; v++)
if(!visited[v])
{
visited[v] = true;
EnQuene(Q,v);
while(!QueneEmpty(Q))
{
DeQuene(Q,u);
for(w = FirstAdjVex(G, u); w; w = NextAdjVex(G, u, w))
if(!visited[w])
{
visited[w] = true;
EnQuene(Q, w);
}//if
}//while
}//if
}//BFS
演算法分析：
每個頂點至多進一次隊列。遍歷圖的過程實質上是通過邊或弧找鄰接點的過程，因此廣度優先搜索遍歷圖的時間復雜度和深搜相同。