图（Graph）是一种数据结构，将其简化为顶点（Vertrx）和边（Edge）的组合，采用形式化的定义，定义一个图：
Graph=(V,E)
其中V为顶点的有限集合，V={x|x∈dataobject}，记为V(Graph)；E是边的有限集合，表示两个顶点之间的关系，E={
2、图的基本术语
（1）顶点、邻接点、有向图、无向图
若这条线从x指向y，则称x为起始点（弧头），称y为终结点（弧尾），称这条边为弧（arc），此时的图为有向图。若当P
图1有向图和无向图
图1(a)中的G1为有向图，根据定义可表述为：G1=(V1,E1)，其中：V1为端点的集合，V1={v1,v2,v3,v4,v5}；E1为弧的集合，E1={
图1(b)中的G2为无向图，根据定义可表述为：G2=(V2,E2)，其中：V2为端点的集合，V2={v1,v2,v3,v4}；E2为边的集合，E2={(v1,v2),(v1,v3),(v1,v4),(v3,v4)}。
（2）完全图
若一个无向图中的每两个顶点之间都存在一条边，则称这个无向图为无向完全图（如图2(a)中的G1）。假设图中顶点的数目为n，显然，无向完全图包含n(n-1)/2条边。
图2完全图
若一个有向图中的每两个顶点都存在方向相反的两条弧，则称该图为有向完全图（如图2(b)中的G2）。假设图中顶点的数目为n，显然，有向完全图包含n(n-1)条边。
（3）顶点的度
顶点的度（degree）是指依附于某顶点vi的边数，通常记为TD(vi)。
在无向图中，依附于某顶点的边的数目称为该顶点的度。如图7-1(b)中，顶点v1的度为：TD(v1)=3；顶点v2的度为：TD(v2)=1；无向图G2的度为8。
在有向图中，度又分为出度和入度：以顶点vi为弧头的边的数目，称为顶点vi的出度,记为OD(vi)；以顶点vi为弧尾的的边的数目，称为顶点vi的入度，记为ID(vi)。顶点vi的出度与入度之和，称为顶点vi的的度。如图7-1(a)中顶点v3的出度为：OD(v3)=1，入度为：ID(v3)=2；则顶点v3的度为TD(v3)=3。
假设图中顶点的数目为n，边的数目为e，每个顶点的度为di（0in-1）,则有：
也就是说，一个图中所有顶点度的和等于图中边的数目的两倍，这是因为图中的每条边连接两个邻接点，在计算度时分为出度和入度计算了两次。
（4）稠密图、稀疏图
若一个图的边数很多，接近完全图，称其为稠密图。反之，若一个图的边数很少（e （5）子图 假设有两个图分别为G=(V,E)和G′=(V′,E′)，若V′*是V的子集，E′是E的子集，则称图G′是图G的子集。如图1(c)中G3为1(b)中G2的子图。 （6）边的权、网图 边上带有权值的图称为网图或者网络（network）。如图3(a)中的G1为有向网图，3(b)中的G2为无向网图。 图3网图 （7）路径、路径长度、简单路径 存在一个图G=(V,E)，从一个顶点p到另一个顶点q的路径为一个顶点序列，假设这个序列为(p,v1,v2,…,vn,q)。若图G是无向图，则边(p,v1)、(v1,v2)、…、(vi,vj)、…、(vn-1,vn)、(vn,q)属于E(G)。若图G是有向图，则边 路径长度指一条路径上经过的边的数目。如图3(a)G1中的路径A(v1,v3,v4)和路径B(v1,v5,v3,v4)，是从顶点v1到v4的两条路径，路径长度分别为2和3。 若一条路径上除去起点和终点，其余顶点各不相同，则称此路径为简单路径。如上文提到的路径A和路径B，都是简单路径。 （8）回路（环）、简单回路 若在一条路径上起点和终点为同一个顶点，则称这条路径为回路或者环。起点与终点相同的简单路径称为简单回路或者简单环。 （9）平行边、重数、自环、简单图 在无向图中，如果关联一对顶点的无向边多于一条，则称这些边为平行边，称平行边的条数为重数。 在有向图中，如果关联一对顶点的有向边多于一条，且方向相同，则称这些边为平行边。 自环是一条边的起点和终点为同一个顶点的边。 既不含平行边也不含自环的图称为简单图。 （10）连通、连通图、连通分量 在无向图中，若顶点p到顶点q之间有路径，则称顶点p和顶点q是连通的。若G中任意两个顶点都连通，则称无向图G为连通图。无向图G中的极大连通子图称为连通分量。显然，连通图中只有一个连通分量，即它本身；非连通图中有不止一个连通分量。图4中给出了非连通图G与它的连通分量示例。 图4连通分量、生成树、生成森林 （11）强连通图、强连通分量 在有向图中，若任意两个顶点p、q之间，既存在从p到q的路径又存在从q到p路径，则称这个有向图为强连通图。有向图的极大强连通子图称为强连通分量。与连通图相同，强连通图中只有一个连通分量，即它本身；非强连通图中有不止一个连通分量。 （12）生成树 一个连通图的生成树，是包含了该连通图中全部顶点的一个极小连通子图。图的生成树不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。生成树必定包含连通图中的n-1条边，并且在这棵生成树上任意添加一条边（这条边是连通图G中包含的边），必定构成回路。图4(c)中给出了G的生成树示例。 需要注意的是，具有生成树的图一定是连通的。 （13）生成森林 在非连通图中，每个连通分量都可得到一个极小连通子图，即可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。如图4(c)就是非连通图G的生成森林。