数据结构--图

图

1.图的基本介绍

1）图的定义：

图(Graph)G由两个集合V和E组成，记为G=(V, E)，其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。V(G)和E(G)通常分别表示图G的顶点集合和边集合，E(G)可以为空集。若E(G)为空，则图G只有顶点而没有边。V(G)为空，则图不存在。

2）图的分类：

1* 按照图的边的指向分类：有向图（单向）、无向图（双向）。

2* 按照图的边的个数分类：稠密图（E（G）接近|E|== V^2），稀疏图相反，但是二者的分类边界没有明确规定，具体问题具体分类。

2.图的一些基本属性

1）一般来说，我们把单向的指向叫做 “弧” ，把双向的连接叫做 “边” （仅作为区分）

对于弧的范围：（0<=弧<=|V|^2），对于边的范围：（0<=弧<=|V|^2）。

2）简单路径：除了顶点和终点，其他的顶点最多出现一次，且顶点和终点不同（简单路径任意处都没有环）【简单路径则是从一个顶点到另一个顶点的非重复路径】

3）途径：可以有重复顶点，但不能有重复的边。

1* 无重复的顶点，必定不会重边。

2* 有重复的顶点，但是不会重边。

4）简单环（简单回路）：简单环是一种特殊的路径，其起点和终点相同，并且至少包含一个以上的顶点和边，形成了一个闭合的环路。（就是单个顶点不允许成环）

5）连通图：说的是对于无向图，任意两个顶点都是连通的。（联通就是存在路径）

6）强连通图：在有向图中对于任意两个顶点是连通的。（可以由无向图转变的）

7）弱连通图：在有向图中不是任意两个顶点是连通的。（不可以由无向图转变的）

8）权和网：在实际应用中，在图中的边上标记上具有某种含义的数值，该数值称为该边上的权，这些权可以表示两个顶点的距离和耗费等信息。这种带权的图称为网。（简单的说，加权图就叫做网）。

9）邻接点：无向图中任意两个顶点V和W中间存在边，那么这两个顶点互为邻接点；有向图中任意顶点V，若存在边E指向另一任意顶点W，则顶点W是顶点V的邻接点。（简单理解：无向图中连接的两点互为邻接点，有向图中A->B，则A是B的邻接点。）

10）度，入度，出度：无向图中，与A连接的边的数量就是A的度；有向图中，由A发射出去的弧的数量叫做出度，由A接收的弧的数量叫做入度

11）子图：图G1完全属于图G2，那么G1就称为G2的子图；任意单个顶点V，是其所在图的子图。

12）连通分量：一个图的连通分量是指图中的一个子图，该子图是一个连通图（所有顶点都是连通的），并且不能再加入其他的顶点或边而保持连通性。换句话说，连通分量是图中的极大连通子图。如果一个图是连通的，那么它的连通分量只有一个，即整个图本身。但如果一个图不是连通的，那么它会由多个连通分量组成，每个连通分量都是一个极大连通子图，且任意两个连通分量之间没有边相连。（简单的说：一个连通图只有一个极大的连通分量就是自己本身；一个非连通图一定是由多个连通图组成的，而且每个连通图都是一个极大的连通分量，而且，两个任意两个连通分量之间没有边相连）

13）强连通分量：与上面的类似，只不过针对于有向图

14）连通图的生成树：对连通图进行遍历过程，经过的顶点和边的组合可以看做树，这棵树叫作该连通图的生成树；因对树的遍历可能存在多种路径，那么一个连通图也可能存在多棵生成树。

15）生成森林：非连通图可分解为若干连通分量，将每个连通分量生成树就是该图的生成森林。

3.图的表示法：1）边列表 2）邻接矩阵 3）邻接表

1）边链表：一种可能的存储和表示一个图的方法。如图：（结点链表，边链表【加权的】）

缺点：在时间复杂度的角度，这种存储方式对于一些频繁的操作并不是很高效。

例如：找到给定结点的相邻节点，需要对边链表进行线性遍历，但是我们直到边的阶数是V^2，相当于O(N^2)的复杂度。因此所有以边为阶数的操作都会非常耗时。

2）邻接矩阵（适用于稠密图）（大小：V * V）【其中0~7是结点索引，0/1代表两节点之间是否存在连接】

优点：对于一个稠密图来说，他的表示可以极大程度上减小解决问题的时间复杂度。（ 方便检查任意一对顶点间是否存在边 ，方便找任一顶点的所有“邻接点”，方便计算任一顶点的“度”（有向图：从该点发出的边数为“出 度”，指向该点的边数为“入度”）；无向图：对应行（或列）非 0元素的个数为该顶点的度。 有向图：对应行非0元素的个数为出度，对应列非0元素的个数为入度）

缺点：对于一个稀疏图来说，他的表示非常浪费内存

3）邻接表：对于大多数的稀疏图来说，无疑是较好的选择，我们把空间复杂度降为了O(V)，时间上也能保证最大为O(V)。（方便找任一顶点的所有“邻接点” ，节约稀疏图的空间，需要 N个头指针 + 2E个结点（每个结点至少 2个域，若带权重，结构体需添加权重域）。对无向图：方便计算每个顶点的度；对有向图：只能计算“出度”；需要构造“逆邻接表”（存指向自己 的边）来方便计算“入度” 。）

无权的图

加权的图