2023-12-28 12:09 门头沟学院 golang

关注

笔试ACM模式图论建图模板（Java&Python&C++）

互联网笔试中图论的题目比例很多，不管是基础的DFS,BFS，还是涉及到一些算法，如拓扑排序，dijkstra等，都离不开图的构建，LeetCode中的二叉树类型的题目，以及图论的题目，都是已经提供好对应的领接表或者领接矩阵，所以对于初学者来说，还是有必要去学习一下图论中的相关知识点，以及如何构建图的关系的。

树

树这个数据结构，相信看过一些后端八股，比如MySQL，Redis，又或者刷过一些数据结构题目的同学，一定对这种结构比较熟悉，树是由 $n（n\ge 1)$ 个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树有以下特点

每个节点具有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的所有点。邻接矩阵：邻接矩阵是一种常见的图的存储结构，用于表示顶点之间的关系。它使用一个二维数组来表示图中顶点之间的连接关系，其中数组的行和列分别代表图中的顶点，而数组中的元素表示顶点之间是否有边相连，以及边的权重。如果顶点 $i$ 和顶点 $j$ 之间有边相连，则邻接矩阵中的元素 $A[i][j]为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个点的点权

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的无向边

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))

离散化建图

一般用于点的范围较大( $[-10^9,10^9]$ )，或者含有负数的点，一般会使用离散化建图，或者有的不是点，而是字符串与字符串之间存在相互转换的关系，就可以使用哈希表这种数据结构来实现离散化建图。

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秋招米哈游的笔试真题，来为大家去看一下笔试中图论题目是如何考察的，以及遇到这种题目，我们如何去处理。

题目描述

塔子哥有一个 $n$ 个节点的树，树根编号为 $1$ 。

塔子哥可以在叶子节点上添加一个新的儿子节点，添加后，添加的节点变成了新的叶子节点。

若干次操作后，塔子哥想问你距离树根不超过 $k$ 的节点最多可以有多少个。

输入描述

第一行，一个正整数 $n$ 表示树中节点个数， $k$ 表示不超过树根的距离，

接下来 $n-1$ 行，每行输入两个整数 $u$ 和 $v$ ，表示节点 $u$ 和 $v$ 之间有一条边。

$1 \leq n \leq 10^5, 1\leq k\leq 10^9, 1\leq u,v\leq n$

输出描述

一个整数，表示若干次操作后距离树根不超过 $k$ 的节点最大数量。

样例

输入

输出

说明若干次操作后，最终的树如下，此时有 $7$ 个点距离 $1$ 号点的距离小于等于 $2$

思路:树形DFS+贡献法计数考虑每一个节点对答案的贡献：如果当前节点距离根节点的距离d有 $d \le k$ ，则答案+1

此外，如果当前节点还是叶子节点，则说明还可以再叶子结点下添加 $k-d$ 个点，这些点可以构成一条链。

因此，我们只需要对以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)

以上内容均来自：笔试刷题指南

#秋招##春招##笔试##大厂##面经##悬赏#

互联网笔试面试经验分享文章被收录于专栏

分享互联网大厂笔试面试经验，笔试面试常见套路和模版