图论
  1. Dotcpp
  2. 图论

列表

图论部分简介

图论部分简介

图论部分简介图论(Graphtheory)是数学的一个分支，图是图论的主要研究对象。图(Graph)是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物……
图论 2022年05月12日
简述最小树形图

简述最小树形图

简述最小树形图一、什么是最小树形图？就是指有向图上的最小生成树，英文是DirectedMinimumSpanningTree。常用的算法是朱刘算法（也称Edmonds算法），可以在O(nm)时间内解决最小树形图问题……
图论 2022年03月27日
最大流是什么？

最大流是什么？

最大流是什么？一、流网络G=(V，E)是一个有向图，其中每条边(u，v)有一个非负的容量值c(u，v)，而且如果E中包含一条边(u，v)，那么图中就不存在它的反向边。在流网络中有两个特殊的结点，源结点s和汇点t。下……
图论 2022年02月25日
什么是树上随机游走？

什么是树上随机游走？

什么是树上随机游走？什么是树上随机游走？我们可以假设给定一棵树，树的某个结点上有一个硬币，在某一时刻硬币会等概率地移动到邻接结点上，问硬币移动到邻接结点上的期望距离。1.树上随机游走用到的定义：● &a……
图论 2022年03月22日
什么是拓扑排序？

什么是拓扑排序？

什么是拓扑排序？拓扑排序的英文名是Topologicalsorting。拓扑排序要解决的问题是给一个图的所有节点排序。一、什么是拓扑排序在图论中，拓扑排序（TopologicalSorting）是一个有向无环图（DA……
图论 2022年01月19日
什么是树的重心？

什么是树的重心？

什么是树的重心？一、树的重心树的重心也叫树的质心。找到一个点，其所有的子树中最大的子树节点数最少，那么这个点就是这棵树的重心，删去重心后，生成的多棵树尽可能平衡。通俗点讲，就是在树中去掉一个点，删除这个点后，最大连通……
图论 2022年01月25日
二分图的最大匹配、完美匹配和匈牙利算法

二分图的最大匹配、完美匹配和匈牙利算法

二分图的最大匹配、完美匹配和匈牙利算法二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分……
图论 2022年01月30日
网络流常用小技巧拆点

网络流常用小技巧拆点

网络流常用小技巧拆点拆点是一种图论建模思想，常用于网络流，用来处理点权或者点的流量限制的问题，也常用于分层图。一、什么是拆点？什么是拆点？拆点就是将一个点拆成入点和出点两个点，并在两个点之间建一条边。为什么要拆点？拆点是……
图论 2022年01月28日
图的遍历DFS深搜优先搜索及C语言代码实现

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

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

图的储存方式

图的储存方式图是一个好东西，能够使用图来模拟或解决很多生活问题，同时在各大比赛上都少不了有关于图的问题.图是关系与顶点与边的，那么我们该如何来存入图的信息呢?（1）直接存边我们开一个数组，数组里每个元素是图的一条……
图论 2022年04月23日