教育部—微软精品课程建设项目 遍历 DFSTraverse(G, v, visito) /顶点V起深度优先遍历图G,并对每 个顶点调用函数Ⅴisit一次且仅一次。 BFSTraverse(G, v, visito; /顶点√起广度优先遍历图G,并对每 个页点调用函数Vst-次且仅一次。 南京航空航天大学数据结构课题组版权所有
遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次
教育部—微软精品课程建设项目 72图的存储表示 图的数组(邻接矩阵)存储表示 图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示 南京航空航天大学数据结构课题组版权所有
7.2 图的存储表示 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示
教育部—微软精品课程建设项目 图的数组(郐接矩阵)存储表示 定义:矩阵的元素为 O (1DEVR A 1(13)∈VR Q0100101 10 00 001 010 01 01 1000 01110 南京航空航天大学数据结构题组版权所有
Aij={ 0 (i,j)VR 1 (i,j)VR 一、图的数组(邻接矩阵)存储表示 B A C D F E 定义:矩阵的元素为 0 1 0 0 1 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 0 1 1 1 0 0
教育部—微软精品课程建设项目 有向图的邻接矩阵 为非对称矩阵 01001 00100 00010 1100 B 0010 00 南京航空航天大学数据结构课题组版权所有
有向图的邻接矩阵 为非对称矩阵 A B E C D 0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0
教育部—微软精品课程建设项目 typedef struct ArcCel∥/弧的定义 VRType adj;∥ VRType是顶点关系类型。 ∥对无权图,用1或0表示相邻否; ∥对带权图,则为权值类型。 nfo Type*info;∥该弧相关信息的指针 3 ArcCell AdjMatriX MAX VertEX NUM MAⅹ VERTEX NU1 南京航空航天大学数据结构课题组版权所有
typedef struct ArcCell { // 弧的定义 VRType adj; // VRType是顶点关系类型。 // 对无权图，用1或0表示相邻否； // 对带权图，则为权值类型。 InfoType *info; // 该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];