数据结构-图2
学习路径如下:
度/入度/出度
对于无向图$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$
- 回路或环(cycle)
第一个顶点和最后一个顶点相同的路径
- 简单路径
序列中顶点不重复出现的路径
- 简单回路或简单环
除了第一个顶点和最后一个顶点相同外,其余顶点不重复出现的回路
连通图/连通分量
- 连通图
在一个无向图$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
)
相关阅读
- 《大话数据结构》第7章 图
- 连通图
- 连通分量
- 生成树算法
- 最小生成树
- 最小生成树之Kruskal算法