广度优先搜索BFS
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G){
for(i=0;i<G.vexnum;++i)
visited[i]=FALSE;
InitQueue(Q);
for(i=0;i<G.vexnum;++i)
if(!visited[i]) //对每个连通分量调用一次BFS
BFS(G, i);
}
//先访问再入队,出队的时候再把未被访问过的邻接点都访问并入队
void BFS(Graph G, int v){
visited(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))
if(!visited[w]){
visited(w);
visited[w]=TRUE;
EnQueue(Q, w);
}
}
}
空间复杂度 O(|V|)
时间复杂度 邻接表O(|V|+|E|)
邻接矩阵O(|V|^2)
BFS求单源最短路径
void BFS_MIN_Distance(Graph G, int u)
{
for(i=0;i<G.vexnum;++i)
d[i]=∞;
visited[u]=TRUE;
d[u]=0;
EnQueue(Q, u);
while(!isEmpty(Q)){
DeQueue(Q, u);
for(w=FirstNeighbor(G, u);w>=0;w=NextNeighbor(G, u, w))
if(!visited[w]){
visited[w]=TRUE;
d[w]=d[u]+1;
EnQueue(Q, w)
}
}
}
深度优先搜索DFS
bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G)
{
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE;
for(v=0;v<G.vexnum;++v)
if(!visited[v])
DFS(G, v);
}
void DFS(Graph G, int v)
{
visited(v);
visited[v]=TRUE;
for(w=FirstNeighbor(G, v);w>=0;w=NextNeighbor(G, v, w))
if(!visited[w]){
DFS(G, w);
}
}
空间复杂度 O(|V|)
时间复杂度 邻接表O(|V|+|E|)
邻接矩阵O(|V|^2)
注意:图的邻接矩阵表示是唯一的,但对于邻接表来说,若边的输入次序不同,生成的邻接表也不同。因此,对于同一个图,基于邻接矩阵的遍历所得到的DFS序列和BFS序列唯一,但基于邻接表的不唯一。(生成树也不唯一)
连通图可得到广度/深度优先生成树,否则产生生成森林。
网友评论