图

各种定义

图：G(V,E) 由顶点和边组成，顶点集V有穷非空，边集E可以为空。
无向图：任意两个顶点之间的边都是无向边。(A,B)
有向图：任意两个顶点之间的边都是有向边。<A,B>
简单图：图中不存在顶点自身到自身的边，且同一条边不重复的图。
无向完全图：任意两个顶点间都有边的无向图。顶点数为n时的边数：n(n-1)/2
有向完全图：任意两个顶点间都存在方向相反的弧的有向图。顶点数为n时的弧数为：n(n-1)
稀疏图：有很少条边或弧的图
稠密图：与上相反。
权：与边或弧相关的数。
网：带权图
G’为G的子图：G’中的所有边和顶点都是G中的子集。
互为邻接点：无向图中，v和v’之间有边相连。
顶点的度：和顶点相关联的边的数量。记为TD(V)。
顶点v邻接到v’，顶点v’邻接自v：存在弧<v,v'>
V的入度：以顶点V为头的弧的数目。
V的出度：以顶点V为尾的弧的数目。
顶点V的度：入度+出度
连通图：任意两个顶点都有路径的无向图。

邻接矩阵

用两个数组来表示图：

1. 一维数组存储顶点
2. 二维数组存储弧或边