苏州网站建设优化,vultr wordpress,品牌网站建设精湛磐石网络,钢材网站建设一.BFS遍历
1.图的广度优先遍历代码实现
说明#xff1a; 1.广度优先遍历#xff0c;类比树的层次遍历#xff08;树属于特殊的图#xff09; 2.对应算法想象图的物理结构存储#xff1a; 邻接矩阵表示唯一时间复杂度#xff1a;O(|V|^2); 邻接表不唯一:O(|V|2|E|) 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(i0;iG.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(wFirstNeighbor(G,v);w0;wNextNeighbor(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(v0;vG.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(wFirstNeighbor(G,v);w0;wNextNeighbor(G,v,w))if(!visited[w]){DFS(G,w);}}
