数据结构-图2

发表于 2019-08-15 更新于 2021-04-04 分类于数据结构/data structure 阅读次数：

本文字数： 1.4k 阅读时长 ≈ 3 分钟

学习路径如下：

度/入度/出度

对于无向图$G=(V,E)$，如果边$(u,v)\in E$，则称顶点$u$和$v$互为邻接点（adjacent），即$u$和$v$相邻接

对于有向图$G=(V,E)$，如果弧<u,v>$\in E$，则称顶点$u$邻接到顶点$v$，顶点$v$邻接自顶点$u$

顶点$v$的度（degree）是和$v$相关联的边的数目，记为$TD(v)$

以顶点$v$为头的弧的数目称为$v$的入度（InDegree），记为$ID(v)$

以顶点$v$为尾的弧的数目称为$v$的出度（OutDegree），记为$OD(v)$

对于有向边<u,v>而言，顶点$u$是弧尾，顶点$v$是弧头，所以$ID(v)=1$, $OD(u)=1$

对无向图而言，仅存在度的概念；对于有向图而言，同时还存在入度和出度的概念，入度和出度之和就是该顶点的度：$ TD(v) = ID(v) + OD(v)$

图$G(V,E)$中从顶点$u$到顶点$v$的路径（path）是一个顶点序列$(V=v_{0},v_{1},...,v_{m})$，其中$v_{0}=u, v_{m}=v, (v_{i-1}, v_{i})\subseteq E,1\leq i\leq m$

第一个顶点和最后一个顶点相同的路径

序列中顶点不重复出现的路径

除了第一个顶点和最后一个顶点相同外，其余顶点不重复出现的回路

在一个无向图$G$中，若从顶点$v_{i}$到顶点$v_{j}$有路径相连，则称$v_{i}$和$v_{j}$是连通的。如果图中任意两点都是连通的，那么图被称作是连通图

在图$G$中，如果对于每一对$u,v\subseteq V, u\neq v$，从$u$到$v$和从$v$到$u$都存在路径，则称$G$是强连通图

连通图是相对于无向图而言的，强连通图是相对于有向图而言的

无向图$G$的极大连通子图称为$G$的连通分量（connected component）。任何连通图（connected graph）的连通分量仅有一个，即是其自身，非连通的无向图有多个连通分量

有向图中的极大强连通子图称做有向图的强连通分量

如果连通图$G$的一个子图是一颗包含$G$的所有顶点的树，则该子图称为$G$的生成树（spanning tree）

连通图的生成树是一个极小的连通子图，包含全部$n$个顶点，但只有足以构成一棵树的$n-1$条边

对于生成树而言，前提是它是连通图，也就是顶点之间有连接

给定无向图$G=(V,E)$，$(u,v)$代表连接顶点$u$和$v$的边，$w(u,v)$代表此边的权重，如果存在生成树$T$使得$w(T)$最小（权值之和最小），那么称$T$为最小生成树(MST, Minimum Spanning Tree)