笔试ACM模式图论建图模板（Java&Python&C++）
互联网笔试中图论的题目比例很多，不管是基础的DFS,BFS，还是涉及到一些算法，如拓扑排序，dijkstra等，都离不开图的构建，LeetCode中的二叉树类型的题目，以及图论的题目，都是已经提供好对应的领接表或者领接矩阵，所以对于初学者来说，还是有必要去学习一下图论中的相关知识点，以及如何构建图的关系的。
树
树这个数据结构，相信看过一些后端八股，比如MySQL，Redis，又或者刷过一些数据结构题目的同学，一定对这种结构比较熟悉，树是由个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树有以下特点
- 每个节点具有0个或多个子节点
- 没有父节点的节点被称为根节点
- 每一个非根节点只有一个父节点
- 每一个节点及其后代节点整体可以被视为一个树
树中有一类很特殊的树：二叉树，二叉树是一种特殊的树，其中任何一个节点具有的子节点个数不超过2，因此被称为二叉树，如下图所示，就是一个根节点为1的二叉树。1号节点的子节点是2和3,2节点的子节点是4和5，3节点的子节点是6和7。
图
那么树与图具有什么关系呢？其实树是一种特殊的图，就是有向无环图。
- 有向，指的是有方向，比如上面这张图，箭头的方向就表示了其是一个有向图，对于二叉树而言，在递归搜索的时候，你可以从父节点搜到子节点，但是你不能从子节点搜索到父节点
- 无环，不能自己指向自己（自环），或者由多个节点构成一个环，比如
a->b,b->c,c->a，这就构成了一个环，对于树这种数据结构，从根节点出发是自顶向下的，是不会存在环的一个关系的，因此树一定是一种无环图。
图论基本概念
入度：指向当前节点的有向边的数量，比如有一条a->b的有向边，则节点b的入度为1
出度：当前节点被指向的有向边的数量，比如有一条a->b的有向边，则节点a的出度为1
注意：如果在一个有向图中，一个节点的入度为0，那么该节点，就是一个没有父节点的根节点。比如拓扑排序中，起始的入队元素就是入度为0的所有点。邻接矩阵：邻接矩阵是一种常见的图的存储结构，用于表示顶点之间的关系。它使用一个二维数组来表示图中顶点之间的连接关系，其中数组的行和列分别代表图中的顶点，而数组中的元素表示顶点之间是否有边相连，以及边的权重。如果顶点和顶点
之间有边相连，则邻接矩阵中的元素
（或边的权重），否则为0。比如有如下无向图
邻接矩阵表示为：
0 1 0 1 1 0 1 1 0 1 0 1 1 1 1 0
邻接表：邻接表是另一种常见的图的存储结构，它使用一个数组和链表来表示图中的顶点和它们的邻接顶点。具体来说，数组中的每个元素代表图中的一个顶点，而每个元素对应的链表存储了与该顶点相邻的顶点。比如有如下无向图
邻接表表示为：
1: 2 -> 4 #表示1有2和4与它相连 2: 1 -> 3 3: 2 -> 4 4: 1 -> 3
这篇文章讲解领接表的质量还是相当不错的，可以供大家参考：领接表讲解
建图模版
笔试中常考的建图，一般都是需要使用领接表建图
对于一般的BFS或者DFS来说，很多题目是没有边权这种说法的，那么就可以直接使用下面的点权建图模版建图，如果有边权，则可以使用下面的边权模版建图，如果边权在点上，仍然可以使用下面的边权模版建图。
常用的建图方法主要是有点权建图(权值在节点上)，边权建图(权值在边上)，还有一种就是使用离散化建图（使用哈希表）
领接表点权建图
权值在点上，对应点有权值，对于C++选手来说，可以使用vector来优化建图，并维护一个w数组来记录点权
输入样例
n个点，m条边，每行输入两个整数a，b，表示a->b连接一条有向边
最后一行输入n个整数，表示n个点的点权
4 3 1 2 2 3 3 4 1 2 3 4
C++
#include <bits/stdc++.h>
using namespace std;
const int N=1E5+10;
vector<int>g[N]; //领接表的vector写法 仅适用于点权建图
int w[N];
void dfs(int u,int fa) //如果是有向图 就不需要fa这个变量
{
//do things
for(int &x:g[u]) //访问u的所有节点
{
if(x==fa)continue; //无向边才需要这一句 保证每个节点只会被访问一次(不理解的可以直接背过)
dfs(x,u);
// do things
}
}
int main(){
int n,m; //n个点,m条边
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
g[a].push_back(b); //a->b建立一条边
}
for(int i=1;i<=n;i++)cin>>w[i];
return 0;
}
Java
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
static final int N = 100010;
static ArrayList<Integer>[] g = new ArrayList[N];
static int[] w = new int[N];
static void dfs(int u, int fa) {
// Do things
for (int x : g[u]) {
if (x == fa)
continue;
dfs(x, u);
// Do things
}
}
public static void main(String[] args) {
int n, m;
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i++) {
g[i] = new ArrayList<>();
}
for (int i = 0; i < m; i++) {
int a, b;
a = scanner.nextInt();
b = scanner.nextInt();
g[a].add(b); // a->b建立一条边
}
for (int i = 1; i <= n; i++) {
w[i] = scanner.nextInt();
}
}
}
Python3
N = 100010
g = [[] for _ in range(N)]
w = [0] * N
def dfs(u, fa):
# Do things
for x in g[u]:
if x == fa:
continue
dfs(x, u)
# Do things
n, m = map(int, input().split())
for i in range(m):
a, b = map(int, input().split())
g[a].append(b) # a->b建立一条边
w[1:] = map(int, input().split())
领接表边权建图
权值在边上，对应点有权值，对于C++选手来说，可以使用vector来优化建图，不过需要使用pair<int,int>这个类型来分别存储节点和边权
输入样例
n个点，m条边，每行输入三个整数a,b,c 表示a->b连接一条边权为c的无向边
4 3 1 2 3 2 3 2 3 4 2
C++
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
#define x first
#define y second
typedef long long ll;
const int N=1E5+10;
vector<PII>g[N];
int n,f[N];
void dfs(int u,int fa){
for(auto &[x,w]:g[u]){
if(x==fa)continue;
dfs(x,u);
//代码逻辑
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int a,b,c;
cin>>a>>b>>c;
g[a].push_back({b,c});
g[b].push_back({a,c});
}
return 0;
}
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static List<int[]>[] g;
static int n;
static int[] f;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
g = new ArrayList[n + 1];
for (int i = 1; i <= n; i++) {
g[i] = new ArrayList<>();
}
f = new int[n + 1];
for (int i = 1; i < n; i++) {
int a = scanner.nextInt();
int b = scanner.nextInt();
int c = scanner.nextInt();
g[a].add(new int[]{b, c});
g[b].add(new int[]{a, c});
}
}
static void dfs(int u, int fa) {
for (int[] pair : g[u]) {
int x = pair[0];
int w = pair[1];
if (x == fa) continue;
dfs(x, u);
//代码逻辑
}
}
}
Python3
from collections import defaultdict
n = int(input())
g = defaultdict(list)
f = [0] * (n + 1)
def dfs(u, fa):
global f
for x, w in g[u]:
if x == fa:
continue
dfs(x, u)
#代码逻辑
for _ in range(1, n):
a, b, c = map(int, input().split())
g[a].append((b, c))
g[b].append((a, c))
离散化建图
一般用于点的范围较大()，或者含有负数的点，一般会使用离散化建图，或者有的不是点，而是字符串与字符串之间存在相互转换的关系，就可以使用哈希表这种数据结构来实现离散化建图。
C++
#include<bits/stdc++.h>
using namespace std;
int main() {
unordered_map<int, vector<pair<int, int>>> path;
// 添加节点 1 到节点 2 的边权为 3
path[1].push_back({2, 3});
// 遍历节点 1 的所有能到的点和边权
int node = 1;
for (auto &entry : path[node]) {
int target = entry.first;
int weight = entry.second;
// 进行处理
cout << "From node " << node << " to node " << target << " with weight " << weight << endl;
}
return 0;
}
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
int N = 100010;
Map<Integer, List<Map.Entry<Integer, Integer>>> path = new HashMap<>();
// 添加节点 u 到节点 v 的边权为 w
int u = 1, v = 2, w = 3;
if (!path.containsKey(u)) {
path.put(u, new ArrayList<>());
}
path.get(u).add(new AbstractMap.SimpleEntry<>(v, w));
// 遍历节点 u 的所有能到的点和边权
int node = 1;
if (path.containsKey(node)) {
for (Map.Entry<Integer, Integer> entry : path.get(node)) {
int target = entry.getKey();
int weight = entry.getValue();
// 进行处理
}
}
}
}
Python3
from collections import defaultdict
n = int(input())
g = defaultdict(list)
f = [0] * (n + 1)
def dfs(u, fa):
global f
for x, w in g[u]:
if x == fa:
continue
dfs(x, u)
#代码逻辑
for _ in range(1, n):
a, b, c = map(int, input().split())
g[a].append((b, c))
g[b].append((a, c))
真题讲解
下面讲解一道24秋招米哈游的笔试真题，来为大家去看一下笔试中图论题目是如何考察的，以及遇到这种题目，我们如何去处理。
题目描述
塔子哥有一个 个节点的树，树根编号为
。
塔子哥可以在叶子节点上添加一个新的儿子节点，添加后，添加的节点变成了新的叶子节点。
若干次操作后，塔子哥想问你距离树根不超过 的节点最多可以有多少个。
输入描述
第一行，一个正整数 表示树中节点个数，
表示不超过树根的距离，
接下来 行，每行输入两个整数
和
，表示节点
和
之间有一条边。
输出描述
一个整数，表示若干次操作后距离树根不超过 的节点最大数量。
样例
输入
4 2 1 2 1 3 1 4
输出
7
说明若干次操作后，最终的树如下，此时有 个点距离
号点的距离小于等于
思路:树形DFS+贡献法计数考虑每一个节点对答案的贡献：如果当前节点距离根节点的距离d有，则答案+1
此外，如果当前节点还是叶子节点，则说明还可以再叶子结点下添加个点，这些点可以构成一条链。
因此，我们只需要对以1号点为根的树进行DFS遍历，在遍历的过程中，可以计算出每一个节点到根节点的距离，然后根据上述的规则进行计算，累加答案即可。
根据上述方式统计计数即可，注意本题题目给的是无向边，需要建两条有向边。
C++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k;
cin >> n >> k;
// 建图
vector<vector<int>> g(n);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v;
u--; v--;
g[u].emplace_back(v);
g[v].emplace_back(u);
}
const int INF = 0x3f3f3f3f;
long long ans = 0;
vector<int> dist(n, INF);
// 计算1号点到每个点的距离，1号点到自己的距离为 0
dist[0] = 0;
function<void(int,int)> dfs = [&](int u, int fa) {
// 如果1号点到u+1点的距离 <= k，则答案加1
if (dist[u] <= k) {
ans += 1;
}
// 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
if (u != 0 && g[u].size() == 1 && dist[u] < k) {
ans += k - dist[u];
}
// 继续遍历子树 v
for (int v: g[u]) {
if (v == fa) continue;
dist[v] = dist[u] + 1;
dfs(v, u);
}
};
dfs(0, -1);
cout << ans << "\n";
return 0;
}
Java
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
static List<List<Integer>> g;
static int[] dist;
static int n, k;
static long ans;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
k = scanner.nextInt();
// 建图
g = new ArrayList<>();
for (int i = 0; i < n; i++) {
g.add(new ArrayList<>());
}
for (int i = 1; i < n; i++) {
int u = scanner.nextInt() - 1;
int v = scanner.nextInt() - 1;
g.get(u).add(v);
g.get(v).add(u);
}
final int INF = 0x3f3f3f3f;
ans = 0;
dist = new int[n];
for (int i = 0; i < n; i++) {
dist[i] = INF;
}
// 计算1号点到每个点的距离，1号点到自己的距离为 0
dist[0] = 0;
dfs(0, -1);
System.out.println(ans);
}
static void dfs(int u, int fa) {
// 如果1号点到u+1点的距离 <= k，则答案加1
if (dist[u] <= k) {
ans++;
}
// 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
if (u != 0 && g.get(u).size() == 1 && dist[u] < k) {
ans += k - dist[u];
}
// 继续遍历子树 v
for (int v : g.get(u)) {
if (v == fa) {
continue;
}
dist[v] = dist[u] + 1;
dfs(v, u);
}
}
}
Python
def dfs(u, fa):
global ans
# 如果1号点到u+1点的距离 <= k，则答案加1
if dist[u] <= k:
ans += 1
# 如果1号点到叶子的距离 < k，则还可以再这个叶子下加 k - dist[u] 个
if u != 0 and len(g[u]) == 1 and dist[u] < k:
ans += k - dist[u]
# 继续遍历子树 v
for v in g[u]:
if v == fa:
continue
dist[v] = dist[u] + 1
dfs(v, u)
n, k = map(int, input().split())
# 建图
g = [[] for _ in range(n)]
for _ in range(1, n):
u, v = map(int, input().split())
u -= 1
v -= 1
g[u].append(v)
g[v].append(u)
INF = int(1e9)
ans = 0
dist = [INF] * n
# 计算1号点到每个点的距离，1号点到自己的距离为 0
dist[0] = 0
dfs(0, -1)
print(ans)
以上内容均来自：笔试刷题指南
#秋招##春招##笔试##大厂##面经##悬赏#分享互联网大厂笔试面试经验，笔试面试常见套路和模版
投递网易游戏等公司6个岗位