易错点总结：
区分：DFS和BFS对图的遍历是否需要使用st[N]状态数组
1. DFS无论遍历邻接矩阵，亦或邻接表，都要使用状态数组，因为他又能产生回路，又绕回来了。
2. 因为BFS是层序遍历，所以不需要用状态数组。对吗？
ANS：不对，如果是使用邻接表存储的话，必须要使用状态数组，自己思考一下。

邻接矩阵转邻接表存储以及邻接表转邻接矩阵存储

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

//定义邻接矩阵
int g[N][N];

//定义邻接表
struct node(){
    int id;
    int w;
    node* next;
    node(int _id,int _w) : id(_id), w(_w), next(NULL){}
}*head[N];

//头插法创建邻接表
void add(int a,int b,int w){
    node* p = new node(b,w);
    p->next = head[a];
    head[a] = p;
}

//邻接矩阵转邻接表
void convert1(){

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(g[i][j] < INF/2) add(i,j,g[i][j]);

}


//邻接表转邻接矩阵
void convert2(){

    for(int i = 1; i <= n ; i++)
        for(auto p = head[i] ; p ; p= p->next)
            g[i][p->id] = g[p->id][i] = p->w;
}



int main(){
    //先将邻接矩阵初始化为无穷
    memset(g, INF, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        //无向图
        g[a][b] = g[b][a] = min(g[a][b], w);
    }

    convert1();

    //convert2();
    return 0;
}

dfs遍历邻接矩阵存储的图

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

bool st[N];

//定义邻接矩阵
int g[N][N];

//定义邻接表
struct node(){
    int id;
    int w;
    node* next;
    node(int _id,int _w) : id(_id), w(_w), next(NULL){}
}*head[N];

//头插法创建邻接表
void add(int a,int b,int w){
    node* p = new node(b,w);
    p->next = head[a];
    head[a] = p;
}

//dfs遍历邻接矩阵存储的图
void dfs(int i){
   st[i] = true;
   cout << i << ' ';

   for(int j = 1; j <= n ; j++)
       if(g[i][j] && !st[j]) dfs(j);
}


int main(){
    //先将邻接矩阵初始化为无穷
    memset(g, INF, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        //无向图
        g[a][b] = g[b][a] = min(g[a][b], w);
    }

    for(int i = 1; i <= n ;i++){
        if(!st[i]) dfs(i);
    }

    return 0;
}

dfs遍历邻接表

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

bool st[N];

//定义邻接矩阵
int g[N][N];

//定义邻接表
struct node(){
    int id;
    int w;
    node* next;
    node(int _id,int _w) : id(_id), w(_w), next(NULL){}
}*head[N];

//头插法创建邻接表
void add(int a,int b,int w){
    node* p = new node(b,w);
    p->next = head[a];
    head[a] = p;
}

//dfs遍历邻接矩阵存储的图
void dfs(int i){
   st[i] = true;
   cout << i << ' ';

   for(auto p = head[i] ; p ; p=p->next){
       int j = p->id;
       if(j && !st[j]) dfs(j);
   }
}


int main(){
    //先将邻接矩阵初始化为无穷
    memset(g, INF, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        add(a,b,w);
    }

    for(int i = 1; i <= n ;i++){
        if(!st[i]) dfs(i);
    }

    return 0;
}

dfs非递归遍历邻接矩阵

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

bool st[N];

//定义邻接矩阵
int g[N][N];

//定义邻接表
struct node(){
    int id;
    int w;
    node* next;
    node(int _id,int _w) : id(_id), w(_w), next(NULL){}
}*head[N];

//头插法创建邻接表
void add(int a,int b,int w){
    node* p = new node(b,w);
    p->next = head[a];
    head[a] = p;
}

void dfs(int i){

    stack<int> s;

    s.push(i);
    while(!s.empty()){

        int t = s.top();
        st[t] = true;
        cout << t << ' ';
        s.pop();

        for(int j = 1; j <= n ; j++)
            if(g[i][j] < INF/2 && !st[j]) s.push(j);

    }

}

int main(){
    //先将邻接矩阵初始化为无穷
    memset(g, INF, sizeof g);
    cin >> n >> m;
    while (m -- )
    {
        int a, b, w;
        cin >> a >> b >> w;
        g[a][b] = g[b][a] = min(g[a][b],w);
    }

    for(int i = 1; i <= n ;i++){
        if(!st[i]) dfs(i);
    }

    return 0;
}

基于邻接表存储的图的拓扑排序

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

bool st[N];

//定义邻接矩阵
int g[N][N];

int d[N];
int q[N];
int top;

bool topsort(){

    int hh = 0, tt = -1;

    for(int i = 1; i <= n ; i++){
        if(d[i]==0) q[++tt] = i;
    }

    while(hh <= tt){

        int j = q[hh++];

        for(auto p = head[j]; p ; p = p->next){
            int t = p->id;
            if(--d[t] == 0) q[++tt] = t;
        }
    }
    return tt == n-1;
}


int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        d[b] ++;
        add(a, b);
    }

    if (topsort()) 
    {
        for (int i = 0; i < n; i ++) cout << q[i] << ' ';
        cout << endl;
    }
    else puts("-1");

    return 0;
}

TopSort of the DFS

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

bool st[N];

//定义邻接矩阵
int g[N][N];

int st[N];
int q[N];
int top;

void dfs(int i){

    st[i] = 1;  // 表示正在遍历中;

    for(auto p = head[i]; p ; p = p->next){
        int j = p->id;
        if(!st[j]){
            if(!dfs(j)) return false;
        }
        if(st[j] == 1) return false;
    }

    q[top++] = i;
    st[i] = 2;  // 代表遍历完成

    return true;
}



bool topsort(){
    for(int i = 1; i <= n ; i++)
        if(!st[i] && !dfs(i)) return false;
    return true;
}


int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;

        add(a, b);
    }

    if (topsort()) 
    {
        for (int i = 0; i < n; i ++) cout << q[i] << ' ';
        cout << endl;
    }
    else puts("-1");

    return 0;
}

给出一个节点，问：从某一节点能否到到达该节点，如果能，请输出路径
tips:
1) 本质就是遍历图的问题
2）如果遍历到该点后，要想办法解决如何记录路径的问题
3）可以创建一个pre数组，借鉴并查集的思想记录他们的父节点，也就是前趋节点

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
const int INF = 0x3f3f3f3f;

int pre[N];
bool st[N];

//我们自定义从1开始遍历，看能否连通6，并输出路径
int hh = 1, tt = 6; 


void findPathWay(){
    pre[1] = -1; // 标志位
    queue<int> q;


    q.push(i);
    while(q.size()){
        int t = q.front();
        q.pop();
        st[t] = true;

        //如果找到了
        if(t == tt){
            vetor<int> path; // 创建一个路径数组
            path.push_back(t);

            for(int i = pre[t] ; i != -1 ; i = pre[i]){
                path.push_back(i);
            }
            reverse(path.begin(),path.end());

            for(int i = 0; i < path.size(),i++){
                cout << path[i];
            }
            return ; //结束任务，直接中断函数.
        }



        for(auto p = head[j]; p ; p = p->next){
            if(!st[p->id]){
                st[p->id] = 1;
                pre[p->id] = t;  // 记录前驱节点(父节点)；
                q.push(p->id);
            }
        }
    }
}


int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;

        add(a, b);
    }

    findPathWay();

    return 0;
}