5.2图的BFS与DFS遍历

一.BFS遍历

1.图的广度优先遍历代码实现

说明：
1.广度优先遍历，类比树的层次遍历（树属于特殊的图）
2.对应算法想象图的物理结构存储：
邻接矩阵表示唯一时间复杂度：O(|V|^2);
邻接表不唯一:O(|V|+2|E|)）
3.空间复杂度分析：
最坏情况：入队操作最大：O(|v|)

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])//对每一个连通分量进行一次BFSBFS(G,i);}
}
//下面代码仅针对于连通图
void BFS(Graph,int v){//从以前顶点v的代码入口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);}}}
}

2.广度优先生成树

一个连通分量——>广度优先生成树
多个连通分量——>广度优先生成森林

二.DFS遍历

复杂度分析：
空间复杂度O(|V|)依据栈的深度建立
时间复杂度，依据物理存储结构的建立

1.图的深度优先遍历代码实现

类比树的先根遍历

void PreOrder(TreeNode *R){if(R!=NULL){    visit(R);while(R->child!=NULL)PreOrder(T);}
}

代码实现

//前置代码，针对于非连通图
void DFSTraverse(Graph G)
{for (i = 0; i <G.vexnum;++i)visited[i]=FALSE;//InitQueue(Q);for(v=0;v<G.vexnum;++v){if(!visited[v])//对每一个连通分量进行一次BFSDFS(G,v);}
}
//图的深度优先遍历
bool visited[MAX_VERTEX_NUM];//访问标记数组
void DFS(Graph G,int v){visit(v);visited[v]=TRUE;for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))if(!visited[w]){DFS(G,w);}}