图论

树哈希常用的方式

树哈希常用的方式树哈希,顾名思义,对树进行哈希,经常判断两个树是否同构。一下均为对有根树的算法,而无根树只需要找重心。我们有时需要判断一些树是否同构。这时,选择恰当的哈希方式来将树映射成一个便于储存的哈希值(一般是3……

简述LGV引理

简述LGV引理LGV引理可以用于在DAG上求解不相交路径方案数问题,下面我们简单介绍一下。一、简介LGV引理英文全称是Lindström–Gessel–Viennotlemma,可……

最小生成树,普利姆(Prim)算法及C/C++代码实现

最小生成树,普利姆(Prim)算法及C/C++代码实现1.最小生成树(又名:最小权重生成树)概念:将给出的所有点连接起来(即从一个点可到任意一个点),且连接路径之和最小的图叫最小生成树。最小生成树属于一种树形结构(树形结构是一种特殊的图),或者说是直链型……

树的基础知识

树的基础知识一、什么是树树是一种类似链表的数据结构,不过链表的结点是以线性方式简单地指向其后继指点,而树的一个结点可以指向许多个结点。树是一种典型的非线性结构。树结构是表达具有层次特性的图结构的一种方法。二、相关……

网络流的基本概念

网络流的基本概念什么是网络流?首先大家要知道网络流在图论中是尤为重要的。在这里,给大家介绍网络流中的一些基本知识。一、网络流的概念和定义整理在图论中,网络流(英语:Networkflow)是指在一个每条边都有容量(C……

斯坦纳树的应用

斯坦纳树的应用斯坦纳树问题是组合优化问题,与最小生成树相似,是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点,使生成的最短网络开销最小。1.什么是斯……

图文解析图论BFS(广度优先搜索)

图文解析图论BFS(广度优先搜索)BFS全称是BreadthFirstSearch,中文名是宽度优先搜索,也叫广度优先搜索。是图上最基础、最重要的搜索算法之一。所谓宽度优先。就是每次都尝试访问同一层的节点。如果同一层都访问完了,再访问……

什么是Prufer序列?

什么是Prufer序列?Prufer序列可以将一个带标号n个结点的树用[1,n]中的n-2个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。He……