BFS/DFS的算法开销
- 时间复杂度
来源:访问顶点以及查找顶点的邻接点
-
对于BFS/DFS,如果邻接矩阵表示,则访问顶点为O(|V|),查找顶点邻接点(需要遍历整个矩阵)为O(|V|²)
-
如果是邻接表,则前者为O(|V|),后者为2|E|,也就是O(|E|)
分析的时候不要一味的看代码找循环
- 空间复杂度
BFS:O(|V|):最坏发散的
DFS:O(|V|):最坏连着一串的,最好发散的
BFS/DFS调用次数
- 无向图:
几个连通分量就调用几次
若是连通图,则调用一次即可
- 有向图:
-
具体分析
-
如果起始顶点到其他顶点都有路径,则只调用一次
-
如果是强连通图,则从任意顶点出发都只调用一次
注意:DFS可以用于判断G是否有环:无向图在DFS中遇到回边则说明有环,有向图中回边可能是生成树森林中别的树指向的,也可能是环,因此需要判断一下,但是可以用
2 判断无向图为树
bool isTree(Graph G)
{
for(v=0;v<G.vexnum;v++)
visited[v]=false;
int c=0;
int flag=0;
for(v=0;v<G.vexnum;v++)
{
if(!visited[v])
{
if(c=1)//说明调用过一次了,再调用就是非连通的,不是一棵树
return false;
else
{
DFS(G,v,&flag);
c++;
}
}
}
if(flag==1) return false;
return true;
}
void DFS(Graph G,int v,int &flag)
{
visit(v);
visited[v]=true;
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
{
if(visited[w])//访问过,说明有环
{
flag=1;
}
else
{
DFS(G,w,flag);
}
}
}
3 DFS的非递归实现
void DFS_NotRC(Graph G,int v)
{
int w;
Stack S;
for(w=0;w<G.vexnum;w++)
visited[w]=false;
S.Push(v);visited[v]=true;
while(!S.Isempty())
{
int k=S.Pop();
for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w))
{
if(!visited[w])//未被访问过,入栈,置位true
{
S.Push(w);
visited[w]=true;
}
}
}
}