图的存储邻接表的奥现 ■邻接表的定义 顶点号元素域与头结点 ◆头结点的定义 相邻的顶点 typedef struct headnodet int node index elemtype data; struct adj node next adj; 3 headnode 下一个与头结点相邻的 ◆邻接结点的定义顶点号 顶点的邻接结点 typedef struct adj_nodet int node index struct adj node *next adj; fadj_ node
图的存储 邻接表的实现 ◼ 邻接表的定义 ◆头结点的定义 ◆邻接结点的定义 顶点号 元素域 与头结点 相邻的顶点 typedef struct headnode{ int node_index; elemtype data; struct adj_node * next_adj; } headnode; 顶点号 下一个与头结点相邻的 顶点的邻接结点 typedef struct adj_node{ int node_index; struct adj_node *next_adj; }adj_node;
图的存储邻接表 ◆图邻接表的定义 typedef struct graph_ t headnode node list[MAXNUMI int node num. Igraph_I; data data 4∧ 3 datal 2=1=1=2 3=3=2=3 4 data
图的存储 邻接表 ◆图邻接表的定义 typedef struct graph_l{ headnode node_list[MAXNUM]; int node_num; }graph_l; 1 data 2 3 2 data 3 data 4 data 1 3 4 1 2 4 2 3
图的存储邻接表 data 2 3∧ data 3 3 dats 4 4 data 2 3∧ 1 data 3∧ data 3 4∧ 3 datal 4∧ 4 data 「注意:有向图与无向图的区别
图的存储 邻接表 2 1 4 3 1 data 2 3 2 data 3 data 4 data 1 3 4 1 2 4 2 3 2 1 4 3 1 data 2 data 3 data 4 data 1 3 4 1 3 4 注意：有向图与无向图的区别
图的存储 图的邻接表存储法的特点 ◆优点 c节省存储空间 c边的插入和删除操作比较简便 ◆缺点 c结构复杂 具有两种不同的基本组成单元
图的存储 ◼ 图的邻接表存储法的特点 ◆优点 节省存储空间 边的插入和删除操作比较简便 ◆缺点 结构复杂 ❖具有两种不同的基本组成单元
图的存储 3.边带权值的图的存储 ◆1)在邻接矩阵中的实现 5 3 0235 a[4[4] 2010 3101 3 5010 a[ij]:记录边的权值;为0表示无边
图的存储 ◼ 3. 边带权值的图的存储 ◆ 1）在邻接矩阵中的实现 0 2 3 5 2 0 1 0 3 1 0 1 5 0 1 0 a[4][4] = a[ i ][ j ]：记录边的权值；为0表示无边 1 2 4 3 2 3 5 1 1