type
status
password
date
slug
summary
category
URL
tags
icon
概念
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：，其中， 表示一个图， 是图 中顶点的集合， 是图 中边的集合。
注意：当线性表没有数据节点时，线性表为空表；树中没有节点时，树为空树；图可以没有边，但是在图中不允许没有顶点。
ㅤ | 邻接矩阵时间复杂度 | 邻接链表时间复杂度 | 空间复杂度 |
深度优先遍历(DFS) | |||
广度优先遍历(BFS) | |||
拓扑排序(入度 or DFS) | |||
二分图检测 | |||
环的检测 | ㅤ | ||
Dijkstra | 采用二叉堆或者斐波纳契堆 | ㅤ | |
Bellman-Ford |
因为邻接矩阵遍历边 | ㅤ | |
SPFA |
因为邻接矩阵遍历边 | ㅤ | |
Floyd | 需要将链表的边权重转移到矩阵 中 | ||
Kosaraju | ㅤ | ||
Tarjan | ㅤ |
有向图与无向图
- 无向边：若顶点 x 和 y 之间的边没有方向，则称该边为无向边(x,y)，(x,y) 与 (y,x) 意义相同，表示 x 和 y 之间有连接。
- 有向边：若顶点 x 和 y 之间的边有方向，则称该边为有向边，与表示的意义是不同的，表示从 x 连接到 y ，x 称为尾，y 称为头。表示从 y 连接到 x ，y 称为尾， x 称为头。
顶点与顶点的度
上述有向图中， 顶点的度为 3，其中出度为 2，入度为 1。
图分类
完全图
完全图：每个顶点都与其他顶点相邻接的图。
- 无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。（含有n个顶点的无向完全图有 条边）
- 有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条边，则称该图为有向完全图。（含有 n 个顶点的有向完全图有 条边）
连通图
无向图
在无向图G中，如果从顶点 到顶点 有路径，则称 和 是连通的，如果对于图中任意两个顶点 和 都是连通的，则称G是连通图(ConnectedGraph)。下图左侧是非连通图，右侧是连通图：
有向图
- 强连通
在有向图 中，如果从顶点 可以到达顶点 ，从顶点 可以到达顶点 ，则称 和 是连通的。如果再有向图中任意两个顶点 和 都是强连通的，则称 是强连通图(ConnectedGraph)。下图左侧是非强连通图，右侧是强连通图：
- 弱连通
把有向图 看作无向图，如果从顶点 到顶点 有路径，则称 和 是弱连通的，如果对于图中任意两个顶点 和 都是弱连通的，则称G是弱连通图(ConnectedGraph)。下图左侧是非弱连通图，右侧是弱连通图：
异质图
二分图
指标
度
存储
邻接矩阵
图的邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息。
数据结构
C++
创建图
C++
优缺点
- 邻接矩阵的优点：数组存储方式容易实现图的操作。例如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。
- 邻接矩阵的缺点：采用数组存储方式，图若有 个顶点则需要 个单元存储边(弧)，空间存储效率为。 当顶点数目较多，边数目较少时，此时图为稀疏图，这时尤其浪费空间。
邻接链表
邻接矩阵对于边数相对顶点较少的图，存在对存储空间的极大浪费的现象。因此这种存储方式对于稀疏图来说不是很合适。借鉴于线性表的解决方案，可以考虑对边或弧使用链式存储的方式来避免空间浪费的问题。
- 顶点表：图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过数组可以较容易地读取顶点信息，更加方便。另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
- 边表：图中每个顶点 的所有邻接点构成一个线性表，由于邻接点的个数不定，所以用单链表存储，无向图称为顶点 的边表，有向图则称为顶点 作为弧尾的出边表。
数据结构
C++
创建图
十字链表
那么对于有向图来说，邻接表是有缺陷的。关心了出度问题，想了解入度就必须要遍历整个图才能知道，反之，逆邻接表解决了入度却不了解出度的情况。那我们思考了：有没有可能把邻接表和逆邻接表结合起来呢？
数据结构
其中
tailvex 是指弧起点在顶点表的下标，headvex 是指弧终点在顶点表中的下标，headlink 是指针域(入)，指向终点相同的下一条边，taillink 是指针域(出)，指向起点相同的下一条边。如果是网，还可以再增加一个weight 域来存储权值。邻接多重表
如果在无向图的应用中，关注的重点是顶点，那么邻接链表是不错的选择，但如果更关注边的操作，比如对已访问过的边做标记，删除某一条边等操作，却是比较繁琐的。如下图所示，图中黄色标记的结点表示A-D之间的边，在邻接表中一条边需要两个结点表示。因此如果对于边的操作（标记或者删除）则需要访问两条链表。
因此可以仿照十字链表的方式，对边表结点的结构进行一些改造。
数据结构
其中
Data 是顶点的值，Ivex 和 Jvex 是与某条边依附的两个顶点在顶点表中的下标；ilink 指向依附顶点 Ivex 的下一条边，jlink 指向依附顶点 Jvex 的下一条边。这就是邻接多重表结构。