武汉理工大学：《软件技术基础》课程教学资源（PPT课件）第3章 基本数据结构及运算（4/4）

3.6图 ■361图的基本概念 36.2图的存储 36.3图的遍历 36.4图的应用

◼ 3.6.1 图的基本概念 ◼ 3.6.2 图的存储 ◼ 3.6.3 图的遍历 ◼ 3.6.4 图的应用 3.6 图

图的定义、术语 36.1图的基本概念 数据结构B=(D,R) B 图:G=(V,E) 顶点:图中的数据元素 V:表示顶点的非空有限集合。 E:表示两个顶点之间关系的集合

3.6.1 图的基本概念 A B C D 6 3 2 1 数据结构 5 B=（D，R） 图： G=（V，E） 顶点:图中的数据元素 V：表示顶点的非空有限集合。 E：表示两个顶点之间关系的集合。 图的定义、术语

图的定义、术语 有向图 图 无向图 在有向图中,表示从V到V3的一条弧 V1为弧尾或初始点,V3为弧头或终端点。 在无向图中,(W1,V3)表示V1和V3之间的一条边

图 有向图 无向图 在有向图中，表示从V1到V3的一条弧。 V1为弧尾或初始点，V3为弧头或终端点。 在无向图中，(V1，V3)表示V1和V3之间的一条边。 V1 V3 V2 V4 V1 V3 V2 V4 图的定义、术语

图的定义、术语 G=(V,E 顶点集合V={V 弧的集合G={,} 顶点集合V={V1,V2,V3,V4} 边的集合E={(V,V3),(V1,V2) (V1,V4),(V2,V4)} 顶点(V1,V3)与(V3,V1)表示同一条边

V1 V3 V2 V4 V1 V3 V2 V4 顶点集合V={V1， V2 ， V3 ， V4 } 弧的集合G={, , , } 顶点集合V={V1， V2 ， V3 ， V4 } 边的集合E={(V1 , V3 ), (V1 , V2 ), (V1 , V4 ),(V2 , V4 )} G=( V, E ) 顶点(V1 , V3 )与 (V3 , V1 )表示同一条边 图的定义、术语

图的定义、术语 权:与图的边或弧相关的数。 顶点的度:依附于该顶点的边数或弧数。 出度:(仅对有向图)以该顶点为尾的弧数 入度:(仅对有向图)以该顶点为头的弧数。 路径:顶点A与顶点C之间存在一条路径。路径上边或弧的数目 称为该路径的路径长度。 连通图:无向图任意两顶点都有路径(没有孤立顶点) 强连通图:有向图任意两顶点都有路径 网:带权的图称为网 B

A B C D 6 3 2 1 5 权：与图的边或弧相关的数。 顶点的度：依附于该顶点的边数或弧数。 出度：（仅对有向图）以该顶点为尾的弧数。 入度：（仅对有向图）以该顶点为头的弧数。 路径：顶点A与顶点C之间存在一条路径。路径上边或弧的数目 称为该路径的路径长度。 连通图：无向图任意两顶点都有路径（没有孤立顶点） 强连通图：有向图任意两顶点都有路径 网：带权的图称为网 图的定义、术语

图的存储邻接矩阵 3.62图的存储 1.邻接矩阵法 ◆(1)给顶点编号 ◆(2)建立邻接(关系)矩阵 1234 a表示弧 0000 1:表示有弧;0:表示无弧 21011 31001 40110 任意顶点的出度是该行元素之和 任意顶点的入度是该列元素之和 3

图的存储 邻接矩阵 ◼ 3.6.2 图的存储 ◼ 1. 邻接矩阵法 ◆ （1）给顶点编号 ◆ （2）建立邻接（关系）矩阵 2 1 4 3 1 2 3 4 1 2 3 4 0 0 0 0 1 0 1 1 1 0 0 1 0 1 1 0 a i j表示弧 1：表示有弧；0:表示无弧 任意顶点的出度是该行元素之和 任意顶点的入度是该列元素之和

图的存储邻接矩阵 1234 0110 123 1011 1101 0 0 无向图的邻接矩阵是对称的 ◆邻接矩阵的优点 υ增减边的操作简单 ◆邻接矩阵的缺点 υ增减顶点的操作需要搬移大量的元素 c浪费存储空间

图的存储 邻接矩阵 ◆邻接矩阵的优点： 增减边的操作简单 ◆邻接矩阵的缺点： 增减顶点的操作需要搬移大量的元素， 浪费存储空间 2 1 4 3 1 2 3 4 1 2 3 4 0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0 无向图的邻接矩阵是对称的

图的存储邻接矩阵的奥现 图的邻接矩阵实现 typedef struct graph mt elemtype node[MAXNUM;顶点集合 int arcs MAXNUMIMAXNUM;边的邻接矩阵 ]graph 二维数组

图的存储 邻接矩阵的实现 ◼ 图的邻接矩阵实现 typedef struct graph_m{ elemtype node[MAXNUM]; int arcs[MAXNUM][MAXNUM]; }graph_m; 顶点集合 边的邻接矩阵 二维数组

图的存储邻接表 2.邻接表法 /1 data datal 3 data 2=1=1=2 3=3=2=3 邻接表 4 data 元素域头指针 一个邻接表由两种结构组成顶点号 3 data c存放各顶点元素的数组,头结点 下一邻接结点 c各顶点各自的邻接链表,邻接结点 邻接顶点号

图的存储 邻接表 ◼ 2. 邻接表法 ◆一个邻接表由两种结构组成 存放各顶点元素的数组，头结点 各顶点各自的邻接链表，邻接结点 2 1 4 3 1 data 2 3 2 data 3 data 4 data 1 3 4 1 2 4 2 3 顶点号 3 data 元素域 邻接链表 头指针 2 邻接顶点号 下一邻接结点

图的存储(课堂练习) 请写出下面这副图的邻接表 ◆1)给顶点编号 ◆2)建立顶点数组 3 ◆3)建立各顶点的邻接链表 c注意,此图为有向图 1 data 33 5 2 data 3 data 4 data 2=1514 5 data

图的存储（课堂练习） ◼ 请写出下面这副图的邻接表 ◆ 1）给顶点编号 ◆ 2）建立顶点数组 ◆ 3）建立各顶点的邻接链表 注意，此图为有向图 2 1 3 4 1 data 5 2 data 3 data 4 data 5 data 2 3 1 3 5 1 4