图论算法
第一节 基本概念
• 一、什么是图？
• 很简单，点用边连起来就叫做图，严格意义上讲，图是一种数据结构，定义为：graph = （V ，E）。V 是一个非
空有限集合，代表顶点（结点），E代表边的集合。
• 二、图的一些定义和概念
• ( a) 有向图：图的边有方向，只能按箭头方向从一点到另一点。( a) 就是一个有向图。
• ( b) 无向图：图的边没有方向，可以双向。( b) 就是一个无向图。
• 结点的度：无向图中与结点相连的边的数目，称为结点的度。
• 结点的入度：在有向图中，以这个结点为终点的有向边的数目。
• 结点的出度：在有向图中，以这个结点为起点的有向边的数目。
• 权值：边的“ 费用”，可以形象地理解为边的长度。
• 连通：如果图中结点U ，V 之间存在一条从U 通过若干条边、点到达V 的通路，则称U 、V 是连通的。
• 回路：起点和终点相同的路径，称为回路，或“ 环”。
• 完全图：一个n 阶的完全无向图含有n* ( n- 1 ) / 2 条边；一个n 阶的完全有向图含有n* ( n- 1 ) 条边；
• 稠密图：一个边数接近完全图的图。
• 稀疏图：一个边数远远少于完全图的图。
•
• 强连通分量：有向图中任意两点都连通的最大子图。右图中，1 - 2 - 5 构成一个强连通分量。特殊地，单个点也算一
个强连通分量，所以右图有三个强连通分量：1 - 2 - 5 ，4 ，3 。
1
2
3
4
5
( a)
1
2
3
4
5
( b)
1
2
3
4
5
& 约定：不考虑顶点到其自身的边，也不允许一条边在
图中重复出现（即若( V
i
，V
j
) 或< V
i
，V
j
> 是E（G ）中
的一条边，则要求V
i
3V
j
），并设图G 的顶点数为n，
边数为e，则有如下性质：
&无向图：最多有n( n- 1 ) / 2 条边，即：0 5e 5n( n- 1 ) / 2
&有向图：最多有n( n- 1 ) 条边，即：0 5e 5n( n- 1 )
图的基本概念
图的基本概念
• 无向完全图：有n( n- 1 ) / 2 条边的无向图。
• 有向完全图：有n( n- 1 ) 条边的有向图。
• 权( W eigh t) ：与图的边或弧相关的数。
• 网（N etwork) ：带权的图（例如表示从一个顶点
到另一个顶点的距离或花费的代价等）。
1
2
3
5
7
8
74
1 0
7
9
7
7
7
1 2
3
1 5
1 7
A
B
D
C
E
7 0
3 0
4 5
3 5
8 0
4 0
7 5
图的基本概念
子图：对于图G = （V ，E），G ’ = （V ’ ，E’ ），若存在V ’ 是V 的子
集 ，E’ 是E的子集 ，则称图G ’ 是G 的一个子图
1
2
4
3
V
1
V
3
V
4
V
2
图G
1
2 3
V
1
V
3
V
2
图G ’ ( 图G 的子图）
邻接点：对于无向图G ＝( V , {E}) ，如果边( v1 , v 2 ) E，则称
顶点v1 和v2 互为邻接点( A djacent) ；边( v1 , v2 ) 依附
于( Incident) 顶点v1 和v 2 ，或者说，v1 和v2 相关联。
