图（graph）是一种网状数据结构，图是由非空的顶点集合和一个描述顶点之间关系的集合组成。其形式化的定义如下：
Graph = ( V , E )
V = {x| x∈某个数据对象}
E = {<u , v>| P(u , v)∧(u,v∈V)}
V 中的数据元素通常称为顶点（Vertex），R 是两个顶点之间关系的集合。
P(u , v)表示u 和v 之间有特定的关联属性。若<u , v>∈E，则<u , v>表示从顶点u 到顶点v 的一条弧或边，并称u 为弧尾或起始点，称v 为弧头或终止点。
有向图
图中的顶点之间的连线是有方向的，这样的图称为有向图（directedgraph）。无向图
若<u , v>∈E 则必有<v , u>∈E，即关系E 是对称的，此时可以使用一个无序对(u , v)来代替两个有序对，它表示顶点u 和顶点v 之间的一条边，此时图中顶点之间的连线是没有方向的，这种图称为无向图（undirected graph）。
我们将弧和边统一称为边（edge）。
并且我们还约定顶点集与边集都是有限的，并记顶点与边的数量为|V|和|E|。通过图的以上形式化定义，我们看到我们所讨论的“图”，并非通常所指的图形、图像或数学上的函数图。
简单图
设G=(V，E)是图，若G中既无吊环又无多重边，则称G是简单图(simplegraph)。邻接点、邻接边
对于无向图G = ( V , E )，如果边(u , v) ∈E，则称顶点u 与顶点v 互为邻接点。对于有向图G = ( V , E )，如果边<u , v> ∈E，则称定点u 邻接到顶点v，顶点v 邻接自顶点u，或称v 为u 的邻接点，u 为v 的逆邻接点。从顶点u 出发的边也称为u 的出边或邻接边，而指向顶点u 的边也称为u 的入边或逆邻接边。顶点的度、入度、出度
顶点的度（degree）是指依附于某顶点v 的边数，通常记为TD (v)。
在有向图中，要区别顶点的入度与出度的概念。顶点v 的入度（in degree）是指以顶点为终点的边的数目，记为ID (v)；顶点v 出度（out degree）是指以顶点v 为起始点的边的数目，记为OD (v)。对于有向图有TD(v) = ID(v) ＋ OD(v)。在无向图中每条边都可以看成出边，也可以看成入边，此时TD(v) = ID(v) = OD(v)。
对于任何无向图G = ( V , E )，都有ΣTD(v ) = 2|E|，其中v ∈V
因为在无向图中计算各点度数之和时，每条边都恰好被统计了两次。另外对于任何有向图G = ( V , E )，都有∑ID(v ) = ∑OD(v ) = |E|，其中v∈V；这是因为在计算各个顶点的出（入）度的过程中，每条有向边都只被统计了一次。由此对于有向图而言TD(v ) = ID(v )＋ OD(v ) = 2|E|。通过以上分析，我们有以下结论：
在任何图G = ( V , E )中，|E| = (∑TD(v ))/2
假设图中顶点个数为n，边数为m。
在无向图中当每个顶点都与其余n-1 个顶点邻接时，图的边数达到最大，此时图中每两
个顶点之间都存在一条无向边，边数m 为n 个顶点任意取出2 个的组合数，即m = n(n-1)/2。同样有向图中当每个顶点都有n-1 条出边并有n-1 条入边时，图中边数达到最大，此时图中每两个顶点之间都存在方向不同的两条边，边数e 为在n 个顶点中任意取出2 个并进行排列的排列组合数，即m = n(n-1)。
假设在图G = ( V , E )中有n 个顶点和m 条边。
1.若G 是无向图，则有0 ≤ m ≤ n(n-1)/2。
2.若G 是有向图，则有0 ≤ m ≤ n(n-1)。
由此，在具有n个顶点的图中，边的数目为Ο(n )。由于图中边数与顶点数并非线性关系，因此在对有关图的算法时间复杂度、空间复杂度进行分析时，我们往往以图中的顶点数和边数作为问题的规模。
完全图 、稠密图、稀疏图
有n(n-1)/2 条边的无向图称为无向完全图；有n(n-1)条边的有向图称为有向完全图。有很少边（如m < n log n）的图称为稀疏图，反之边较多的图称为稠密图。-
子图
设图G = ( V , E )和图G' = ( V' , E' )。
如果V'⊆ V 且E'⊆ E ，则称G'是G 的一个子图（subgraph）。以图7-1（a）为例，若V' =
{ a , b , c , d }且E' = {( a , b ) , ( a , c ) , ( a , d )}，则G' = ( V' , E' )就是图G 的子图。
如果V'= V 且E'⊆ E ，则称G'是G 的一个生成子图（spanning subgraph）。
路径、环路及可达分量
所谓图中的一条通路或路径（path），就是由m+1 个顶点与m条边交替构成的一个序列ρ= { v , e , v , e , v , … , e , v }，m ≥ 0，且e = (v , v )，1 ≤ i ≤ m。路径上边的数目称为路径长度，计作|ρ|。长度|ρ| ≥ 1 的路径，若路径的第一个顶点与最后一个顶点相同，则称之为环路或环(cycle)。如果组成路径ρ的所有顶点各不相同，则称之为简单路径（simple path）；如果在组成环的所有顶点中，除首尾顶点外均各不相同，则称该环为简单环路（simple cycle）。如果组成路径ρ的所有边都是有向边，且e 均是从v 指向v ，1 ≤ i ≤ m，则称ρ为有向路径，同样可以定义有向环路。在描述简单图的路径或环路时，我们只需要依次给出组成路径或环路的各个顶点，而不必再给出具体的边。
在有向图G 中，若从顶点s 到顶点v 有一条通路，则称v 是从s 可达的。对于顶点s，从 s 可达的所有顶点所组成的集合，称作 s 在 G 中对应的可达分量。连通性与连通分量
在无向图中，如果从一个顶点v 到另一个顶点v (i≠j)有路径，则称顶点v 和v 是连通的。如果图中任意两顶点v 、v ∈V，v 和v 都是连通的，则称该图是连通图（connected graph）。所谓连通分量（connected component），是指无向图的极大连通子图。显然任何连通图的连通分量只有一个，即本身。强连通图、强连通分量
在有向图中，若图中任意一对顶点v 和v (i≠j)均有一条从顶点v 到另一个顶点v 的路径，也有从v 到v 的路径，则称该有向图是强连通图。有向图的极大强连通子图称为强连通分量。显然任何强连通图的强连通分量只有一个，即本身。
- 无向图的生成树
对于无向图G = ( V , E )。如果G 是连通图，则G 的生成树（spanning tree），是G 的一个极小连通生成子图。
原图
一棵有n 个顶点的生成树有且仅有n-1 条边。如果一个图有n 个顶点和小于n-1 条边，则是非连通图。如果它有多于 n-1 条边，则一定有环路，不是极小连通生成子图。但是，有n-1 条边的生成子图不一定是生成树。
如果在生成树中确定某个顶点作为根结点，则生成树就可以成为我们在之前介绍的
树结构。
- 权与网
在实际应用中，图不但需要表示元素之间是否存在某种关系，而且图的边往往与具有一定实际意义的数有关，即每条边都有与它相关的实数，称为权。这些权值可以表示从一个顶点到另一个顶点的距离或消耗等信息，在本章中假设边的权均为正数。这种边上具有权值的图称为带权图（weighted graph）或网（network）。
图定义_6.PNG
