图论

1. Dotcpp
2. 图论

什么是树的重心？

一、树的重心树的重心也叫树的质心。找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心，删去重心后，生成的多棵树尽可能平衡。通俗点讲，就是在树中去掉一个点，删除这个点后，最大连通块(一定是树)的结点数最小。举个例子：对于一颗n个节点的无根树，

图论 2022年01月25日 200 点赞 0 评论 104950 浏览

图的遍历DFS深搜优先搜索及C语言代码实现

1.图的遍历在理解DFS算法之前，我们首先需要对什么是遍历进行了解，遍历的概念就是：从某一个点出发（一般是首或尾），依次将数据结构中的每一个数据访问且只访问一遍。2.DFS简介DFS（Depth-First-Search，深度优先搜索）算法的具体做法是：从某个点一直往深处走，

图 2022年01月25日 261 点赞 0 评论 184276 浏览

网络流常用小技巧拆点

拆点是一种图论建模思想，常用于网络流，用来处理点权或者点的流量限制的问题，也常用于分层图。一、什么是拆点？什么是拆点？拆点就是将一个点拆成入点和出点两个点，并在两个点之间建一条边。为什么要拆点？拆点是为了实现对点的限制。什么时候需要拆点？当题目中明确说明对点有限制或在实际应用中对点有限制时，

图论 2022年01月28日 230 点赞 0 评论 91840 浏览

简述矩阵树定理

Kirchhoff矩阵树定理可以简称矩阵树定理，可以解决了一张图的生成树个数计数问题。本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。一、概况1.无向图情况设G是一个有n个顶点的无向图。定义度数矩阵D(G)为：设为点i与点j相连的边数，

图论 2022年05月27日 160 点赞 0 评论 93130 浏览

有向无环图图文讲解

一、定义边有向，无环。英文名叫DirectedAcyclicGraph，缩写是DAG。一个无环的有向图称做有向无环图。在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环，

图论 2022年03月20日 154 点赞 0 评论 84717 浏览

网络流的基本概念

什么是网络流？首先大家要知道网络流在图论中是尤为重要的。在这里，给大家介绍网络流中的一些基本知识。一、网络流的概念和定义整理在图论中，网络流（英语：Networkflow）是指在一个每条边都有容量（Capacity）的有向图分配流，使一条边的流量不会超过它的容量。

图论 2022年03月23日 158 点赞 0 评论 106338 浏览

树链剖分解决什么问题？

一、什么是树链剖分什么是树链剖分？它可以把树分成若干条链，从而维护树上的路径信息。本质思想是把树剖成可以用线性结构存储的结构，然后可以数据结构维护。分为三种：重链剖分、长链剖分、实链剖分。以下以重链剖分为主。二、树链剖分的思想及能解决的问题重链剖分可以将树上的任意一条路径划分成不超过O(logn)条连

图论 2022年01月25日 168 点赞 0 评论 59652 浏览

图论部分简介

图论(Graphtheory)是数学的一个分支，图是图论的主要研究对象。图(Graph)是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。

图论 2022年05月12日 147 点赞 0 评论 83019 浏览

图的遍历BFS广度优先搜索

1.简介BFS（BreadthFirstSearch，广度优先搜索，又名宽度优先搜索），与深度优先算法在一个结点“死磕到底“的思维不同，广度优先算法关注的重点在于每一层的结点进行的下一层的访问。2.BFS算法介绍BFS算法和核心思路就是：从某个点一直把其邻接点走完，

图 2022年04月02日 240 点赞 0 评论 132705 浏览

什么是差分约束系统？

什么是差分约束系统？差分约束系统是一种特殊的N元一次不等式组，它包含N个变量以及M个约束条件，每个约束条件都是由两个变量作差得到的，形如，其中是常数。我们根据题目要求，并用这M个约束条件求出某个不等式的最值，例如的最大值。怎么解？转化：把上面不等式稍微变形一下可以得到，

图论 2022年02月05日 234 点赞 0 评论 71356 浏览