数据结构-图的基本概念和存储结构课件.ppt
文本预览下载声明
图的存储表示--邻接矩阵 A B E C D 有向图的邻接矩阵为非对称矩阵 E D C B A E D C B A 图的存储表示--邻接矩阵 #define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //最大顶点个数 Typedef enum{DG,DN,UDG,UDN} GraphKind //有向图,有向网,无向图,无向网 图的存储表示--邻接矩阵 typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型。 // 对无权图,用1或0表示相邻否; // 对带权图,则为权值类型。 InfoType *info; // 该弧相关信息的指针 } ArcCell 图的存储表示--邻接矩阵 typedef struct { // 图的定义 VertexType vexs[MAX_VERTEX_NUM]; // 顶点信息 ArcCell arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 弧的信息 int vexnum, arcnum; // 顶点数,弧数 GraphKind kind; // 图的种类标志 } MGraph; 图的存储表示--邻接表 0 1 2 3 4 5 A B C D E F 1 4 0 4 3 5 2 5 0 1 1 2 5 3 B A C D F E 1)无向图的邻接表 图的存储表示--邻接表 A B E C D 0 1 2 3 4 A B C D E 1 4 3 0 1 2 2 2)有向图的邻接表--每个顶点链接的是以该顶点为弧尾的弧 但是,在有向图的邻接表中不易找到指向该顶点的弧 图的存储表示--邻接表 A B E C D 3)有向图的逆邻接表--每个顶点链接的是指向该顶点的弧 0 1 0 1 2 3 4 A B C D E 3 2 0 3 4 图的存储表示--邻接表 邻接表:图的链式存储结构 对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附顶点Vi的边。 对有向图来说,是指以顶点Vi的为弧尾的弧。 图的存储表示--邻接表 邻接表:图的链式存储结构 adjvex nextarc info 邻接点域 链域 数据域(存放权值等) 表结点: 头结点: data firstarc 数据域 链域,指向链表中第一个结点 弧结点 顶点结点 图的存储表示--邻接表 图的邻接表: 1、容易找到任意顶点的一个邻接点 2、但是要判定任意两个顶点(vi,vj)之间是否有边或者弧相连,需要搜索第i个或者第j个链表,不如邻接矩阵方便。 图的存储表示--有向图的十字链表 A B C A B C 0 1 2 ∧ 0 1 2 1 ∧ 0 2 ∧ ∧ 2 0 ∧ ∧ 图的存储表示--有向图的十字链表 弧尾顶点位置 弧头顶点位置 弧的相关信息 指向下一个有相同弧尾的结点 指向下一个有相同弧头的结点 tailvex headvex hlink tlink info 弧的结点结构 弧的结点结构表示 typedef struct ArcBox { // 弧的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; } ArcBox; 图的存储表示--有向图的十字链表 顶点的结点结构表示 typedef struct VexNode { // 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; } VexNode; 图的存储表示--有向图的十字链表 十字链表 图的存储表示--有向图的十字链表 typedef struct { VexNode xlist[MAX_VERTEX_NUM]; // 顶点结点(表头向量) int vexnum, arcnum; //有向图的当前顶点数和弧数 } OLGraph; * * 图和图的存储结构 图的定义和术语 图的存储表示 小结和作业
显示全部