图的定义

在图中，通常将数据元素称为顶点，顶点之间的关系称为边。图由有限顶点集V和有限边集E组成，记为G=(V，E)，其中顶点总数|V|记为n，边的总数|E|记为e。

表示顶点v指向顶点w的有向边，或称为弧，其中v为起点，w为终点，起点和终点的顺序不能随意颠倒。如果图中的边全都是有向边，则该图称为有向图。

(v,w)表示顶点v和顶点w之间有连线，但是没有方向，相当于和都存在，这种没有方向的边就称为无向边。如果图中的边全都是无向边，则该图称为无向图。

图的术语

• 子图：假设两个图G=(V，E)和G’=(V’，E’)，如果V’是V的子集，E’也是E的子集，则G’称为G的子集

• 完全图：包含所有可能的边的图称为完全图。无向完全图包含n(n-1)/2条边，有向完全图包含n(n-1)条弧
• 邻接顶点：简单的说，有直接连线的两个顶点互称为邻接顶点
• 度、出度和入度：顶点的度是指依附该顶点的边数。有向图的度又分为出度和入读，出度就是以该顶点为起点的弧的数目，入度就是以该顶点为终点的弧的数目，且度数=出度+入度。而无向图就没有出度和入度的说法
• 权和网：有时图中的边需要附加属性信息，比如：顶点之间的距离，这些信息就称为权，带权的图称为带权图或简称为网

• 回路：从图中某个顶点出发，经过某条路径，最后又回到顶点生成的路径就称为回路
• 连通图：在无向图中，若顶点v到顶点w有路径，则称为顶点v到w是连通的。若图中任意两个顶点都是连通的，则称该图为连通图。连通分量是指无向图中的极大连通子图

• 强连通图：在有向图中，若顶图中任意两个顶点v和w，既有点v到顶点w的路径，也有点w到顶点w的路径，则称为强连通图。强连通分量是指有向图中的极大连通子图

• 生成树：如果连通图G的一个子图是一棵包含G的所有顶点的树，则该子图称为G的生成树。连通图的生成树是含有所有顶点且只有n-1条边的连通子图