【数据结构】图

一、图的基本概念
二、图的存储结构
- 邻接矩阵表示法
- 邻接表表示法
三、图的遍历
四、生成树
- 最小生成树
- - 克鲁斯卡尔算法
  - 普里姆算法

一、图的基本概念

图：一个图G是由两个集合V和E组成的，V是有限的非空顶点集。E是V上的顶点对所构成的边集，分别V(G)和E(G)来表示图中的顶点集和边集记作G =( V, E)
顶点：图中每个结点称为顶点
无向图 ：例如图（a）,每条边都没有方向，则称为无向图，在无向图中，边是无序的，并用圆括号表示，例如图(a)的两种表示

V(G1) = {V1,V2,V3,V4,V5};
E(G1) = {(V1,V2),(V2,V5),(V2,V3),(V3,V5),(V3,V4),(V1,V4)};

有向图:例如图（b），每条边都用箭头指明了方向，则称为有向图。边是有序的，并用尖括号表示,例如图（b）的两种表示方法为

V（G2）= {V1,V2,V3,V4}；

E（G2）= {<V1,V3>,<V3,V4>,<V4,V1>,<V1,V2>};

无向完全图
- 如果任意两个顶点间都有一条直接边相连，则称其为无向完全图
- 具有n个顶点的无向完全图中，有 n(n-1) / 2 条边
有向完全图
- 任意两个顶点间都有方向互为相反的两条边相连，则称该图为有向完全图
- 具有n个顶点的有向完全图中，有 n(n-1)条边
子图
- 设有两个图G = （V，E）和 G1 = （V1,E1）
- 且满足条件：V1是V的子集，E1是E的子集，则称G1为G的子图。
路径、路径长度、简单路径和简单回路
- 路径:在图G中从顶点Vp到顶点Vq的一条路径，路径是顶点序列;注：有向图的路径也是有向的
- 路径长度:路径长度是指在这条路径上边的数目 ;路径(v1,v2),(v2,v3), (v3,v5) 记作(v1,v2,v3,v5),其路径长度为3
- 简单路径: 除了第一个顶点和最后一个顶点之外，其余顶点都不同的路径，称为简单路径。例如：（v1,v2,v3,v1）或（v1,v2,v3,v4）
- 简单回路：第一个顶点和最后一个顶点相同的简单路径为简单回路；例如：（v1,v2,v3,v1）
连通图（无向图）与强连通图（有向图）
- 在无向图中，若从一个顶点Vi到另一个顶点Vj(且i != j)有路径则称顶点Vi和Vj是连通的。若V(G)中每一对不同的顶点都是连通的，则称G是连通图。
- 在有向图中，若V(G)中每一对不同的顶点Vi和Vj。都存在从Vi到Vj及Vj到Vi的路径，则称G是强连通图。
- 注：对于n个顶点的无向图G，若G是连通图，则最少有n-1条边
度、入度和出度
- 度：在无向图中，顶点所具有的边的数目称为该顶点的度。
- 入度：在有向图中，以某顶点为终点的边的数目，称为该顶点的入度。
- 出度：在有向图中，以某顶点为尾（始点）的边的数目称为该顶点的出度。
- 注：一个顶点的出度与入度之和等于该顶点的度
- 度与边的关系：所有顶点的度数之和等于边的二倍
有权图
- 对于图G = (V,E) ，若图中的每条边都具有一个相关的数，则这种与图的边相关的数称为该边的权，这种带权的图就称为权图或权网