首页 > 其他分享 >【code】图论

【code】图论

时间:2023-04-10 17:44:30浏览次数:33  
标签:图论 遍历 matrix int graph 连通 code 节点

一幅图是由节点和边构成的,逻辑结构如下:

  1. 所以图的逻辑结构为:
/* 图节点的逻辑结构 */
class Vertex {
    int id;
    Vertex[] neighbors;
}
  1. 一般边的表示,有两种实现方式,一种是邻接表,一种是邻接矩阵
  • 邻接表很直观,我把每个节点 x 的邻居都存到一个列表里,然后把 x 和这个列表关联起来,这样就可以通过一个节点 x 找到它的所有相邻节点。
  • 邻接矩阵则是一个二维布尔数组,我们权且称为 matrix,如果节点 x 和 y 是相连的,那么就把 matrix[x][y] 设为 true,如果想找节点 x 的邻居,去扫一圈 matrix[x][..] 就行了
// 邻接表
// graph[x] 存储 x 的所有邻居节点
List<Integer>[] graph;

// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
boolean[][] matrix;

  1. 图论中特有的度(degree)的概念
  • 在无向图中,「度」就是每个节点相连的边的条数
  • 有向图的边有方向,所以有向图中每个节点「度」被细分为入度(indegree)和出度(outdegree)

图的衍生

  1. 有向加权图
  • 是邻接表,我们不仅仅存储某个节点 x 的所有邻居节点,还存储 x 到每个邻居的权重,不就实现加权有向图了吗
  • 是邻接矩阵,matrix[x][y] 不再是布尔值,而是一个 int 值,0 表示没有连接,其他值表示权重,不就变成加权有向图了吗
// 邻接表
// graph[x] 存储 x 的所有邻居节点以及对应的权重
List<int[]>[] graph;
// 邻接矩阵
// matrix[x][y] 记录 x 指向 y 的边的权重,0 表示不相邻
int[][] matrix;
  1. 无向加权图
  • 是邻接表,在 x 的邻居列表里添加 y,同时在 y 的邻居列表里添加 x
  • 是邻接矩阵,如果连接无向图中的节点 x 和 y,把 matrix[x][y] 和 matrix[y][x] 都变成 true 不就行了

图的遍历

所有数据结构被发明出来无非就是为了遍历和访问,所以遍历是所有数据结构的基础

  • 参考多叉树的遍历框架
/* 多叉树遍历框架 */
void traverse(TreeNode root) {
    if (root == null) return;
    // 前序位置
    for (TreeNode child : root.children) {
        traverse(child);
    }
    // 后序位置
}
  • 图的遍历顺序
    图的遍历算法大多与BFS和DFS算法相关
    图是可能包含环的,你从图的某一个节点开始遍历,有可能走了一圈又回到这个节点,而树不会出现这种情况,从某个节点出发必然走到叶子节点,绝不可能回到它自身。
    所以,如果图包含环,遍历框架就要一个 visited 数组进行辅助。
// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;

/* 图遍历框架 */
void traverse(Graph graph, int s) {
    if (visited[s]) return;
    // 经过节点 s,标记为已遍历
    visited[s] = true;
    // 做选择:标记节点 s 在路径上
    onPath[s] = true;
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    // 撤销选择:节点 s 离开路径
    onPath[s] = false;
}

图的遍历,应该用DFS算法,即把 onPath 的操作放到 for 循环外面,否则会漏掉记录起始点的遍历

  • 图遍历的题目
    所有可能路径
    题目输入一幅有向无环图,这个图包含 n 个节点,标号为 0, 1, 2,..., n - 1,请你计算所有从节点 0 到节点 n - 1 的路径。
    【思路】以 0 为起点遍历图,同时记录遍历过的路径,当遍历到终点时将路径记录下来即可。既然输入的图是无环的,我们就不需要 visited 数组辅助了,直接套用图的遍历框架
class Solution {
    // 记录所有路径
    List<List<Integer>> res = new LinkedList<>();    
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 维护递归过程中经过的路径
        LinkedList<Integer> path = new LinkedList<>();
        traverse(graph, 0, path);
        return res;
    }

    /* 图的遍历框架 */
    void traverse(int[][] graph, int s, LinkedList<Integer> path) {
        // 添加节点 s 到路径
        path.addLast(s);

        int n = graph.length;
        if (s == n - 1) {
            // 到达终点
            res.add(new LinkedList<>(path));
        }
        // 递归每个相邻节点
        for (int v : graph[s]) {
            traverse(graph, v, path);
        }        
        // 从路径移出节点 s
        path.removeLast();
    }
}

并查集(森林)

并查集(Union-Find)算法是一个专门针对「动态连通性」的算法,Union-Find 算法的关键就在于 union 和 connected 函数的效率。

class UF {
    /* 将 p 和 q 连接 */
    public void union(int p, int q);
    /* 判断 p 和 q 是否连通 */
    public boolean connected(int p, int q);
    /* 返回图中有多少个连通分量 */
    public int count();
}

用数组实现:

class UF {
    // 记录连通分量
    private int count;
    // 节点 x 的父节点是 parent[x]
    private int[] parent;

    /* 构造函数,n 为图的节点总数 */
    public UF(int n) {
        // 一开始互不连通
        this.count = n;
        // 父节点指针初始指向自己
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    /* 其他函数 */
     public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样
        count--; // 两个分量合二为一
    }

