这里只打一遍算法笔记上的邻接表版和邻接矩阵版

DFS

伪代码

  1. DFS(u){
  2.     vis[u] = true;
  3.     for(从u出发能到达的所有顶点v){
  4.         if(vis[v] = false) DFS(v)
  5.     }
  6. }
  7. DFSTrave(G){
  8.     for(G的所有顶点u){
  9.          if(vis[u] == false) DFS(u)   
  10.     }
  11. }

邻接矩阵版

  1. const int maxv = 1000;
  2. const int INF = 1000000000;
  3. int n, G[maxv][maxv];
  4. bool vis[maxv] = {false};
  6. void DFS(int u, int depth){
  7.     vis[u] = true;
  8.     //一些操作
  9.     for(int v = 0; v < n; v++){
  10.         if(vis[v] == false && G[u][v] != INF){
  11.             DFS(v, depth + 1);
  12.         }
  13.     }
  14. }
  15. void DFSTrave(){
  16.     for(int u = 0; u < n; u++){
  17.         if(vis[u] == false){
  18.             DFS(u, 1)
  19.         }
  20.     }
  21. }

邻接表版

  1. vector<int> Adj[maxn];
  2. int n;
  3. bool vis[maxn] = {false};
  5. void DFS(int u, int depth){
  6.     vis[u] = true;
  7.     for(int i = 0; i < Adj[u].size(); i++){
  8.         int v = Adj[u][i];
  9.         if(vis[v] == false){
  10.             DFS(v, depth + 1);
  11.         }
  12.     }
  13. }
  15. void DFSTrave(){
  16.     for(int u = 0; u < n; u++){
  17.         if(vis[u] == false){
  18.             DFS(u, 1);
  19.         }
  20.     }
  21. }

BFS

伪代码

  1. BFS(u){
  2.     queue q;
  3.     inq[u] = true;
  4.     while(q非空){
  5.         for(从u出发可到达的所有顶点v)
  6.             if(inq[v] == false){
  7.                 inq[v] = true;
  8.                 q.push(v);
  9.             }
  10.     }
  11. }
  12. BFSTrave(G){
  13.     for(G的所有顶点u){
  14.         if(inq[u] == false){
  15.             BFS(u);
  16.         }
  17.     }
  18. }

邻接矩阵版

  1. int n, G[maxn][maxn];
  2. bool inq[maxn] = {false};
  4. void BFS(int u){
  5.     queue<int> q;
  6.     q.push(u);
  7.     inq[u] = true;
  8.     while(!q.empty()){
  9.         int u = q.front();
  10.         q.pop();
  11.         for(int v = 0; v < n; i++){
  12.             if(inq[v] == false && G[u][v] != INF){
  13.                 q.push(v);
  14.                 inq[v] = true;
  15.             }
  16.         }
  17.     }
  18. }
  20. void BFSTrave(){
  21.     for(int u = 0; u < n; u++){
  22.         if(inq[u] == false){
  23.             BFS(q);
  24.         }
  25.     }
  26. }

邻接表版

  1. vector<int> Adj[maxn];
  2. int n;
  3. bool inq[maxn] = {false};
  5. void BFS(int u){
  6.     queue<int> q;
  7.     q.push(u);
  8.     inq[u] = true;
  9.     while(!q.empty()){
  10.         int u = q.front();
  11.         q.pop();
  12.         for(int i = 0; i < Adj[u].size(); i++){
  13.             int v = Adj[u][i];
  14.             if(inq[v] == false){
  15.                 q.push(v);
  16.                 inq[v] = true;
  17.             }
  18.         }
  19.     }
  20. }
  21. void BFSTrave(){
  22.     for(int i = 0; i < n; i++){
  23.         if(inq[i] == false){
  24.             BFS(i);
  25.         }
  26.     }
  27. }

求该连通块其他顶点的层号

  1. struct Node{
  2.     int v;
  3.     int layer;
  4. };
  6. vector<Node> Adj[N];
  8. void BFS(int s){
  9.     queue<Node> q;
  10.     Node start;
  11.     start.v = s;
  12.     start.layer = 0;
  13.     q.push(start);
  14.     inq[start.v] = true;
  15.     while(!q.empty()){
  16.         Node topNode = q.front();
  17.         q.pop();
  18.         int u = topNode.v;
  19.         for(int i = 0; i < Adj[u].size(); i++){
  20.             Node next = Adj[u][i];
  21.             next.layer = topNode.layer + 1;
  22.             if(inq[next.v] == false){
  23.                 q.push(next);
  24.                 inq[next.v] = true;
  25.             }
  26.         }
  27.     }
  28. }