图－基本概念
- 图：顶点＋线
- 无向边 (A,B)
- 有向边 <A,B>，不能写成<B,A>，A是弧尾，B是弧头
- 简单图：没有到自身的边，没有重复的边
- 无向完全图：如果任意两个顶点之间都存在边
- 有向完全图：如果任意两个定点之间都存在方向互为相反的两条弧
- 有很少条边或弧的图称为稀疏图，反之为稠密图
- 网：边或弧上带权重的图
- 顶点的度：是与顶点相关联的边的数量（无向图）
- 树的总边数：所有顶点度之和的一半（无向图）
- 无向图分为出度和入度
- 无向图的弧的总数：等于所有节点的出度之和／入度之和
- 路径的长度是路径上的边或弧的数目
- 回路／环：第一个顶点到最后一个顶点相同的路径
- 简单路径：序列中顶点不重复出现的路径
- 简单回路：除了第一个和最后一个顶点，其余顶点不重复的回路
- 联通图：如果对于图中任意两个顶点都是联通的（无向图）
- 联通分量：无向图中的极大连通子图（无向图）
- 要是子图
- 子图要是连通的
- 连通子图含有极大顶点数
- 具有极大顶点数的连通子图包含以负于这些顶点的所有边
- 强联通图：任意两个顶点之间都存在相反方向的两条弧（有向图）
- 强连通分量：极大联通子图（有向图）
连通分量的疑惑
连通分量（无向图的极大连通子图）到底什么意思？？
- 无向非连通图，
相连的所有节点组成的子图就是一个连通分量。E/F和A/B/C/D都不相连，所以它们独自形成一个连通分量。而A/B/C组成的子图缺少了可连通的节点D，因此就不能称之为极大连通子图（连通分量） - 无向连通图，它的极大连通子图就是自身
图的存储结构（内存存储结构）
邻接矩阵
邻接表
图的遍历
深度优先
- 类似于树的先序遍历
- 如同人站在迷宫里，从一个顶点进去，每次选择未访问的最右边的顶点
- 红色线框标记部分；这是代码的核心，
循环＋递归实现了从每个节点深度进入，再递归回来，最终遍历所有节点 -
时间复杂度：O(
)
广度优先
- 类似于树的层级遍历
- 算法用到一个辅助队列，来记录需要访问的顶点顺序
- 从第一个顶点开始，与他连接的所有顶点就是第二层，依此类推
代码：