    /* 返回某个节点 x 的根节点 */
    private int find(int x) {
        // 根节点的 parent[x] == x
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    /* 返回当前的连通分量个数 */
    public int count() { 
        return count;
    }   

    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
    }
}
  • 连通的概念:
    1、自反性:节点 p 和 p 是连通的。
    2、对称性:如果节点 p 和 q 连通,那么 q 和 p 也连通。
    3、传递性:如果节点 p 和 q 连通,q 和 r 连通,那么 p 和 r 也连通。

最小生成树

树不会包含环,图可以包含环。如果一幅图没有环,完全可以拉伸成一棵树的模样。说的专业一点,树就是「无环连通图」。

  • 生成树:在图中找一棵包含图中的所有节点的树
  • 最小生成树:一幅图可以有很多不同的生成树,对于加权图,每条边都有权重,所以每棵生成树都有一个权重和,所有可能的生成树中,权重和最小的那棵生成树就叫「最小生成树」
  1. Kruskal算法
    利用贪心的思想,将连通网中的所有边按照权值大小进行升序排序,从小到大依次选择
    条件:如果这个边不会与之前选择的所有边组成回路,就可以作为最小生成树的一部分;反之,舍去。直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。筛选出来的边和所有的顶点构成此连通网的最小生成树。

  2. Prim算法
    也是利用贪心的思想,从某个点相邻的边开始,每次选取最小权值的边加入

最短路径

输入一幅图和一个起点 start,计算 start 到其他节点的最短距离

标签:图论,遍历,matrix,int,graph,连通,code,节点
From: https://www.cnblogs.com/xiaoyu-jane/p/17303675.html

相关文章

  • leetcode 177
    第N高的薪水 CREATEFUNCTIONgetNthHighestSalary(NINT)RETURNSINTBEGINdeclareTintdefault0;SETT=N-1;RETURN(#WriteyourMySQLquerystatementbelow.selectifnull((selectdistinctsalaryfromEmployeeorderbysalarydesclimit......
  • linux系统下vscode的命令
    linux系统下vscode的命令选择“Terminal”--“NewTerminal",进入命令窗口1.文件夹跳转(1)进入共享文件夹:cdmnt/hgfs/共享文件夹/自定义文件夹/项目文件夹/例如:cd/mnt/hgfs/ljh/hello/hello/(2)进入系统主目录:cd/home/noi/(3)返回上一级目录:cd..(4)返回主目录:cd~2.查......
  • LeetCode 959. 有斜杠划分区域
    题目: https://leetcode.cn/problems/regions-cut-by-slashes/description/题解(参考了讨论区):将初始N*N的网格看做4*N*N的三角形集合,根据输入合并对应的三角形。   C#实现 publicclassSolution{publicintRegionsBySlashes(string[]grid){Uni......
  • mac配置vscode和go
    一安装和配置Go去这里下载Go的安装包:https://studygolang.com/dl建议下载pkg格式,懒人安装安装完毕后用goversion验证一下是否安装成功然后使用goenv查看一下go相关的环境变量主要是查看GOROOT,GOPATH,GOBINGOPATH:GO的工作目录,这个默认是~/goGOROOT:GO的安装目......
  • LeetCode 530.二叉搜索树的最小绝对值差
    1.题目:给你一个二叉搜索树的根节点root,返回树中任意两不同节点值之间的最小差值。差值是一个正数,其数值等于两值之差的绝对值。示例1:输入:root=[4,2,6,1,3]输出:1来源:力扣(LeetCode)链接:https://leetcode.cn/problems/minimum-absolute-difference-in-bst著作权归领扣网络所......
  • vscode保存时自动ESLint格式化(vue)
    一、安装eslint  二、vscode全局配置2.1打开设置   2.2打开settings.json  2.3在settings.json中添加eslint配置{"code-runner.runInTerminal":true,"eslint.format.enable":true,//以下是eslint配置//vscode默认启用了根据文件......
  • AtCoder Regular Contest 159
    Preface这周六紧张刺激的一日三赛,上午蓝桥杯,晚上ARC之后隔5min就是CF,可谓是手搓键盘到冒烟的一天了这场其实打的感觉很没水准,B刚开始没想清楚很多边界条件挂了三发,45min左右才过然后C的构造也不太会,随便写了个暴力也是挂挂挂,只好弃了去写D题了结果发现D题好像是个不难的线段树......
  • Codeforces Round 863 (Div. 3)
    题解报告基本的一些理解和问题都在注释中A:InsertDigit找到第一个小于输入数字的数的位置塞进去就好了,可以细推,但是粗略想想也能知道#include<bits/stdc++.h>usingnamespacestd;intmain(void){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int......
  • Codeforces Round 865 (Div. 2)
    CodeforcesRound865(Div.2)A.IanVisitsMaryvoidsolve(){intx=read(),y=read();if(__gcd(y,x)!=1){cout<<2<<endl;cout<<1<<""<<y-1<<endl;cout<<x<<"&q......
  • 第1章 C#和.NET简介 (Code like pro in C#)
    在本书的第一部分,我们将简要介绍C#语言,并讨论它的一些特性。第1章介绍了什么是C#和.NET,以及为什么您会(也不会)在项目中使用它们。第2章深入探讨了.NET的各种迭代,并在编译过程中采用了C#方法,在编译过程的每一个主要步骤都停止下来。尽管这部分确实是本书的介绍,但它仍然为熟悉C#的......