图论

存储。图用邻接矩阵（较少），树用邻接表。

1
2
//邻接表
void add(int a, int b) {e[idx]=b; ne[idx]=h[a]; h[a]=idx++;}

一、遍历：DFS和BFS

DFS模板

dfs多用函数递归，作为遍历框架；bfs则用队列是否为空的循环，作为遍历框架。

1
2
3
4
5
6
7
8
9
10
11
12
13
//从dfs(0)作为函数入口
void dfs(int u){					//path[]作为答案，st[]限制元素使用次数，u作为path[]的下标
  if(u==n) 								//输出
  for(int i=1; i<=n; i++){		//遍历范围
    if(!st[i]){								//满足条件
      path[u]=i;
      st[i]=true；						 //使用过后做标记
      dfs(u+1);
      path[u]=0;						  //还原
      st[i]=false;
    }											
  }
}
1
2
3
4
5
6
7
8
9
10
//树的dfs遍历
void dfs(int u){
  st[u]=trrue;
  for(int i=h[u]; i!=-1; i=ne[i]){
    int j=e[i];
    if(!st[j]){
      dfs(j);
    }
  }
}

经典例题

N皇后问题

BFS模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void bfs(){
  queue<int> q;
  unordered_map<string,int> d;
  q.push({1,1}); 
  while(q.size()){
    auto t=q.front(); q.pop();
    
    if(d[t]满足条件) return d[t];
    
    //从边遍历
    int distance;	//记录t的距离
    for(int i=h[t]; i!=-1; i=ne[i]){
      int j=e[i];
      if(!st[j]){
        d[t]=distance+1;
        q.push(t);
      }
    }
  }
}

二、拓扑排序

1
2
3
4
5
6
7
8
9
10
11
void top_sort(){
  queue<int>q;
  for(int i=1; i<=n; i++) {if(!in[i]) q.push(i);}
  while(q.size()){
    auto t=q.front(); q.pop(); L.push_back(t);
    for(int i=h[t]; i!=-1; i=h[i]){
      int j=e[i];
      if(--in[j]==0) q.push(j);
    }
  }
}

( 还不会拓扑排序？看这一篇就够了_Iareges的博客-CSDN博客)

例题

有向图的拓扑序列

三、最短路

Djkstra

1使用于紧密矩阵，2适用于稀疏矩阵。

  1. 连线很多的时候，对应的就是稠密图，显然易见，稠密图的路径太多了，所以就用点来找，也就是抓重点；
  2. 点很多，但是连线不是很多的时候，对应的就是稀疏图，稀疏图的路径不多，所以按照连接路径找最短路，这个过程运用优先队列，能确保每一次查找保留到更新到队列里的都是最小的，同时还解决了两个点多条路选择最短路的问题；

```C++