一、基本概念
定义:图:{{顶点集},{边(弧)集}}
1.无向图
2.有向图
3.顶点、边、弧、弧头(终端点)、弧尾(初始点)
4.无向完全图
5.有向完全图
6.稠密图和稀疏图
7.邻接点
8.顶点的度、入度、出度
9.路径、路径的长度
10.回路、简单路径、简单回路
11.子图
12.连通
13.连通图
14.连通分量
15.强连通图、强连通分量
16.生成树
17.生成森林
18.网
二、图的基本操作
结构的建立和销毁
对顶点的访问操作
插入或删除顶点
插入和删除弧
对邻接点的操作
遍历
三、图的两种常见的存储结构
1.图的数组(邻接矩阵)存储表示
对具有n个顶点的图:
用一维数组存储图中顶点的信息;
用一个二维数组存储顶点之间的关系(边或弧)信息。这个二维数组称为邻接矩阵。
邻接矩阵的基本性质:
(1)一个图的邻接矩阵表示是唯一的
(2)对于n个顶点的有向图,需要n*n个存储单元
(3)无向图的邻接矩阵是对称矩阵时,邻接矩阵只需要存矩阵的上三角或下三角部分就可以了,需要n*(n+1)/2
(4)对于无向图,顶点Vi的度是邻接矩阵中第i行(或第i列)元素之和
(5)对于有向图,邻接矩阵的第i行非零元素之和是第i个顶点的出度,第j列元素之和是第i个顶点的入度。
邻接矩阵的相关数据结构/p>
2.图的邻接表存储表示
邻接表是图的一种链式存储结构。在邻接表中,对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点vi的边(对有向图是以顶点vi为尾的弧)
代码实现(以邻接表作为存储结构的图)/p>