当前位置：首页 > news >正文

网站建设案例机构4001688688人工服务

news 2025/7/27 12:50:37

网站建设案例机构,4001688688人工服务,在线ps网站,wordpress动态链接301图的遍历是指从某点出发,按照某种搜索方式沿着边访问图中所有节点图的遍历算法主要有两种:广度优先,深度优先都需要辅助数组visited[]来记录节点是否被访问过 6.3.1广度优先搜索 like层次遍历,需要辅助队列代码实现 #include<stdio.h> #define maxnum 15 bool vi…

图的遍历是指从某点出发,按照某种搜索方式沿着边访问图中所有节点

图的遍历算法主要有两种:广度优先,深度优先

都需要辅助数组visited[]来记录节点是否被访问过

6.3.1广度优先搜索

like层次遍历,需要辅助队列

代码实现


#include<stdio.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; p=NextNeighbor(G,i,w)){if (!visited[p]) {visit(p);visited[p] = true;EnQueue(Q, p);}}}}

广度优先遍历过程

从顶点1出发:12563748

从顶点3出发:34678215

性能分析

邻接表和邻接矩阵空间复杂度

邻接表时间复杂度

邻接矩阵的时间复杂度

广度优先生成树

在广度遍历中可以得到一颗遍历树,为广度优先生成树

邻接矩阵唯一,生成树唯一

邻接表不唯一,生成树不唯一

6.3.2深度优先搜索

belike树的先序遍历

代码实现

#include<stdio.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);}
}