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

  • 深度优先搜索

    • 一条路走到黑
    • 回溯/剪枝
    • 每一个dfs都对应一个搜索树
    • 解决全排列,搜索所有可能解
  • 宽度优先搜索
    • 一层一层搜索
    • 解决最短路问题
搜索方式 数据结构 空间 特点
DFS stack O(h) 不具有最短性
BFS queue O(2^h) 最短路
  • 树与图的存储

    • 有向图/树

      • 每条边建一次
        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;//不存在拓扑序
      }
      

热门相关:我的治愈系游戏   姨母的诱惑3   女大学生的沙龙室3   不科学御兽   异世修真邪君