五味子

小舟从此逝,江海寄余生

0%

图论基础

图论基础

各种定义

定义实在太多了,有空再整理

  1. G(V, E)表示一个图(graph),V表示点集(vertex),E表示边集(edge)。
  2. (vi,vj)表示无向边。
  3. <vi, vj>表示有向边,也称为弧,vi为弧尾,vj为弧头。
  4. 简单图:不存在顶点到自身的边,且同一条边不重复出现。
  5. 无向完全图:无向图中任意两个顶点都存在边。
  6. 有向完全图:有向图中任意两个顶点都存在方向相反的两条弧。
  7. 稀疏图/稠密图:很少/多边或弧。
  8. 网:带权的图。
  9. 子图:V’和E’分别是V和E的子集的图。
  10. 度:无向图中与v相关联的边的数目。
  11. 入度/出度:有向图中以v为头/尾的弧。
  12. 路径及路径长度:略。
  13. 回路或环:略。
  14. 简单路径:序列中顶点不重复出现的路径。
  15. 简单回路或简单环:除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路。
  16. 连通图:略。
  17. 联通分量:无向图中极大连通子图。
  18. 强连通图:有向图中,任意点可到达。
  19. 强连通分量:有向图中极大强连通子图。
  20. 生成树:极小的联通子图。
  21. 生成森林:略。

图的存储结构

邻接矩阵

用一个二维数组来存储图中的边或弧的信息。

arc[i][j]表示i到j有边。值可以表示为边的权值。

适用于稠密图

邻接表

数组+链表的存储方式

以v[i]为头结点创建链表,链表存储与i相连的边

邻接表存储有向图的出度

也可以根据需要创建逆邻接表存储有向图的入度

适用于足够稀疏的图

十字链表

结合邻接表与逆邻接表,既保存图的入度,又保存图的出度。

顶点结构体:

data:结点编号

firstin:指向第一个入边

first:指向第一个出边

边表结点结构体:

tailvex:弧起点的顶点编号

headvex:弧终点的顶点编号

headlink:指向同一个终点的指针域

taillink:指向有同一个起点的指针域

根据以上构造链表即可

适用于有向图

邻接多重表

顶点结构体:

data:顶点编号

firstedge:指向一条边(data为顶点)

边集结构体:

ivex:边的一个顶点编号

ilink:指向一条边,该边的jvex与本身的ivex相同

jvex:边的另一个顶点编号

jlink:指向一条边,该边的ivex与本身的jvex相同

适用于无向图

边集数组

由一个顶点数组和一个一维结构体数组组成

结构体数组:

begin:边的起点

end:边的终点

weight:权值

只存储边,适用于对边依次处理的操作

最小生成树算法

Prim算法

kruskal算法