图论
  1. Dotcpp
  2. 图论

列表

简述矩阵树定理

简述矩阵树定理

简述矩阵树定理Kirchhoff矩阵树定理可以简称矩阵树定理，可以解决了一张图的生成树个数计数问题。本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。一、概况1.无向图情况设G是一个有n个顶点的无向图。定义……
图论 2022年05月27日
网络流的基本概念

网络流的基本概念

网络流的基本概念什么是网络流？首先大家要知道网络流在图论中是尤为重要的。在这里，给大家介绍网络流中的一些基本知识。一、网络流的概念和定义整理在图论中，网络流（英语：Networkflow）是指在一个每条边都有容量（C……
图论 2022年03月23日
图的存储:链式向前星

图的存储:链式向前星

图的存储:链式向前星1.概念链式向前星代码是基于向前星代码的优化，这是极大多数算法竞赛以及高效率图论算法喜欢适用的创建方法，与邻接表和邻接矩阵比较容易的理解方式，向前星算法并不容易理解。在理解链式向前星之前我们需要了解什……
图 2022年01月11日
树链剖分解决什么问题？

树链剖分解决什么问题？

树链剖分解决什么问题？一、什么是树链剖分什么是树链剖分？它可以把树分成若干条链，从而维护树上的路径信息。本质思想是把树剖成可以用线性结构存储的结构，然后可以数据结构维护。分为三种：重链剖分、长链剖分、实链剖分。以下以重链剖……
图论 2022年01月25日
什么是差分约束系统？

什么是差分约束系统？

什么是差分约束系统？什么是差分约束系统？差分约束系统是一种特殊的N元一次不等式组，它包含N个变量以及M个约束条件，每个约束条件都是由两个变量作差得到的，形如，其中是常数。我们根据题目要求，并用这M个约束条件求出某个不等式……
图论 2022年02月05日
图的基础概念

图的基础概念

图的基础概念图(Graph)是由顶点和连接顶点的边构成的离散结构。在计算机科学中，图是最灵活的数据结构之一，很多问题都可以使用图模型进行建模求解。图(Graph)通常会放在树(Tree)后面介绍，树可以说是图的特……
图论 2022年05月05日
图论中的有向无环图

图论中的有向无环图

图论中的有向无环图在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均……
图论 2022年02月06日
简述LGV引理

简述LGV引理

简述LGV引理LGV引理可以用于在DAG上求解不相交路径方案数问题，下面我们简单介绍一下。一、简介LGV引理英文全称是Lindström–Gessel–Viennotlemma，可……
图论 2022年04月20日
最大流是什么？

最大流是什么？

最大流是什么？一、流网络G=(V，E)是一个有向图，其中每条边(u，v)有一个非负的容量值c(u，v)，而且如果E中包含一条边(u，v)，那么图中就不存在它的反向边。在流网络中有两个特殊的结点，源结点s和汇点t。下……
图论 2022年02月25日
图的遍历DFS深搜优先搜索及C语言代码实现

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

图的遍历DFS深搜优先搜索及C语言代码实现1.图的遍历在理解DFS算法之前，我们首先需要对什么是遍历进行了解，遍历的概念就是：从某一个点出发（一般是首或尾），依次将数据结构中的每一个数据访问且只访问一遍。2.DFS简介DFS（Depth-Fi……
图 2022年01月25日