图的遍历（DFS与ＢＦＳ）

2019-11-08 00:59:04

字体：大中小

来源：转载

供稿：网友

一、深度优先遍历（DFS）

基本思想：从图中某个顶点Vo出发，访问此顶点，然后依次从Vo的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和Vo有路径相通的顶点都被访问到。

代码（递归用vector存）

<php>const int MAXN=1010;vector <int> g[MAXN];//存储边bool visited [MAXN];//节点是否被访问void dfs(int x) {visited[x]=true;//标记x被访问 for(int i=0;i<g[x].size();i++) if(!visited[i]) dfs(i);//遍历x的相邻结点，若没被访问则从这个结点开始深搜遍历 }

二、广度优先遍历（BFS）

从某个顶点Vo出发，并在访问此顶点之后依次访问Vo的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和Vo有路径相通的顶点都被访问到。

代码（用队列）

<php>const int MAXN=1000+5;vector <int> g[MAXN];//存储边queue<int> q;bool visited[MAXN];//是否被访问for(int i=1;i<=MAXN;i++)g[i].clear();while(!q.empty())q.pop();//移除队列第一个元素memset(visited,0,sizeof(visited));void bfs() {visited[1]=1;//初始结点进入队列 q.push(1); while(!q.empty())//队列为空时结束遍历 {int t=q.front(); q.pop(); for(int i=0;i<g[t].size();i++)//寻找队头元素的相邻结点并弹出队头元素 if(!visited[i])//访问相邻结点并使之入队 {q.push(i); visited[i]=1; } } }

三、vector 容器

①头文件 #include ②创建vector对象 vector vec; ③尾部插入数字 vec.push_back(a); 清空 vec.clear(); 大小 vec.size(); ④使用迭代器访问元素 vector::iterator it; for(it=vec.begin();it!=vec.end();it++) cout<< *it; ⑤在第i个元素前插入新元素a vec.insert(vec.begin()+i,a); 删掉某个元素（从0开始删掉第i个） vec.erase(v.begin()+i); (删除一段) vec.erase(v.begin()+i;v.begin()+j); ⑥用sort排序（升序） #include sort(vec.begin(),vec.end());

上一篇：多线程---线程通信

下一篇：算法训练字串逆序

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注