图的基本理解

图

什么是图？

图是由顶点(Vertex)和边（Edge）组成的结构。

为什么会出现图这种结构？

在现实生活中的关系，不全是以“一对一”或”一对多“，而是复杂的多对多。

经典的”一对一“，“一对多”，”多对多“关系有：

1.线性结构（数组，链表，栈，队列） 只能出现一对一关系。

2.树形结构 一对多

3.图结构 可以表示多对多的关系

图 -->有向图 -->无向图

无向图

首先，我们先来讲无向图

无向图 = 顶点+没有方向的边。

假设有4个顶点：V0,V1,V2,V3

边集：{(V0,V1), (V0,V2), (V1,V3), (V2,V3)}

V0 —— V1

| |

V2 —— V3

无向图的核心术语：

1.顶点的度 度：与该顶点相连的边的数量

V0连接 V1 V2 那么V0的度为2

2.路径

3.环/回路

无向图的特例：

1.完全图 每对不同顶点之间都有一条边直接相连。

2.树 = 连通 + 无环的无向图

3.森林 = 多个树的集合

无向图的存储（领接矩阵和邻接表）

1.领接矩阵：

V0 V1 V2 V3

V0 0 1 1 0

V1 1 0 0 1

V2 1 0 0 1

V3 0 1 1 0

2.邻接表：

V0 → [V1] → [V2]

V1 → [V0] → [V3]

V2 → [V0] → [V3]

V3 → [V1] → [V2]

无向图的遍历：

1.深度优先遍历（DFS）

2.广度优先遍历 (BFS)

有向图

有向图 = 顶点+有方向的边

G = (V,E) V：顶点集合 E：有向边的集合，每条边是一个有序对

顶点V = {V0,V1,V2,V3} 边E = {<v0,v1>,<vo,v2>,<v0,v3>,<v1,v3>}

V0

/↓ ↘

↓ ↓ ↓

V1 V2

↓ /

V3

有向图的核心数据：出度和入度

出度 = 从顶点出去边的数量

入度 = 进入该顶点边的数量

强连通分量：在有向图当中，如果从顶点A可以到达顶点B，并且从顶点B也可以到达顶点A，那么称A和B是强连通性的。

拓扑排序：把有向无环图（DAG）的顶点排成一个线性序列，如果存在边A -> B 那么A在序列中一定会出现在B之前。

有向图不意味着遍历顺序也固定

图的方向性（固定）边有方向性 只可以单向移动。

图的遍历顺序，不固定，会利用回溯的方式。