c#网站购物车怎么做,制作app下载,网站联系方式要素,西宁城西区建设局网站一、广度优先搜索(BFS)①找到与一个顶点相邻的所有顶点
②标记哪些顶点被访问过
③需要一个辅助队列#define MaxVertexNum 100
bool visited[MaxVertexNum]; //访问标记数组
void BFSTraverse(Graph G){ //对图进行广度优先遍历#xff0c;处理非连通图的函数 for(int i0;i…一、广度优先搜索(BFS)
①找到与一个顶点相邻的所有顶点
②标记哪些顶点被访问过
③需要一个辅助队列#define MaxVertexNum 100
bool visited[MaxVertexNum]; //访问标记数组
void BFSTraverse(Graph G){ //对图进行广度优先遍历处理非连通图的函数 for(int i0;iG.vexnum;i)// 遍历一下所有的 顶点visited[i] false; // 将所有的顶点都 设为 未访问标志。InitQueue(Q); //初始化辅助队列Q for(int i0;iG.vexnum;i)// 从0号顶点开始遍历if(!visited[i]) // 对每个连通分量调用一次BFS() BFS(G,i);
}
void BFS(Graph G,int v){visit(v);visited[V]true; //对v做已访问标记 EnQueue(Q,v); //顶点v入队 while(isEmpty(Q)){Dequeue(Q,v); //队首顶点v出队 //for(wFirstNeighbor(G,v);w0;wNextNeighbor(G,v,w))for(pG.vertices[v].firstarc;p;pp-nextarc){ //检测v的所有邻接点 wp-adjvex;if(visited[w]false){visit(w); //w为v尚未访问的邻接点访问w visited[w]true; // 对w做已访问标记 EnQueue(Q,w); // 顶点w入队 } }}
}无论是邻接矩阵还是邻接表的存储方式BFS算法都需要借助一个辅助队列Q
n个顶点均需要入队一次在最坏的情况下空间复杂度为O(|V|)BFS遍历图的实质就是对每个顶点查找其邻接点的过程耗费时取决于存储结构。
1、采用邻接表存储每个顶点均需搜索或入队一次时间复杂度为O(|V|),在搜索每个顶点的邻接点时
每条边至少被访问一次时间复杂度为O(|E|),总的时间复杂度为 O(|V||E|)
2、采用邻接矩阵存储查找每个顶点的邻接点所需要的时间为O(|V|),总的时间复杂度为O(|V|²) 同一个图的邻接矩阵存储是唯一的所以其广度优先生成树也是唯一的。
但因为邻接表存储表示不唯一所以其广度优先生成树也是不唯一。 广度优先搜索的应用——只可以检测无向图是否有环有向图无法检测
二、深度优先搜索(DFS)
DFS算法是一个递归算法需要借助一个递归工作栈最好的空间复杂度是O(1),最差的空间复杂度是O(|V|)DFS遍历图的实质就是对每个顶点查找其邻接点的过程耗费时取决于存储结构。
1、采用邻接表存储每个顶点均需搜索或入队一次时间复杂度为O(|V|),在搜索每个顶点的邻接点时
每条边至少被访问一次时间复杂度为O(|E|),总的时间复杂度为 O(|V||E|)
2、采用邻接矩阵存储查找每个顶点的邻接点所需要的时间为O(|V|),总的时间复杂度为O(|V|²) #define MAX_VERTEX_NUM 100
bool visited[MAX_VERTEX_NUM]; //访问标记数组
void DFSTraverse(Graph G) //对图进行深度优先遍历
{for(v0;vG.vexnum;i)visited[v]false; //初始化已访问标记数组 for(v0;vG.vexnum;i) //本代码是从v0开始遍历 if(!visited[v]) //对尚未访问的顶点调用DFS() DFS(G,v);
}//用邻接表实现深度优先搜索算法
void DFS(ALGraph G,int v)
{visit(v); visited[v]true;for(pG.vertices[v].firstarc;p;pp-nextarc){ //检测v的所有邻接点 jp-adjvex;if(!visited[w])DFS(G,w); //j为v的尚未访问邻接点递归访问v }}//用邻接矩阵实现深度优先搜索算法
void DFS(MLGraph G,int v)
{visit(v); visited[v]true;for(j0;jG.vexnum;j){ //检测v的所有邻接点 if(visited[j]false G.edge[i][j]1)DFS(G,j); //j为v的尚未访问邻接点递归访问v }}深度优先搜索应用——检测是否有向图/无向图是否有环比如无向图先访问结点1再访问结点2再访问结点5再访问结点3此时结点3有两个邻接点在先访问结点2的情况下发现结点2已经被访问过并且不是结点3的父节点结点3的父节点是它的来时路——结点5。则此时图里存在环。三、图的遍历与连通性1、对于无向图来说若无向图是连通的则从任意一个结点出发仅需一次遍历就能访问图中所有顶点若无向图是非连通的则从某一个顶点出发一次性只能访问到该顶点所在连通分量的所有顶点
2、对于无向图BFSTraverse、 DFSTraverse这两个函数调用BFS、DFS的次数等于该图的连通分量
3、对于有向图来说若从初始顶点到图中的每个顶点都有路径则能够访问到图中的所有顶点否则不能访问到所有顶点。即与是否为强连通图无关
4、对于有向图非强连通分量一次调用不一定能访问到该子图的所有顶点。
