图的深度优先遍历(DFS)和广度优先遍历(BFS)

body, table{font-family: 微软雅黑; font-size: 13.5pt}
table{border-collapse: collapse; border: solid gray; border-width: 2px 0 2px 0;}
th{border: 1px solid gray; padding: 4px; background-color: #DDD;}
td{border: 1px solid gray; padding: 4px;}
tr:nth-child(2n){background-color: #f8f8f8;}

  从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traversing Graph)
****注:图的建立上一篇博客《图的邻接矩阵存储实现》已经放了源代码了,这里要运行只要按代码加上相应的文件就能执行****

深度优先遍历(DFS,Depth_First_Search):
  从图中某个顶点V出发,访问此顶点,然后从V的未被访问的邻接点触犯深度优先遍历图,直至图中所有和V有路径相通的顶点都被访问到。相当于树的前序遍历。针对非连通图,只要对每个连通分量分别进行深度优先遍历,即在先前一个顶点进行一次深度优先遍历后,若图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点,重复上述过程,直至图中所有顶点都被访问到为止。
图的深度优先遍历(DFS)和广度优先遍历(BFS)
右图是递归遍历的过程,其实每一层都是从A结点开始搜寻满足条件的点
图的深度优先遍历(DFS)和广度优先遍历(BFS)
/* DFS.h */
#ifndef __DFS_H__
#define __DFS_H__
#include"Graph.h"
namespace meihao
{
        void DFS(const meihao::Graph& g,int vi,bool*& visited);  //参数->图和顶点数组中某个顶点的下标
        void DFSTraversal(const meihao::Graph& g);
};
#endif

/* testMain.cpp */
#include"DFS.h"
#include<iostream>
int main()
{
        meihao::Graph g("data.txt");
        meihao::DFSTraversal(g);
        cout<<endl;
        system("pause");
}
图的深度优先遍历(DFS)和广度优先遍历(BFS)

/* data.txt */
9
A B C D E F G H I
0 1 0 0 0 1 0 0 0
1 0 1 0 0 0 1 0 1
0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 1 1 1
0 0 0 1 0 1 0 1 0
1 0 0 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0
0 0 0 1 1 0 1 0 0
0 1 1 1 0 0 0 0 0 
/* DFS.cpp */
#include"DFS.h"
namespace meihao
{
//算法都是基于邻接矩阵实现的
        void DFS(const meihao::Graph& g,int vi,bool*& visited)
        {
                visited[vi] = true;  //修改第vi个结点的访问标记为true
                cout<<g.getGraphVertexData(vi)<<" ";
                for(int idx=0;idx!=g.getGraphVertexNumber();++idx)
                {
                        if(1==g.getGraphEdgeWeight(vi,idx)&&
                                false==visited[idx])  //如果(vi,idx)之间存在边(==1),并且第idx个顶点还没有访问过
                        {
                                DFS(g,idx,visited);  //递归遍历第idx个顶点
                        }
                }
        }
        void DFSTraversal(const meihao::Graph& g)
        {
                bool* visited = new bool[g.getGraphVertexNumber()]();
                for(int idx=0;idx!=g.getGraphVertexNumber();++idx)
                {
                        visited[idx] = false;  //初始化访问标记,全部为false,表示未访问
                }
                for(int idx=0;idx!=g.getGraphVertexNumber();++idx)
                {
                        if(false==visited[idx])  //随便选一个点,如果未访问过,就从它开始深度优先遍历
                                DFS(g,idx,visited);
                }
        }
};
广度优先遍历(Breadth First Search):
 类似于图的层序遍历,
图的深度优先遍历(DFS)和广度优先遍历(BFS) 图的深度优先遍历(DFS)和广度优先遍历(BFS)
/* BFS.h */
#ifndef __BFS_H__
#define __BFS_H__
#include"Graph.h"
namespace meihao
{
        void BFSTraversal(const meihao::Graph& g);
};
#endif

/* test.cpp */
#include"BFS.h"
#include<iostream>
int main()
{
        meihao::Graph g("data.txt");
        meihao::BFSTraversal(g);
        cout<<endl;
        system("pause");
}
图的深度优先遍历(DFS)和广度优先遍历(BFS)

/* data.txt */
9
A B C D E F G H I
0 1 0 0 0 1 0 0 0
1 0 1 0 0 0 1 0 1
0 1 0 1 0 0 0 0 1
0 0 1 0 1 0 1 1 1
0 0 0 1 0 1 0 1 0
1 0 0 0 1 0 1 0 0
0 1 0 1 0 1 0 1 0
0 0 0 1 1 0 1 0 0
0 1 1 1 0 0 0 0 0 
/* BFS.cpp */
#include"BFS.h"
#include<queue>
namespace meihao
{
        void BFSTraversal(const meihao::Graph& g)
        { //广度优先遍历相当于层序遍历
                queue<int> rootNode;  //存放图的顶点
                bool* visited = new bool[g.getGraphVertexNumber()];
                for(int idx=0;idx!=g.getGraphVertexNumber();++idx)
                {
                        visited[idx] = false;
                }
                for(int idx=0;idx!=g.getGraphVertexNumber();++idx)
                { //if语句可以确保如果图中有多个连通分量,也能每个点都访问到
                        if(false==visited[idx])  //如果该结点没有访问到
                        {
                                //访问
                                cout<<g.getGraphVertexData(idx)<<" ";
                                visited[idx] = true;
                                rootNode.push(idx);
                                while(!rootNode.empty())  //把刚刚访问到的结点的下一层结点访问并入队列
                                {
                                        for(int iidx=0;iidx!=g.getGraphVertexNumber();++iidx)
                                        {
                                                if(1==g.getGraphEdgeWeight(rootNode.front(),iidx)&&
                                                        false==visited[iidx])
                                                {
                                                        cout<<g.getGraphVertexData(iidx)<<" ";
                                                        visited[iidx] = true;
                                                        rootNode.push(iidx);
                                                }
                                        }
                                        rootNode.pop();  //最先访问的一个结点出队列
                                }
                        }
                }
        }
};

两种遍历算法在时间复杂度上是一样的
深度优先遍历算法适合图和边都非常多,要找到合适的顶点
广度优先遍历算法适合不断扩大遍历范围时找到相对最优
上一篇:Matlab编辑器背景修改


下一篇:python利用Remove.bg接口自动去背景