# 第五章：图（图的遍历操作）

## 1.图的遍历 ## 2.广度优先搜索(BFS)

• 首先访问起始顶点v
• 接着由v出发依次访问v的各个 未被访问过 的邻接顶点w1,w1....wi
• 然后依次访问w1,w2....wi的所有 未被访问过 的邻接顶点
• 在从这些访问过的顶点出发,访问它们所有 未被访问过 的邻接顶点
• 以此类推 bool visited[MAX_TREE_SIZE]
void BFSTraverse(Graph G){
for(int i=0; i<G.vexnum;i++){
visited[i]=FALSE;
}
InitQueue(Q);
//for循环的作用，我们上面讲的是一个连通图，所有顶点都可以通过一个顶点依次进行访问
//但是如果一个图不是连通的，我们需要遍历所有顶点
for(int i=0;i<G.vexnum;i++){
if(!visited(i)){
BFS(G,i);
}
}
}
//广度优先搜索
void BFS(Graph G,int V){
visit(v); //访问
visited=TRUE; //TRUE 入队了，FALSE未入队
EnQueue(Q,v); //将结点入队
while(!isEmpty(Q)){ //判断队列是否是空
DeQueue(Q,v); //出队队首元素，并赋值到v中
//FirstNeighbor 求图G中顶点x的第一个邻接顶点，存在返回顶点号，不存在返-1
//判断 w是否大于0，如果是-1则说明没有邻接顶点了
//NextNeighbor 求图G中顶点v的的下一个邻接顶点并赋值给w
for(int w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w)){
if(!visited[w]){//判断是否入队过
visit[w];
visited[w]=TRUE;
EnQueue(Q,w);
}
}
}
}


## 3.应用

### 3.1无权图单源最短路径问题

//和广度优先搜索相似，增加了保存最短路径的一个数组
void BFS_MIN_Distance(Graph G,int u){//传入图 和 初始顶点
for(int i=0;i<G.vexnum;++i){ //
d[i]=MAX; //保存最短路径的值，我们初始化为最大值
}
visited[u]=TRUE;//标识为该顶点已经入队
d[u]=0;//初始顶点路径值改为0
EnQueue(Q,u);//入队
while(!isEmpty(Q)){//判断队列时候为空
DeQueue(Q,u);//出队队首元素
//FirstNeighbor 求图G中顶点x的第一个邻接顶点，存在返回顶点号，不存在返-1
//判断 w是否大于0，如果是-1则说明没有邻接顶点了
//NextNeighbor 求图G中顶点v的的下一个邻接顶点并赋值给w
for(int w=FirstNeighbor(G,u);w>0;w=NextNeighbor(G,u,w)){
if(!visit[w]){//判断该顶点是否已经被访问过
visited[w]=TRUE;//设置被访问过
//d[u]表示到初始顶点的最短路径，w是它的邻接点，所以+1等目前w到初始顶点的最短路径
d[w]=d[u]+1;
EnQueue(Q,w);//入队
}
}
}
}


### 3.2广度优先生成树

连通图：任意两个结点都是连通的 ## 4.深度优先搜索(DFS) • 首先访问起始顶点v
• 接着由v出发访问v的任意一个邻接且未被访问的邻接顶点Wi
• 然后再访问与Wi邻接且未被访问的任意顶点Yi
• 若Wi没有邻接且未被访问的顶点时,退回到它的上一层顶点v
• 重复上述过程,直到所有顶点被访问为止 bool visited[MAX_TREE_SIZE]//辅助标记数组
void DFSTraverse(Graph G){
for(int i=0;i<G.vexnum;i++){
visited[i]=FALSE;//初始化所有结点都未必访问
}
for(int i=0;i<G.vexnum;i++){
if(!visited[i]){//如果结点未被访问
DFS(G,i);//G：图，i：起始顶点的编号
}
}
}
void DFS(Graph G,int v){
visit(v); //访问
visited[v]=TRUE;//置为访问过
for(int w=FirstNeighbor(G,v);w>0;w=NextNeighbor(G,v,w)){
if(!visit[w]){//判断该顶点是否已经被访问过
DFS(G,w);//递归
}
}
} ## 5.深度优先生成树 ## 6.遍历与连通性问题 ## 7.理木客
{"ft_lang_label":"__label__zh","ft_lang_prob":0.94104683,"math_prob":0.9836099,"size":4558,"snap":"2020-45-2020-50","text_gpt3_token_len":3882,"char_repetition_ratio":0.09486166,"word_repetition_ratio":0.019480519,"special_character_ratio":0.2424309,"punctuation_ratio":0.1389271,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9619521,"pos_list":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26],"im_url_duplicate_count":[null,1,null,4,null,1,null,4,null,1,null,1,null,4,null,1,null,1,null,4,null,1,null,1,null,6,null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2020-11-26T20:33:38Z\",\"WARC-Record-ID\":\"<urn:uuid:205a0da2-00cc-42e6-b45e-03dcb0a0e668>\",\"Content-Length\":\"156040\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:a61a78a0-d99a-45c4-866d-581dccc1a017>\",\"WARC-Concurrent-To\":\"<urn:uuid:9ec13f87-8df1-4f06-a3c3-7f6744e43418>\",\"WARC-IP-Address\":\"123.56.170.149\",\"WARC-Target-URI\":\"https://www.limuke.top/archives/data-structure-20\",\"WARC-Payload-Digest\":\"sha1:VUSCFMLAFKBJREXQFRYDUJV6G27KCSLC\",\"WARC-Block-Digest\":\"sha1:WQTG5RNC2FV4Q5A2VASGTF2CAEM3GGC5\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2020/CC-MAIN-2020-50/CC-MAIN-2020-50_segments_1606141188947.19_warc_CC-MAIN-20201126200910-20201126230910-00559.warc.gz\"}"}