【数据结构 | 每日一题】图的概念辨析

图的概念辨析

考点分析：我们学习数据结构图的第一小节就是：图的基本概念，我们会发现图的概念非常多且有些概念之间又很像，而对于初学者来说，相比树的概念是不好理解的，很容易搞混，因此做了这么一个辨析带大家一起理解基础上进行一个记忆。

首先我们先把图的概念，分一个大体的框架出来，我个人习惯把有向图和无向图相似的概念放在一起对比记忆，更容易抓住特性。

1. 完全图（好理解）

   • 无向完全图：任意两个点都有边相连
   • 有向完全图：任意两个点都有两条相反的边相连
   • 注意：和连通图进行区分（两个点有路径就行，不一定要有边！）

2. 连通图（这一块容易混淆，如极大、极小等概念）

   • 首先先理解基本概念
     • 连通子图：任意两个点之间存在路径的子图（注意不是所有子集都构成子图，首先得是个图）
     • 对于无向图来说，如果是连通图，边数必须大于等于n-1
   • 极大连通子图：不被任何一个连通子图所包含，边数要尽可能的多
   • 连通分量：无向图的极大连通子图（注意它不是一个新的概念）
     • 连通图的连通分量唯一，就是本身（因为它是极大连通子图，边要尽可能的多）
     • 非连通图的连通分量不唯一（对比记忆）
   • 极小连通子图：包含边数最少得连通子图（顶点数是没有要求的，只要是子集就行）
   • 生成树：含n个顶点，n-1条边的极小连通子图（顶点数有要求了，包含所有顶点）

3. 强连通图（有向图更强：这个强仅仅是名字多一个“强”！）

   • 任意两个顶点都存在顶点的有向图（强连通图和连通的定义是一样的，只是变成了有向图而已）
   • 强连通分量：有向图的极大连通子图

4. 顶点的度（记住两个公式）

   • 无向图全部顶点的 度之和等与边的两倍
   • 有向图的全部顶点的 入度之和==出度之和==边数

题目

讲解笔记

讲解视频链接：【数据结构 | 每日一题】图的概念辨析