数据结构-图

参考:《大话数据结构》第7章 图

学习路径如下:

  1. 图的基本定义本文学习内容
  2. 顶点/边/图的关系
  3. 图的存储结构
  4. 深度/广度优先遍历
  5. 最小生成树

完整工程:zjZSTU/graph_algorithm

什么是图

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:$G(V,E)$,其中,$G$表示一个图,$V$是图$G$中顶点(vertex)的集合,$E$是图$G$中边(edge)的集合

注意:图可以没有边,不能没有顶点

  • 子图

假设有两个图$G(V,E)$和${G}’({V}’,{E}’)$,如果${V}’\subseteq V$且${E}’\subseteq E$, 则称${G}’$为$G$的子图(subgraph

简单图

图中不存在顶点到自身的边,且同一条边不重复出现,称这样的图为简单图

之后的讨论都是基于简单图进行的

权重/网

  • 权重(weight

与边相关的数称为权重(weight

带权重的图通常称为网(network

有向图/无向图

参考:

数据结构与算法——图论基础与图存储结构

无向图

  • 无向边(undirected edge

若顶点$x$和$y$之间的边没有方向,则称该边为无向边,用无序偶对$(x,y)$表示。$(x,y)$与$(y,x)$意义相同,仅表示$x$和$y$之间有连接

  • 有向边(directed edge

若顶点$u$和$v$之间的边有方向,则称该边为有向边(也称为弧$Arc$),用有序偶对<u,v>表示,表示从$u$指向$v$。称$u$为该边的起点(origin)或尾顶点/弧尾(tail),称$v$为该边的终点(destination)或头顶点/弧头(head

  • 无向图

图中任意两个顶点之间的边都是无向边,称该图为无向图(undirected graph

  • 有向图

图中任意两个顶点之间的边都是有向边的图称为有向图(directed graph

  • 混合图

包含无向边和有向边的图称为混合图(mixed graph

注意:无向边用小括号$()$表示,有向边用尖括号$<>$表示

稀疏图/稠密图/完全图

  • 稀疏图(sparse graph

顶点很少互相连接的图

  • 稠密图(dense graph

顶点几乎都能两两连接的图

  • 完全图(complete graph

每个顶点均与除自身之外的其他顶点连接的图

  • 无向完全图

在无向图中,如果任意两个顶点之间都存在边,则称该图为无向完全图

含有$n$个顶点的无向完全图有$\frac {n\times (n-1)}{2}$条边

  • 有向完全图

在有向图中,如果任意两个顶点之间都存在方向互为相反的两条弧,则称该图为有向完全图

含有$n$个顶点的有向完全图有$n\times (n-1)$条边

坚持原创技术分享,您的支持将鼓励我继续创作!