数据结构与算法分析(第二版)review11.ppt

第6章 图 第11章 图 11.1 图的基本概念 11.2 图的存储结构 11.3 图的遍历 11.4 最短距离问题 11. 图的基本概念 11. 图的基本概念 11.2 图的存储结构 11.2.1 关联矩阵 11.2.2 求值矩阵 11.2.3 邻接表 11.2.4 邻接多重表 11.2 图的存储结构 11.2.1 关联矩阵 长度为n的一维数组D(1：n)存放图中各数据结点的信息， n阶的二维数组R(1：n，1：n)存放图中各结点的关联信 息。其中二维数组R称为图的关联矩阵。在关联矩阵R中，每一个元素R(i，j) (1≤i≤n，1≤j≤n)的定义为 11.2 图的存储结构 11.2 图的存储结构 11.2 图的存储结构 11.2 图的存储结构 11.2 图的存储结构 11.2.2 求值矩阵 11.2 图的存储结构 11.2 图的存储结构 11.2.3 邻接表 （“顺序－索引－链接”存储结构） 11.2 图的存储结构 11.2 图的存储结构 11.2 图的存储结构 struct node /*单链表中结点结构*/ { int num；/*图中结点编号*/ ET1 val；/*求值函数*/ struct node *next；/*指针域*/ }； struct gpnode /*顺序存储空间中结点结构*/ { ET data； /*结点值*/ struct node *link；/*指针域*/ }； 11.2 图的存储结构 图邻接表的构造 输入：图的结点数n；依次存放图中结点值的数组D(1：n)。 输出：邻接表顺序存储空间的首地址。 PROCEDURE CREATGP(D，n) 定义DATA(1：n)，LINK(1：n) [建立顺序存储空间] FOR k＝0 TO n DO { DATA(k)＝D[k]； LINK(k)＝0 INPUT m，v /*输入图中第k个结点的后件信息*/ WHILE (m＞＝0) DO /*输入后件信息未结束*/ { NEW(p) /*分配单链表结点*/ NUM(p)＝m； VAL(p)＝v；NEXT(p)＝LINK(k)；LINK(k)＝p INPUT m，v /*继续输入后件信息*/ } } RETURN 11.2 图的存储结构 2，63（回车）3，95（回车）4，84（回车）－1，－1（回车）（结点A的后件） 1，63（回车）3，49（回车）4，44（回车）5，37（回车）－1，－1（回车） （结点B的后件） 1，95（回车）2，49（回车）－1，－1（回车）（结点C的后件） 1，84（回车）2，44（回车）5，35（回车）－1，－1（回车）（结点D的后件） 2，37（回车）4，35（回车）－1，－1（回车）（结点E的后件） 11.2 图的存储结构 #include stdio.h #include stdlib.h struct node /*单链表中结点结构*/ { int num； /*图中结点编号*/ int val； /*求值函数*/ struct node *next； /*指针域*/ }； struct gpnode /*顺序存储空间中结点结构*/ { char data； /*结点值*/ struct node *link； /*指针域*/ }； 11.2 图的存储结构 struct gpnode *creatgp(d，n)/*该函数返回顺序存储空间的首地址*/ int n； char d[]； { struct gpnode *head； struct node *p； int k，m，v； head＝(struct gpnode *)malloc(n*sizeof(struct gpnode))； for (k＝0；k＜n；k＋＋) /*依次对图中的每一个结点建立链接所有后件的单链表*/ { (head＋k)－data＝d[k]； /*置顺序存储空间的结点值*/ (head＋k)－link＝NULL；/*置顺序存储空间结点指针域为空*/ printf(input