检测网站名 注册,用python做网站我那些,安徽合肥制作网站公司哪家好,网站的页面动态需要哪些方法做图的遍历是指从某点出发,按照某种搜索方式沿着边访问图中所有节点
图的遍历算法主要有两种:广度优先,深度优先
都需要辅助数组visited[]来记录节点是否被访问过
6.3.1广度优先搜索
like层次遍历,需要辅助队列
代码实现 #includestdio.h
#define maxnum 15
bool vi…图的遍历是指从某点出发,按照某种搜索方式沿着边访问图中所有节点
图的遍历算法主要有两种:广度优先,深度优先
都需要辅助数组visited[]来记录节点是否被访问过
6.3.1广度优先搜索
like层次遍历,需要辅助队列
代码实现 #includestdio.h
#define maxnum 15
bool visited[maxnum];//定义辅助数组
void BFSTraverse(Graph G) {for (int i 0; i G.vexnum; i){visited[i] false;}//初始化数组initQueue(Q);//初始化队列for (int i 0; i G.vexnum; i)//从0号顶点开始遍历{if (!visited[i]) {BFS(G,i);//广度优先遍历}}
}
void BFS(Graph G,int i){visit(i);//访问visited[i] true;//改为tEnQueue(Q,i);//入队while (!isEmpty(Q)) {//判断队列是否为空DeQueue(Q,i);//输出队列第一个元素for ( p FirstNeghbor(G,i); p 0; pNextNeighbor(G,i,w)){if (!visited[p]) {visit(p);visited[p] true;EnQueue(Q, p);}}}} 广度优先遍历过程 从顶点1出发:12563748
从顶点3出发:34678215
性能分析
邻接表和邻接矩阵空间复杂度
邻接表时间复杂度
邻接矩阵的时间复杂度
广度优先生成树
在广度遍历中可以得到一颗遍历树,为广度优先生成树
邻接矩阵唯一,生成树唯一
邻接表不唯一,生成树不唯一 6.3.2深度优先搜索
belike树的先序遍历
代码实现
#includestdio.h
#define maxnum 15
bool visited[maxnum];//定义辅助数组
void DFSTraverse(Graph G) {for (int i 0; i G.vexnum; i){visited[i] false;}//初始化数组for (int i 0; i G.vexnum; i)//从0号顶点开始遍历{if (!visited[i]) {DFS(G, i);//深度优先遍历}}
}
void DFS(Graph G, int i) {visit(i);//访问visited[i] true;//改为tfor (p FirstNeghbor(G, i); p 0; p NextNeighbor(G, i, w)){if (!visited[p]) {DFS(G, p);}
}
深度优先遍历过程 从2出发:21563478
从3出发:34762158
性能分析 深度优先生成树和生成森林
非连通图可通过深度优先产生n棵生产树 6.3.3图的遍历与图的连通性
to无向图:调用DFS/BFS的次数连通分量数
to有向图:强连通分量只调用一次DFS/BFS;
若从起始节点到其他节点都有路径,则只需调用一次
