c++ 搜索与图的遍历及拓扑排序

  DFS在搜索中，拥有的空间复杂度与树(解空间构成的搜索数)的高度成正比，但是搜索的点不具有“最短路”的概念。

//算法框架
void dfs(int n){
   if(搜索结束){
      记录结果。
      return;
   }
   for(遍历所有解){
       if(合法的解){
         占位。
    }
       dfs(n+1);
       取消占位。
  }
}

  BFS在搜索中，需要大量空间是树(解空间构成的搜索数)的高度的指数级别，搜索具有“最短路”的概念。例如：最少步数，最少操作次数等等。当图的边权都相等，可以使用BFS求最短路。

//模板如下
#include
queue Q;

Q.push(初始状态);
while(!Q.empty()){
    type temp=Q.front();
    Q.pop();
    for(队首可扩展的每种状态){
        if(状态合法){
            Q.push(状态)
        }
    }
}

//在这里，要注意一点，主要是当type为结构体的情况。
//STL搭配结构体，以及它们对应的排序规则，一定要会。

  由于树是特殊的图，是无环连通图，因此可以采用存储图的方式存储树。对于图而言，存储方式可以利用邻接表和邻接矩阵。对于邻接矩阵而言，空间复杂度过高，也不常用。因此，重点介绍邻接表。对于无向图而言，如果a,b是联通的，采用的是在a中插入b和在b中插入a。
邻接表
类似于哈希表的拉链法，每个节点存储它能到达的边。采用数组模拟的方式更快速。结合代码讲解

const int maxn = 1e6 + 10;
int h[maxn],val[maxn],ne[maxn],idx; //h表示节点构成的数组。
void add(int a,int b){ //向a中加入边b。
   val[idx] = b,ne[idx] = head[a],head[a] = idx++; 
}
int main(){
    memset(h,-1,sizeof(h)); //初始化h数组
}

1.h数组表示所有节点，其余val,ne,idx和单链表含义一样,作为头结点初始化时为-1。
2.add是向节点a中加入边b
补充：memset()按照字节赋值，原理就是计算机组成原理c++按照补码存储。用法特殊：一般用来初始化0，-1，与无穷大。

#include
const int Max = 0x3f3f3f3f; //10^9范围内采用0x3f3f3f3f作为无穷大。
int h[10];
memset(h,0,sizeof(h)); //h全部为0
memset(h,-1,sizeof(h)); //h全部为-1
memset(h,0x3f,sizeof(h)); //h全部为0x3f3f3f3f;

int h[maxn],e[maxn],ne[maxn],idx;
bool st[maxn]; //存储每个节点是否被访问
void add(int a,int b){ //向a中加入边b。
   val[idx] = b,ne[idx] = head[a],head[a] = idx++; 
}
void dfs(int u){
    st[u] = true; //标记每个节点被访问
    for(int i =head[u] ;i != -1;i = ne[i]){
       int j = e[i]; 
     if(!st[j]) dfs(j);
}
}

int h[maxn],e[maxn],ne[maxn],idx;
bool st[maxn]; //存储每个节点是否被访问
queue q;
void add(int a,int b){
   val[idx] = b,ne[idx] = head[a],head[a] = idx++;
}
void bfs(){
    q.push(1);
    st[1] = true;
    while(q.size()){
      int t = q.front();
      q.pop();
      for(int i = head[t];i != -1;i = ne[i]){
          int j = val[i];
          if(!st[j]){
               q.push(j);
               st[j] = true;
          }
      }
}
}

  拓扑排序是针对有向图而言的，可以证明每一个有向无环图，都存在它的拓扑序列。可以利用宽度优先搜索解决。
  求解有向图的拓扑序列，首先找到图中入度为0的点，删除入度为0的点以及它的出边。循环往复即可。拓扑序列

#include
#include
#include
#include
using namespace std;
const int maxn = 1e5 + 10;
int n,m,d[maxn];
int head[maxn],val[maxn],ne[maxn],idx;
queue q,s;
void add(int a,int b){
    val[idx] = b,ne[idx] = head[a],head[a] = idx++;
}
bool topesort(){ //拓扑排序
    while(q.size()){
        int t = q.front();
        s.push(t);
        q.pop();
        for(int i = head[t];i != -1;i = ne[i]){
            int j = val[i];
            d[j]--;
            if(d[j] == 0) q.push(j);
        }
    }
    return s.size() == n; 
}
int main(){
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        d[b]++;
    }
    for(int i = 1;i<=n;i++){
        if(d[i] == 0) q.push(i);
    }
    if(topesort()){
        while(s.size()){
            printf("%d ",s.front());
            s.pop();
        }
    }else{
        puts("-1");
    }
}