图/树的搜索/存储/拓扑排序

深度优先搜索

• 一条路走到黑
• 回溯/剪枝
• 每一个dfs都对应一个搜索树
• 解决全排列，搜索所有可能解

• 一层一层搜索
• 解决最短路问题

树与图的存储

• 有向图/树

  • 每条边建一次

    add(a, b);
    

  • 存储：

    • 邻接矩阵：

      • 存稠密图，无法存重边，浪费空间

    • 邻接表：

      • 单链表数组，有几个点就开几个单链表，每个单链表存储该点可以到的点

      • 代码：

        //h[i]存储以节点i为起点的单链表，单链表中的节点存的是节点i能够到达的所有节点
        //以节点的编号代指结点，但是节点有两类，一类是图中的节点，一类是链表中的节点
        //idx分配单链表中的节点的编号，而不是图中节点的编号，注意区分
        //h[i]中的i是图中节点的编号，存的是单链表节点编号
        //e[i]中的i是单链表中节点的编号，存的是图中节点的编号，e[i]表示i节点存储的图中的节点
        //ne[i]中的i是单链表中节点的编号，存的是单链表点的编号，ne[i]表示i节点的下一个链表节点
        //链表节点下标以1开始，0表示空节点
        int h[N], e[N], ne[N], idx = 1;
        
        void add(int a, int b){//插入节点a指向b的一条边
        	e[idx] = b;//单链表节点的值就是图中节点
        	ne[idx] = h[a];
        	h[a] = idx;
        	idx ++ ;
        }
        

• 无向图/树

  • 每条边建两次

    add(a, b);
    add(b, a);
    

树与图的深度优先遍历

• 有向图/树的深度优先遍历

• 树的优先遍历可以求出子树的节点数
• 代码：

  bool st[N];//标记是否被访问过
  void dfs(int u){
  	st[u] = true; //设置为已标记
  	for(int i = h[u]; i; i = ne[i]){ //遍历节点u的单链表
  		int j = e[i]; //取链表节点的值(图中节点的编号)
  		if(!st[j]) dfs(j); //没有被访问过就访问
  	}
  }
  

树与图的宽度优先遍历

• 有向图/树的宽度优先遍历

拓扑排序

• 拓扑排序是一个有向无环图的所有顶点的线性序列。且该序列必须满足下面两个条件：
• 每个顶点出现且只出现一次。
• 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
• 只要图中有环，那么该图不存在拓扑序列
• 拓扑序不唯一
• 代码：

  //将所有入度为0的节点i优先入队
  //删除以节点i为起点j为终点的所有边，同时更新j的入度
  //再次将所有入度为0的节点j入队
  //建图步骤省略
  int q[N], hh, tt = -1;//队列
  int d[N];//存储每个节点的入度
  //初始化入度与图
  cin >> a >> b;
  add(a, b);
  d[b] ++ ;
  
  void topsort(){
  	for(int i = 1; i <= n; ++ i)//遍历所有节点
  		if(!d[i]) q[ ++ tt] = i;//将入度为0的节点优先入队
  	//BFS
  	while(hh <= tt){ //队列非空
  		int x = q[hh ++ ]; //队首出队
  		for(int i = h[x]; i; i = ne[i]){
  			int j = e[i];//遍历以x为起点的所有边的终点
  			d[j] -- ; //删边，更新入度
  			if(!d[j]) q[ ++ tt] = j; //将所有入度为0的点入队
  		}
  	}
  	if(tt == n - 1) //所有点都在q数组时，存在拓扑序
  		for(int i = 0; i < n; ++ i) cout << q[i];
  	else cout << -1;//不存在拓扑序
  }