链式前向星写法下的DFS和BFS

Input

5 7

1 2

2 3

3 4

1 3

4 1

1 5

4 5

output

1 5 3 4 2

#include<bits/stdc++.h>

using namespace std;

const int maxn = 150;

const int maxm = 1050;

int n, m;//顶点数，边数

int head[maxm], tot;

bool used[maxn];

//head[u]表示已知的最后一条以u为起点的边在边集e中的下标

struct edge {

    int to, next;

    //e[i].to表示边的终点，e[i].next表示上一条和边e[i]起点相同的点在e中的下标

    //int w;权值

}e[maxm];//边集

void init() {

    tot = 0;

    memset(head, -1, sizeof(head));

    memset(used, 0, sizeof(used));

}

void add(int u, int v) {//在图中加边

    //e[tot].w = w

    e[tot].to = v;

    e[tot].next = head[u];

    head[u] = tot++;

}

void dfs(int u) {

    used[u] = 1;

    printf("%d ", u);

    for (int i = head[u]; i != -1; i = e[i].next) {//遍历的方式

        int v = e[i].to;

        if (!used[v]) dfs(v);

    }

}

int main() {

    while (scanf("%d%d", &n, &m) == 2) {

        init();

        for (int i = 1; i <= m; ++i) {

            int from, to;

            scanf("%d%d", &from, &to);

            add(from, to);

            //add(to, from)无向图

        }

        for (int i = 1; i <= n; ++i) {

            if (!used[i] && head[i] != -1) dfs(i);

        }

        printf("\n");

    }

    return 0;

}

/*

5 7

1 2

2 3

3 4

1 3

4 1

1 5

4 5

1 5 3 4 2

*/

链式前向星和邻接表的思想是一样的，

区别就是：邻接表是用链表实现的，可以动态的增加边；

而链式前向星是用结构体数组实现的，是静态的，需要一开始知道数据范围，开好数组大小。

相比之下，邻接表灵活，链式前向星好写。