数据结构_图（1_图的概述）

主要知识点

1. 图的概述
2. 图的存储结构
3. 图的遍历
4. 最小生成树
5. 最短路径
6. 拓扑排序
7. 关键路径

一、图的概述

1.1 图的基本概念

图由顶点集V和边集E组成，记为G=(V,E)。e属于E，e=(u,v)表示无向边，e=<u,v>表示有向边。E可以是空集，此时G只有顶点，没有边，称为零图。

1.1.1无向图

V1 = {0,1,2,3,4}
E1 = {(0,1),(1,2),(1,4),(2,3),(3,4)}

1.1.2有向图

V2 = {v0, v1, v2, v3, v4}
E2 = {<v0, v1>, <v0, v2>, <v2, v3>, <v3, v0>, <v3, v4>}

1.1.3权和网

加权图称为网。

1.1.4完全图

无向图中，当边的数量=n(n - 1)/2时，为完全图。
有向图中，当边的数量=n(n - 1)时，为完全图。

1.1.5稠密图和稀疏图

e少为稀疏图，反之为稠密图。

1.1.6子图与生成子图。

略

1.1.7邻接点

无向图中，边(u, v)，则称u与v互为邻接点。
有向图中，边<u, v>，则称顶点u邻接到v，顶点v邻接自u。

1.1.8顶点的度

无向图中，顶点的度就是与之关联的边的数量。
有向图中，度分为出度和入度。

1.1.9路径与回路

路径是从顶点u到顶点v所经过的顶点序列。
路径长度是指路径所经过的边的数量。
如果路径的首尾顶点相同则此路径称作回路或环。
在网中，路径长度为所经过边的权值的和。

1.1.10连通图和连通分量

无向图中，u到v有路径，则称u和v是连通的。若任意两个顶点是连通的，则是连通图。

1.1.10强连通图和强连通分量

有向图中，若任意两个顶点是连通的，则是强连通图。