目录
一、图的基本概念与数据结构
1.1 基本概念
1.1.1 图
所谓的图，直观地讲就是在平面上n个点，把其中的一些点对用曲线或直线连接起来,不考虑点的位置与连线曲直长短，这样形成一个关系结构就是一个图。记成G=(V,E)，V是以上述点为元素的顶点集，E是以上述连线为元素的边集。
如果各条边都加上方向，则称为有向图，否则称为无向图。如果有的边有方向,有的边无方向,则称为混合图。
如果任两定点间最多有一条边，且每条边的两个端点皆不重合的图,称为简单图。
定义 一个图是一个三元组<V(G),E(G),jG>，
其中V(G)是一个非空的结点集合， E(G)是边集合，
jG是从边集合到结点无序偶（有序偶）集合上的函数。
图可简记为G=<V,E>，其中V是非空结点集，E是边集 。
1.1.2 完全、非完全图
1.1.3 二分图、完全二分图
1.1.4. 度、奇定点、偶顶点
1.1.5 Hamilton图
1.1.6 赋权图
称两顶点u,v分别为起点和终点的最短轨道之长为顶点u,v的距离;在完全二分图Kxx中，X中两顶点之间的距离为偶数，X中的顶点与Y中的顶点的距离为奇数。
赋权图是指每条边都有一个(或多个)非负实数对应的图，这个（些)实数称为这条边的权（每条边可以具有多个权)。赋权图在实际问题中非常有用。根据不同的实际情况，权数的含义可以各不相同。例如，可用权数代表两地之间的实际距离或行车时间,也可用权数代表某工序所需的加工时间等。
（1）赋权有向图
（2）赋权无向图
1.2 图与网络的数据jie'gou
1.2.1 邻接矩阵表示法
1.2.2 稀疏矩阵表示法
二、最短路问题
2.1 两个指定顶点之间的最短路径
2.1.1 Dijkstra（迪克斯特拉）
其基本思想是按距u_0从近到远为顺序，依次求得u_0到G的各顶点的最短路和距离，直至v_0（或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法
2.2 两个指定顶点之间最短路问题的数学规划模型
起点：i = 1；终点：i = （1，n）；中间点：i = n
2.3 每对顶点之间的最短路径
2.3.1 Floyd算法
三、最小生成树问题
3.1 基本概念
（1）图
（2）树
3.2 最小生成树
3.2.1 prim算法构造最小生成树
总而言之，prim算法就是从一个点出发，每次出发都选择权值最小的点行动，直至遍历所有的点，注意的是上一个到达的终点不一定就是下一次出发的起点，如上一个起点是A，终点是B，而下一步是要到达C，但B和A都可以到达C，此时需要比较B-C和A-C的权值，选择小的
3.2.2 Kruskal算法构造最小生成树
选权最小的边，避圈法
Kruskal算法是基于贪心的思想得到的。首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。至于怎么合并到一个集合，那么这里我们就可以用到一个工具——-并查集。换而言之，Kruskal算法就是基于并查集的贪心算法。
所以Kruskal算法就是把所有边的权值排序，先选择最小的边，两端点不在同一树下是，并入一个集合E，然后继续选择次小的边，不在同一树下的话继续并入集合，直至所有的端点都在同一集合下形成最小生成树，而遇到边的端点已在集合内时放弃这条边，选择次小的，直到都不在同一树下，即不在同一集合内，继续并入。
86待续：网络流问题、最大流问题、匹配问题、最优分配、匈牙利算法
标签：赋权,1.1,建模,网络,算法,数学,集合,顶点,最小 From： https://blog.csdn.net/qq_47941078/article/details/125740112