【深基18.例3】查找文献-图的储存与遍历

【深基18.例3】查找文献

题目来源-洛谷

题意：

由文献组成的有向图/树，需要分别深搜和广搜得到查阅结果，其中，同一层级的节点需要排序

思路:

• 如何储存？

  文献比较多,能达到1e5 如果直接邻接矩阵，显然会内存超限。因此选择邻接表来储存,题目不涉及权值，直接储存结点关系即可 vector <int> p[MAXN] 也可以用vector<vector<int>>

• 同一层级如何排序？

  如果想到用set来储存，在遍历时写法稍微复杂，sort可以排序，sort(起始地址（.begin()），末端地址（.end()，排序方式0/1) 默认升序。

• 如何遍历

  • dfs
    ①结束遍历的条件是：该节点被访问过

②由于本题dfs结束的条件是已访问过该节点，所以标记访问的操作应该是在for循环上方区域
cpp void dfs(int node) { //判断是否遍历完一遍 if(结束条件){· return; }else{ for(可选择的范围) if(继续搜索的条件-是否访问过){ 1.标记访问过 2.dfs（下一个） } } }

• bfs
  注意：第一个入队的数据一定要做标记

  void bfs(){
      queue<类型> q;
      第一个数据入队
      while (!q.empty()) {
          int x = q.front();//取队首输出
          q.pop();
          for (可选范围)
          {
              if (未访问过) {
                 1.当前节点入队
                 2. 标记
              }
           }
       }
  }
  

数据约束

注意数组长度即可

参考代码

//P5318 【深基18.例3】查找文献
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+5;
void bfs(int k);
void dfs(int k); 
//邻接表储存数据关系-数据比较大需要储存在外面 
vector<int> p[MAXN] ;
queue <int> q;
//bool f[MAXN][MAXN] = {false};//判断这个点是否被访问过，二维数组会超内存！且没必要 
bool f[MAXN] = {false};//直接储存节点即可 
bool f1[MAXN] = {false};
int m,n;
int main()
{
	int x,y;
	cin>>n>>m;//m条文献 
	for(int i=1;i<=m;i++){
		cin>>x>>y;
		p[x].push_back(y);
	} 
	for(int i=1;i<=n;i++){
		sort(p[i].begin(),p[i].end());//默认升序 
	}
	dfs(1);//dfs遍历输出
	cout<<endl; 
	bfs(1);//bfs遍历输出
//	查看储存的数据是否正确 
//	for(int i=1;i<m;i++){
//		for(int j=0;j<p[i].size();j++){
//			cout<<p[i][j]<<" "; 
//		} 
//		cout<<endl;
//	}
	return 0;
}
void dfs(int k){
	if(f[k]) return;	
	f[k] = true; 			
	 cout<<k<<" ";//跟节点输出 
	for(int i=0;i<p[k].size();i++){
		if(!f[p[k][i]]){ //没被访问过 
			dfs(p[k][i]) ;//访问该节点的子节点 
		}
	}
	return ;
}
void bfs(int k){
	q.push(k);//从顶部开始搜索 
	f1[k] = true;//马上做标记！ 
	while(!q.empty()){
		int t = q.front();//取对头输出 
		q.pop();
		cout<<t<<" ";
		for(int i=0;i<p[t].size();i++){ //孩子节点入队 -是节点t不是k! 
			if(!f1[p[t][i]]){
				q.push(p[t][i]);
				f1[p[t][i]] = true; 
			}
		}
	} 
	return ;
}