潍坊市论坛

注册

 

发新话题 回复该主题

数据结构复习图 [复制链接]

1#

一、基本概念

定义:图:{{顶点集},{边(弧)集}}

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>

分享 转发
TOP
发新话题 回复该主题