图
图的应用极为广泛，已渗入到诸如物理、化学、电信工程、计算机科学，以及数学等其他分支中。在离散数学中，图论是专门研究图的性质的数学分支，而在数据结构中，则应用图论的知识讨论如何在计算机上实现图的操作，因此主要学习图的存储结构，以及若干图的操作的实现。
图的定义和基本术语
图的定义
图的基本术语
-
子图：假设有两个图 \(G = (v, E)\) 和 \(G^{'}=(V^{'}, E^{'})\) ，如果 \(V^{'} \subseteq V 且 E^{'} \subseteq E\)，则称 \(G^{'}\) 为 \(G\) 的子图。
-
无向完全图和有向完全图：对于无向图，若具有 \(n(n - 1)/2\) 条边，则称为无向完全图。对于有向图，若具有 \(n(n - 1)\) 条弧，则称为有向完全图。
-
稀疏图和稠密图：有很少条边或弧（如 \(e < nlog_{2}n\) ）的图称为稀疏图，反之称为稠密图。
-
权和网：在实际应用中，每条边可以标上具有某种含义的数值，该数值称为该边上的权。这些权可以表示从一个顶点到另一个顶点的距离或耗费。这种带权的图通常称为网。
-
邻接点：对于无向图 \(G\) ，如果图的边 \((v, v^{'}) \subseteq E\) ，则称顶点 \(v\) 和 \(v^{'}\) 互为邻接点，即 \(v\) 和 \(v^{'}\) 相邻接。边 \((v, v^{'})\) 依附于顶点 \(v\) 和 \(v^{'}\) ，或者说边 \((v, v^{'})\) 与顶点 \(v\) 和 \(v^{'}\) 相关联。
-
度、入度和出度：顶点 \(v\) 的度是指和 \(v\) 相关联的边的数目，记为 \(TD(v)\) 。对于有向图，顶点 \(v\) 的度分为入度和出度。入度是以顶点 \(v\) 为头的弧的数目，记为 \(ID(v)\) ；出度是以顶点 \(v\) 为尾的弧的数目，记为 \(OD(v)\) 。顶点 \(v\) 的度为 \(TD(v) = ID(v) + OD(v)\) 。一般地，如果顶点 \(v_{i}\) 的度记为 \(TD(v_{i})\) ，那么一个有 \(n\) 个顶点 \(e\) 条边的图，满足如下关系 $$ e = \frac{1}{2} \sum_{i = 1}^{n}TD(v_{i}) $$
-
路径和路径长度：在无向图 \(G\) 中，从顶点 \(v\) 到顶点 \(v^{'}\) 的路径是一个顶点序列\((v = v_{i, 0}, v_{i, 1}, ... v_{i, m} = v^{'})\) ，其中 \((v_{i, j - 1}, v_{i, j}) \subseteq E, 1 \le j \le m\) 。如果 \(G\) 是有向图，则路径也是有向的，顶点序列应满足 \(<v_{i, j-1}, v_{i, j}> \subseteq E, 1 \le j \le m\) 。路径长度是一条路径上经过的边或弧的数目。
-
回路或环：第一个顶点和最后一个顶点相同的路径称为回路或环。
-
简单路径、简单回路或简单环：序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路，称为简单回路或简单环。
-
连通、连通图和连通量：在无向图 \(G\) 中，如果从顶点 \(v\) 到顶点 \(v_{'}\) 有路径，则称 \(v\) 和 \(v_{'}\) 是连通的。如果对于图中任意两个顶点 \(v_{i}、v_{j} \subseteq V\)，\(v_{i}\) 和 \(v_{j}\) 都是连通的，则称 \(G\) 是 连通图。 所谓连通分量 ，指的是无向图中的极大连通子图。
-
强连通图和强连通分量：在有向图 \(G\) 中，如果对于每一对 \(v_{i}，v_{j} \subseteq V\) ， \(v_{i} \ne v_{j}\) ，从 \(v_{i}\) 到 \(v_{j}\) 和从 \(v_{j}\) 到 \(v_{i}\) 都存在路径，则称 \(G\) 是强连通图。有向图中的极大强连通子图称作有向图的强连通分量。
-
连通图的生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的 \(n - 1\) 条边，这样的连通子图称为连通图的生成树。
-
有向树和生成森林：有一个顶点的入度为0，其余顶点的入度均为1的有向图称为有向树。一个有向图的生成森林是由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。