图的遍历

dfs深度优先遍历

//邻接表存边
#include <iostream>

const int N = 100010;
bool st[N];

using namespace std;

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

void add(int a, int b)//头插法将b添加到a的邻接表中
{
    Node* p = new Node(b);
    p->next = head[a];
    head[a] = p;
}

void dfs(int u)
{
    st[u] = true;
    printf("%d ", u);

    for(auto p = head[u]; p; p = p->next)//继续深度优先遍历u未被访问过的邻接点，直到访问完u所有的邻接点
    {
        int j = p->id;
        if(!st[j]) dfs(j);
    }
}

int main()
{
    int n, m;//n个点，m条边
    scanf("%d%d", &n, &m);
    while (m -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    for(int i = 1; i <= n; i ++)//遍历所有连通分量
        if(!st[i]) dfs(i);
}

//输入：4 4
1 2
1 3
2 4
3 2
//输出：1 3 2 4

//输入: 5 4
1 2
1 3
2 4
3 2
//输出：1 3 2 4 5

bfs广度优先遍历

//邻接表存边+stl容器queue
#include <iostream>
#include <queue>

const int N = 100010;
bool st[N];

using namespace std;

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

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

void bfs()
{
    queue<int> q;
    q.push(1);//从1开始遍历
    while(q.size())//队列非空
    {
        int u = q.front();//出队并访问队头元素
        q.pop();
        st[u] = true;
        printf("%d ", u);

        for(auto p = head[u]; p; p = p->next)//将u未被访问过的邻接点都入队
        {
            int j = p->id;
            if(!st[j])
            {
                st[j] = true;//入队顺序与遍历顺序相同
                q.push(j); 
            }
        }
    }
}

int main()
{
    int n, m;//n个点，m条边
    scanf("%d%d", &n, &m);

    while (m -- ){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    bfs();//不考虑不连通的点
}

//输入：4 4
1 2
1 3
2 4
3 2
//输出：1 3 2 4

//邻接表存边+数组模拟队列
#include <iostream>

const int N = 100010;
int q[N];//数组模拟队列
bool st[N];

using namespace std;

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

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

void bfs()
{
    int hh = 0, tt = - 1;//hh队头，tt队尾
    q[++ tt] = 1;//1入队
    st[1] = true;
    while(hh <= tt)//队列非空
    {
        int u = q[hh]; hh ++;//出队一个元素
        printf("%d ", u);

        for(auto p = head[u]; p; p = p->next)//将出队元素的所有邻接点都入队（访问）
        {
            int j = p->id;
            if(!st[j])
            {
                st[j] = true;//入队即置访问标记
                q[++ tt] = j;
            }
        }
    }
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    while (m -- )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    bfs();
}