第七章图 程序设计—数据结构 图的遍历算法及其应用 映：必须另外引入存储空间反映顶点之间的邻接关系。 图的存储结构：1)顶点信息：2)边（弧）信息：3)整体信息：顶点数、边（弧）数、图的种 类（有向图、无向图、有向网、无向网） 顶点集的存储：图的应用中，顶点集动态变化的几率十分小 ∴.顶点集可以采用顺序表存储，按预先估计的最大顶点数分配空间 (顺序表和链表：若数据元素集是静态的，采用顺序表要好（随机存取）： 若数据元素集是动态的，则采用链表要好（动态分配与释放）) #define MAX VERTEX NUM 20 体最大顶点数*/ 注意：顺序表与顺序映像之间的区别 关系集的存储：在顶点确定的情况下，边或弧的数目也是不定的：且在实际应用中，可能 会改变图中顶点之间的关系。 邻接矩阵表示法：矩阵中的第ⅰ行第j列的元素反映图中第i个顶点到第 j个顶点是否存在弧：若存在，其附加的信息是什么。 邻接表表示法：将每一顶点的邻接点位置串成一个链，称为邻接表。对于 有向图/网来说，该邻接表反映的是顶点的出边表。 typedef enum(DG,DN,AG,AN)GraphKind; 体{有向图，有向网，无向图，无向网}*/ 2、邻接矩阵表示法（数组表示法） 无向图网：对称矩阵 有向图/网：非必是对称矩阵 图：邻接关系用1/0表示 网：邻接关系需要进一步反映权值，用NFINITY表示无穷大，反映顶点之间无邻接关系 #define INT MAX 32767 体最大整数 * #define INFINITY INT MAX 1)邻接矩阵 typedef struct ArcCell int adj; ∥顶点间关系，无权图：0-不相邻，1-相邻 ∥有权图，权值，NFINITY.不相邻 InfoType *info; ∥该弧相关信息的指针 }ArcCell,AdjMatrix[MAX VERTEX NUM][MAX_VERTEX_NUM]; 2) 图的整体结构 typedef struct{ VertexType vexs[MAX VERTEX NUM]; 体有效的顶点下标从0开始*/ AdiMatrix arcs: *关系集 int vexnum,arcnum; /体顶点数、边弧数 GraphKind kind; /体图的种类 */ MGraph; 3、邻接表表示法 无向图/网：边表，表结点的个数为边数的两倍 有向图网：出边表，表结点的个数为弧数 1)邻接表的表结点 typedef struct ArcNode int adivex;/体弧所指向的顶点的位置/ struct ArcNode *nextarc:体指向下一条弧的指针*/ InfoType *info; }ArcNode; 文档编号 完成时间 完成人张昱 修改时间20026-6 第3页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 3 页 映；必须另外引入存储空间反映顶点之间的邻接关系。 图的存储结构：1）顶点信息；2）边(弧)信息；3）整体信息：顶点数、边(弧)数、图的种 类(有向图、无向图、有向网、无向网) 顶点集的存储：∵图的应用中，顶点集动态变化的几率十分小 ∴顶点集可以采用顺序表存储，按预先估计的最大顶点数分配空间 （顺序表和链表：若数据元素集是静态的，采用顺序表要好(随机存取)； 若数据元素集是动态的，则采用链表要好(动态分配与释放)） #define MAX_VERTEX_NUM 20 /* 最大顶点数 */ 注意：顺序表与顺序映像之间的区别 关系集的存储：在顶点确定的情况下，边或弧的数目也是不定的；且在实际应用中，可能 会改变图中顶点之间的关系。 邻接矩阵表示法：矩阵中的第 i 行第 j 列的元素反映图中第 i 个顶点到第 j 个顶点是否存在弧；若存在，其附加的信息是什么。 邻接表表示法：将每一顶点的邻接点位置串成一个链，称为邻接表。对于 有向图/网来说，该邻接表反映的是顶点的出边表。 typedef enum{DG, DN, AG, AN} GraphKind; /*{有向图，有向网，无向图，无向网}*/ 2、邻接矩阵表示法（数组表示法） 无向图/网：对称矩阵 有向图/网：非必是对称矩阵 图：邻接关系用 1/0 表示 网：邻接关系需要进一步反映权值，用 INFINITY 表示无穷大，反映顶点之间无邻接关系 #define INT_MAX 32767 /* 最大整数 */ #define INFINITY INT_MAX 1) 邻接矩阵 typedef struct ArcCell{ int adj; // 顶点间关系，无权图：0-不相邻，1-相邻 // 有权图，权值，INFINITY-不相邻 InfoType *info; // 该弧相关信息的指针 }ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 2) 图的整体结构 typedef struct { VertexType vexs[MAX_VERTEX_NUM]; /* 有效的顶点下标从 0 开始 */ AdjMatrix arcs; /* 关系集 */ int vexnum, arcnum; /* 顶点数、边/弧数 */ GraphKind kind; /* 图的种类 */ }MGraph; 3、邻接表表示法 无向图/网：边表，表结点的个数为边数的两倍 有向图/网：出边表，表结点的个数为弧数 1) 邻接表的表结点 typedef struct ArcNode{ int adjvex; /* 弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; }ArcNode;