图的概念
图（Graph）是由一组顶点(V)和一组能够将两个顶点相连的边(e)的非空有限集组成的。
例如：
定义一个图G=(V,E)，V={V1,V2,V3,V4},E={E1,E2,E3,E4,E5,E6}
E1=<V1,V2> E2=<V1,V3> E3=<V1,V4> E4=<V2,V3> E5=<V3,V2> E6=<V3,V3>
一些定义
基本概念
- 有向边：一条边所代表的顶点是有序的，则为有向边，也称弧，例如< V1,V2 >和< V2,V1 >是不同的两个边或弧。
- 无向边：一条边所带表的顶点是无序的，则为无向边，例如(V1,V2)和(V2,V1)是同一个边。
- 弧的头尾：一条边从V1指向V2，则V1为弧尾，V2为弧头。
- 度：一个顶点的度是指与它相连的边的数目，入度指入边数，出度指出边数。
- 路径：从顶点V1到V2的路径是指从V1到V2的边所表示的顶点序列。
- 权值：与图的边相关的数称为权值，带权值的图称为网。
- 连通：若两个顶点之间存在路径，则称这两个顶点是连通的。
图的分类
- 简单图：不存在顶点到自身的边且一条边不重复出现，这样的图称为简单图。
- 无向图：图中任意一条边代表的顶点是无序的，则为无向图。
- 有向图：图中任意一条边代表的顶点是有序的，则为有向图。
- 完全图：图中任意两个顶点之间都存在边，则为完全图。
- 连通图：图中任意两个顶点之间都存在路径，则为连通图，否则为非连通图。