Question

急！！C++深度优先算法和广度优先算法

Answer 1

以搜索为例，下面两种介绍了深搜与广搜的具体实现。
算法博大精深，望楼主好好学习啊
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
算法分析：
每个顶点至多进一次队列。遍历图的过程实质上是通过边或弧找邻接点的过程，因此广度优先搜索遍历图的时间复杂度和深搜相同。