图

二分图匹配概述 首先是什么二分图？ 有一个无向图G = (U ∪ V, E) ，所有的顶点可以划分为U，V两个不相交的顶点集，那么就是一个二分图。 二分图的最大匹配就是找到两个集合可以通过边相连且...

流网络的基本概念和性质 1. 定义：流网络G = (V, E)是一个有向图，图中每条边有一个非负的容量值c，不会有一条边是另一条边的反向边（即不存在u->v 和 v->u同时存在）。且存在一个源点和一...

最短路径问题 首先定义最短路径是什么。最短路径就是在有权图中，从顶点s到顶点t的路径中权重最小的那条路。 同样，由于可能出现一点到另一点相同权重的路径，所以最短路径并不是唯一的。 本章节讨论有向...

什么是最小生成树? 在图G上，如果一个强连通图上的每条边上都有一个权重值，权重值可以是一个负数或零。那么一定可以找到一个无环边子集能够把这个图上的所有的点能够连接起来。 这个五环边子集的权重和如果是...

什么是拓扑排序？ 拓扑排序和其他排序算法不同，它主要是给有向无环图中所有结点的一种线性排序。 依据什么排序呢？如果有一条从u指向v的边，那么u在排序结果中一定会在v前面。正因如此，所有拓扑排序只对有...

图的基础概念 1. 图的定义： 无向图： 一个图G = (V,E)由顶点（或结点）的非空集V和边的集合E构成，每条边有一个或两个顶点与它相连，这样的顶点称为端点。边连接它的端点。（顶点集为无限的称为无...