文档介绍：算法与数据结构
阙夏制作
§5 图
图是另一种非线性结构,它比树更复杂、更一般化,因此可以把树看成是简单的图。图的应用范围极广,近年来已经渗入到各个领域,如语言学、逻辑学、数学、物理、化学、计算机科学和各种工程学领域。
§ 图的定义和基本术语
一、图的定义
图:由顶点集V和连接顶点的边(弧)集E所组成的结构,记作G=(V,E);
1
2
3
4
3
1
2
4
V={1,2,3,4}
E={<1,2>,<1,3>,<2,4>,<3,4>,<4,1>}
V={1,2,3,4}
E={(1,2),(1,3),(2,4),(1,4),(3,4)}
二、基本概念
带权的有向图称为网络;
6
2
5
1
2
3
4
4
3
一、基本概念
若无向图G中任意两点间都有一条边,则称此图G为无向完全图。
1
2
3
…
n
即n个顶点的无向完全图有n(n-1)/2条边;
n-1
n-2
n-3
0
…
(n-1)+(n-2)+…+0=n(n-1)/2
1
2
3
4
一、基本概念
若有向图G中任意一个顶点到其余各点间均有一条弧,则称G为有向完全图。
即n个顶点的有向完全图有n(n-1)条弧;
1
2
3
…
n
n-1
n-1
n-1
n-1
…
1
2
3
4
一、基本概念
若一个图G1=(V1,E1)是从G中选取部分顶点和部分边(或弧)组成,即V1⊆V,E1⊆E,则称G1是G的子图。
相邻:若(i,j)∈E,——i,j相邻;
若<i,j>∈E——i,j相邻;
i邻接到j;j邻接自i。
1
2
3
4
5
6
一、基本概念
度——邻接点的数目。
有向图:入度,出度。
有向图中某结点的度=入度+出度。
1
2
3
4
1
2
3
4
一、基本概念
路径:顶点序列
(1)若中间无重复——简单路径
(2)若首尾相同——回路
(3)若首尾相同且中间无重复 ——简单回路
1
2
3
4
1
2
3
4