acwing算法基础之搜索与图论--树与图的遍历

1 基础知识

树和图的存储：邻接矩阵、邻接表。
树和图的遍历：dfs、bfs。

2 模板

树是一种特殊的图（即，无环连通图），与图的存储方式相同。
对于无向图中的边ab，存储两条有向边a->b, b->a。
因此我们可以只考虑有向图的存储。

(1) 邻接矩阵：g[a][b] 存储边a->b

(2) 邻接表：

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;// 添加一条边a->b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 初始化
idx = 0;
memset(h, -1, sizeof h);

3 工程化

题目1：求树的重心。把某个结点删除，剩余连通块的最大值。遍历每一个结点，求取这个最大值集合中的最小值。
考察点：用dfs()遍历树，注意走过的结点不用走了。

#include <iostream>
#include <vector>using namespace std;const int N = 1e5 + 10;
int n;
int res = 1e9;
vector<bool> visited(N);
vector<vector<int>> g(N);int dfs(int u) {//返回以u为根结点的子树的结点数目visited[u] = true;int sum = 1;int ans = 0; //把u删除之后的，剩余连通块，数目最大值for (auto x : g[u]) {if (visited[x] == false) {int t = dfs(x);ans = max(ans, t);sum += t;            }}ans = max(ans, n - sum);res = min(res, ans);return sum;
}int main() {cin >> n;int x, y;for (int i = 0; i < n - 1; ++i) {cin >> x >> y;g[x].emplace_back(y);g[y].emplace_back(x);}dfs(1);cout << res << endl;return 0;
}

题目2：给你一张图，结点编号1,2,3…n，给你一些边，边的权重均是1，求结点1到结点n的最短距离，如果不存在路径，输出-1。
考察点：bfs()遍历图。

#include <iostream>
#include <vector>
#include <queue>using namespace std;const int N = 1e5 +10;
vector<vector<int>> g(N);
vector<int> d(N, -1);
int n, m;int main() {cin >> n >> m;int x, y;for (int i = 0; i < m; ++i) {cin >> x >> y;g[x].emplace_back(y);}queue<int> q;q.push(1);d[1] = 0;while (!q.empty()) {int t = q.front();q.pop();//t可以走到哪儿for (auto x : g[t]) {if (d[x] != -1) continue;d[x] = d[t] + 1;q.push(x);}}cout << d[n] << endl;return 0;
}