图是由顶点V的集合和边E的集合组成的二元组，记G=（V，E），图可以分为有向图和无向图。
无向图
若 为无向图，则 中的每个元素为一个无序二元组 ，称作 无向边 (Undirected edge) ，简称 边 (Edge) ，其中 。设 ，则 和 称为 的 端点 (Endpoint) 。
有向图
若 为有向图，则 中的每一个元素为一个有序二元组 ，有时也写作 ，称作 有向边 (Directed edge) 或 弧 (Arc) ，在不引起混淆的情况下也可以称作 边 (Edge) 。设 ，则此时 称为 的 起点 (Tail) ， 称为 的 终点 (Head) ，起点和终点也称为 的 端点 (Endpoint) 。并称 是 的直接前驱， 是 的直接后继。
- 完全图：任意两点都有边相连，我们很容易推出来，一张完全图的边数为（n为结点个数） n×(n−1)/2
- 连通图：顾名思义，连通图就是连通的图，即任意两点都能直接或间接到达，这就区别于完全图必须直接用边到达的定义。
- 顶点的度：与顶点关联的边的数目，有向图中等于该顶点的入度与出度之和。
- 入度——以该顶点为终点的边的数目和
- 出度——以该顶点为起点的边的数目和
- 关于度的定理：度数为奇数的顶点叫做奇点，度数为偶数的点叫做偶点。
- 图G中所有顶点的度数之和等于边数的2倍。因为计算顶点的度数时。每条边均用到2次。
- 任意一个图一定有偶数个奇点
2019 CSP-S 8. G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有 （）个顶点。
A. 10
B. 9
C. 11
D. 8答案：「B」
试题分析
- 一个没有重边和自环的联通无向图, 最多边数是每个顶点两两相连, 所以有 边. 所以28条边的话, 应该能有8个顶点. 8 * 7 / 2 = 28.
- 把这个图改成非联通, 只需要再增加一个孤点就可以. 也就是 8 + 1 = 9 个顶点.
最小生成树
在一个具有几个顶点的连通图G中，如果存在子图G’包含G中所有顶点和一部分边，且不形成回路，则称G’为图G的生成树，代价最小生成树则称为最小生成树。
求给定图的最小生成树有普里姆算法（Prim） 克鲁斯卡尔算法（Kruskal）
- 普里姆算法（Prim）
- 克鲁斯卡尔算法（Kruskal）
最短路径
所谓最短路径问题是指：如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边的权值总和（称为路径长度）达到最小。
- Dijkstra（迪杰斯特拉）算法
他的算法思想是按路径长度递增的次序一步一步并入来求取，是贪心算法的一个应用，用来解决单源点到其余顶点的最短路径问题。
- Floyd算法
Floyd算法属于动态规划，实现容易，好理解，但缺点就是时间复杂度高是O(n3)。
M[j][k] 表示从j 到 k 的路径，而 i 表示当前 j 到 k 可以借助的点；红色部分表示，如果 j 到 i ，i 到 k 是通的，就将 j 到 k 的值更新为min(M[j][i]+M[i][k],M[j][k])