题目描述
请对这个图分别进行 DFS 和 BFS，并输出遍历结果。如果有很多篇文章可以参阅，请先看编号较小的那篇(因此你可能需要先排序)。
输入
8 9 1 2 1 3 1 4 2 5 2 6 3 7 4 7 4 8 7 8
输出
1 2 5 6 3 7 8 4 1 2 3 4 5 6 7 8
思路:DFS+BFS+图的存储 这个题中在搜索过程中需要不断的判断两点之间的边是否存在,所以应该使用邻接矩阵,但由于数据量太多,所以邻接矩阵也是不行的.我们可以使用vector.然后用一种新的方法来存储图.
首先，我们用一个结构体vector（为了节省空间，咱用vector来存）存储每个边的起点和终点，然后用一个二维vector（也就是一个vector数组）存储边的信息。
我们用e[a][b]=c，来表示顶点a的第b条边是c号边。咱举个栗子，还是拿样例说吧：
8 9 1 2 //0号边（由于vector的下标是从0开始的，咱就“入乡随俗”，从0开始） 1 3 //1号边 1 4 //2号边 2 5 //3号边 2 6 //4号边 3 7 //5号边 4 7 //6号边 4 8 //7号边 7 8 //8号边
最后二维vector中的存储会如下所示：
0 1 2 //1号顶点连着0、1、2号边 3 4 //2号顶点连着3、4号边 5 //3号顶点连着5号边 6 7 //4号顶点连着6、7号边 //5号顶点没有边 //6号顶点没有边 8 //7号顶点连着8号边 //8号顶点没有边
- 别忘了题目要求：“如果有很多篇文章可以参阅，请先看编号较小的那篇”
那就排序呗！咱们按照题目要求,如果起始点相同则先终点从小到大进行排列,如果起始点不同则起始点从小到大排列.(这里的理解可能有问题,看出来的兄弟,可以说说自己的想法)
参考代码
#include<bits/stdc++.h> using namespace std; const int maxn = 100000+10; int n,m,vex[maxn],visited1[maxn],visited2[maxn],u2,v2; struct edge{ int u,v; edge(int u1,int v1):u(u1),v(v1){//构造方法 }; }; vector<edge> s; vector<int> e[maxn]; bool cmp(edge X,edge Y){//用于排序 // if(X.v==Y.v){ // return X.u<Y.u; // }else{ // return X.v < Y.v; // } if(X.u==Y.u){ return X.v < Y.v; }else{ return X.u < Y.u; } } void dfs(int x){ cout<<x<<" "; visited1[x] = 1; for(int i = 0; i < e[x].size(); i++){// i:代表e下表 int w = e[x][i]; if(!visited1[w])//没有被访问 { dfs(w); } } } void bfs(int x){ queue<int> Q; Q.push(x); visited2[x] = 1; while(!Q.empty()){ int temp = Q.front(); Q.pop(); cout<<temp<<" "; for(int i = 0; i < e[temp].size(); i++){ int w = e[temp][i]; if(!visited2[w]){ Q.push(w); visited2[w] = 1; } } } } int main() { cin>>n>>m; while(m--){ cin>>u2>>v2; s.push_back(edge(u2,v2));//将边放到s中 } sort(s.begin(),s.end(),cmp);//进行排序 按照终点从小到大进行排序,如果终点相同则按照起始点从 小到大进行排序 (后面) // for(int i = 0; i < s.size(); i++){ // cout<<s[i].u<<"--"<<s[i].v<<endl; // } for(int i = 0;i<s.size(); i++) //vector 用s对邻接表进行初始化(这是一个由vector构成的邻接表) { e[s[i].u].push_back(s[i].v); } dfs(1); cout<<endl; bfs(1); cout<<endl; return 0; }
