一、图论基础

多对多的关系

定义：G=(V,E) Vertex顶点 Edge边

顶点的集合V={v1,v2}

边的结合E={(v1,v2)}

无向图(1,2)

有向图<1,2>

依附：边(v1,v2)依附于顶点v1,v2

路径：（v1,v2)(v2,v3)

无权路径最短：边最少

连通：一个点到另外一个点，有路径可通

无向图的连通图：图中任意两点之间均有路径连通

有向图的强连通图：任意相异成对顶点之间均有路径可通

子图

极大连通子图（连通分量/强连通分量）

完全图：图中所有的边均存在

无向完全图边数：Cn2=n(n-1)/2

有向完全图边数：An2=n(n-1)

简单图：没有指向自己的路径

简单路径：除起点和终点可以相同，其他点不可重复

度：几条邻接关系，最多n-1

有向图：入度、出度

n个顶点无向图中，最少n-1条边，可以是连通图

n个顶点无向图中，最少C(n-1)2 + 1条边，一定是连通图

二、图的存储结构

2.1 邻接矩阵

二维数组，存储顶点之间的边关系

唯一的

适合边多，稠密图

2.2 邻接链表

不唯一，表示与表头顶点连接

适合边少，稀疏图

结构体：

（1）顶点个数

（2）边的条数

（3）邻接矩阵 

创建：

① 顶点个数

② 矩阵申请

③ 放边（a,h）矩阵对应行列赋值