图的存储邻接矩阵 3.62图的存储 1.邻接矩阵法 ◆(1)给顶点编号 ◆(2)建立邻接(关系)矩阵 1234 a表示弧<i,j> 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表示弧< 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