图的存储与遍历

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>

using namespace std;

const int N = 10010, M = 10010;//N代表顶点,M代表边
int n,m;
bool st[N];

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

struct Node{
    int id;
    Node* next;
    Node(int _id): id(_id), next(NULL){};
} * head[N];

// 邻接表插入边a——>b(头插法)
void add(int a, int b){
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

//DFS（深度优先）
 void dfs(int u){
    st[u] = true;
    cout << u << ' ';

    for(Node *p = head[u] ; p ; p = p -> next){
        if(!st[p->id]){
            dfs(p->id);
        }
    }
}


//BFS（广度优先）
void bfs(int a){
    queue<int> q;
    q.push(a);
    st[a] = true;

    while(q.size()){
        int t = q.front();
        cout << t << ' ';
        q.pop();

        for(Node* p = head[t]; p ; p = p -> next){
            if(!st[p->id]){
                st[p->id] = true;
                q.push(p->id);
            }
        }
    }
}

int main(){
    cin >> n >> m;//n代表顶点，m代表边
    int a,b;

    //创建邻接矩阵
    // for(int i = 1; i <= n; i ++){
    //     for(int j = 1; j <= n; j++){
    //         g[i][j] = 0;
    //     }
    // }
    // for(int i = 1;i <= m ; i ++){
    //     cin >> a >> b;
    //     g[a][b] = 1;
    // }


    //创建邻接表
    for(int i = 0; i < m; i ++){
        cin >> a >> b;
        add(a,b);
    }

    // 输出邻接表
    for(int j = 1; j <= n ; j++ ){
        cout << j << "——>";
        for(Node* p = head[j]; p ; p = p->next){
            cout << p->id << "——>";
        }
        cout << "NULL" << endl;
    }

    //输出邻接矩阵
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= n; j++){
    //         cout << g[i][j] << ' ';
    //     }
    //     cout << endl;
    // }

    puts("----------------------------------");

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

    //bfs输出
    bfs(1);
    return 0;
}

DFS的非递归实现

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>

using namespace std;

const int N = 100, M = 100;//N代表顶点,M代表边
int n,m;
bool st[N];

struct Node{
    int val;
    Node* next;
    Node(int _val):val(_val),next(NULL){};//构造函数
}*head[N];

void add(int a, int b){
    Node* p = new Node(b);
    p -> next = head[a];
    head[a] = p;
}

void dfs(int k){
    stack<int> s;
    s.push(k);

    while(s.size()){
        int t = s.top();
        s.pop();

        if (st[t]) continue;
        cout << t << ' ';
        st[t] = true;

        for(Node *q = head[t]; q ; q = q -> next){
            int e = q -> val;
            if(!st[e]){
                s.push(e);
            }
        }
    }
}

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

    for(int i = 1; i <= m; i++){
        cin >> a >> b;
        add(a,b);
    }

    for(int j = 1; j <= n; j++){
        cout << j << ':';
        Node* t = head[j];
        while(t){
            cout << t -> val << "——>";
            t = t -> next;
        }
        cout << "NULL" << endl;
    }
    puts("---------------------------------------------");

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

    return 0;
}