树与图的建立：
# includeusing namespace std; const int N = 100010; int h[N], e[N], ne[N]; int idx; void add(int a, int b)//与单链表插入相同 { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int main() { int n; memset(h, -1, sizeof h); cin >> n; while (n--) { int a, b; cin >> a >> b; add(a, b); } }
树与图的深度优先搜索
void dfs(int u)
{
st[u] = true;
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])dfs(j);
}
}
# includeusing namespace std; const int N = 100010; int h[N], e[N], ne[N]; int idx; bool st[N]; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } void dfs(int u)//树与图的深度优先搜索 { st[u] = true; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j])dfs(j); } } int main() { int n; memset(h, -1, sizeof h); cin >> n; while (n--) { int a, b; cin >> a >> b; add(a, b); } dfs(1); }
例题：
树的重心题目描述：
给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1条无向边。请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式：
第一行包含整数 n，表示树的结点数。
接下来 n−1行，每行包含两个整数 a 和 b，表示点 a 和点 b之间存在一条边。
输出格式：
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围：
1≤n≤100000
输入样例：
9 1 2 1 7 1 4 2 8 2 5 4 3 3 9 4 6
输出样例：
4
解题代码：
# include# include using namespace std; const int N = 100010, M = N * 2; int h[N], e[M], ne[M]; int idx; bool st[N]; int ans = N, n; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int dfs(int u) { st[u] = true; int sum = 1, res = 0; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (!st[j]) { int s = dfs(j); res = max(res, s); sum += s; } } res = max(res, n - sum); ans = min(ans, res); return sum; } int main() { cin >> n; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); } dfs(1); cout << ans << endl; return 0; }
树与图的宽度优先搜索
例题：
图中点的层数题目描述：
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。所有边的长度都是 1，点的编号为 1∼n。请你求出 1 号点到 n 号点的最短距离，如果从 1号点无法走到 n 号点，输出−1。
输入格式：
第一行包含两个整数 n和 m。
接下来 m 行，每行包含两个整数 a 和 b，表示存在一条从 a走到 b的长度为 1 的边。
输出格式：
输出一个整数，表示 1 号点到 n 号点的最短距离。
数据范围：
1≤n,m≤100000
输入样例：
4 5 1 2 2 3 3 4 1 3 1 4
输出样例：
1
解题代码：
# include# include # include using namespace std; const int N = 100010; int h[N], e[N], ne[N],idx; int n, m; int d[N]; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } int bfs() { memset(d, -1, sizeof d); queue q; d[1] = 0; q.push(1); while (q.size()) { int t = q.front(); q.pop(); for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; if (d[j] == -1) { d[j] = d[t]+ 1; q.push(j); } } } return d[n]; } int main() { cin >> n >> m; memset(h,-1 ,sizeof h); while (m--) { int a, b; cin >> a >> b; add(a, b); } cout << bfs() << endl; return 0; }
树与图的宽搜的例题：
树与图的拓扑排序题目描述：
给定一个 n 个点 m 条边的有向图，点的编号是 1到 n，图中可能存在重边和自环。请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出−1。若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。
输入格式：
第一行包含两个整数 n 和 m。
接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。
输出格式：
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。否则输出 −1。
数据范围：
1≤n,m≤100000
输入样例：
3 3 1 2 2 3 1 3
输出样例：
1 2 3
一个有向无环图一定至少存在一个入度为零的点：
反证法：
若不存在入度为零的点，则这个图中的所有点必能找到其进入它的点，如此循环下去，改图不是无穷，就是有环，与条件不符，故得证。
解题代码：
# include# include # include using namespace std; const int N = 100010; int h[N], e[N], ne[N], idx; int n, m; int d[N],q[N]; void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } bool topsort() { int hh = 0, tt = -1; for (int i = 1; i <= n; i++) { if (!d[i]) { q[++tt] = i; } } while (hh <= tt) { int t = q[hh++]; for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; d[j] --; if (!d[j]) { q[++tt] = j; } } } return tt == n - 1; } int main() { scanf("%d%d",&n,&m); memset(h, -1, sizeof h); for (int i = 0; i < m; i++) { int a, b; scanf("%d%d",&a,&b); add(a, b); d[b]++; } if (topsort()) { for (int i = 0; i < n; i++) { cout << q[i] << " "; } cout<
