教黎 第七章图 程序设计—数据结构 图的遍历算法及其应用 结论：邻接矩阵适于稠密图的存储，邻接表适于稀疏图的存储：邻接表求有向图的顶点的 入度不方便，要遍历各个顶点的邻接表。 7.2.2图的创建 基本过程： 1)输入图的类型，根据类型选择相应的创建算法 2)输入图的顶点数，边/弧数 3)输入并存储顶点信息 4)输入边/弧所关联的顶点对，将边或弧的信息存储到邻接矩阵/邻接表中 图的存储结构不同、图的类型不同，都会影响创建算法的实现细节：但是，图的总体创建 流程是一致的（如上）。 示例：用邻接矩阵表示法构造有向网G Status CreateMDG(MGraph &G){ /*步骤2：输入图的顶点数、边/弧数*/ scanf(&G.vexnum,&G.arcnum,&IncInfo;/体IncInfo为0则各弧不含其它信息*/ /*步骤3：输入并存储顶点信息 */ for (i=0:i<G.vexnum :++scanf (&G.vexsi]): /*步骤4：输入并存储边/弧信息 for(i=0;i<G.vexnum;i++) /体邻接矩阵初始化* for (j=0;j<G.vexnum ;j++) G.arcs[i][j]=(INFINITY,NULL); for(k=0;k <G.arcnum k++){ scanf (&v1,&v2,&w); i=LocateVex(G,v1);j=Locate Vex(G,v2); G.arcs[i][j].adj=w; if(Inclnfo)Input(*G.arcs]j].info);/体*G.arcs[i][].info要求G.arcs[]i[jl.info指向的 空间在调用Input()前分配*/ } 7.3图的遍历 7.3.1深度优先搜索 1、分析 ·类似于树的先序遍历 ·引入访问标志数组visit[0:n-1],区分顶点是否已被访问 ·非连通图，需引入多个深度优先搜索的起始顶点 ·递归算法或基于栈的非递归算法 2、基于ADT Graph的DFS算法 Boolean visited[MAX VERTEX NUM]; void DFSTraverse(Graph G,Status(*Visit )(Graph G,int v)) { for(v=0;v <G.vexnum;++v)visited[v]=FALSE; for(v=0;v<G.vexnum;++v) if(!visited[v]) DFS(G,v,Visit); } 文档编号 完成时间 完成人张昱 修改时间20026-6 第5页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 5 页 结论：邻接矩阵适于稠密图的存储，邻接表适于稀疏图的存储；邻接表求有向图的顶点的 入度不方便，要遍历各个顶点的邻接表。 7.2.2 图的创建 基本过程： 1）输入图的类型，根据类型选择相应的创建算法 2）输入图的顶点数，边/弧数 3）输入并存储顶点信息 4）输入边/弧所关联的顶点对，将边或弧的信息存储到邻接矩阵/邻接表中 图的存储结构不同、图的类型不同，都会影响创建算法的实现细节；但是，图的总体创建 流程是一致的（如上）。 示例：用邻接矩阵表示法构造有向网 G Status CreateMDG(MGraph &G){ /* 步骤 2：输入图的顶点数、边/弧数 */ scanf (&G.vexnum, &G.arcnum, &IncInfo); /* IncInfo 为 0 则各弧不含其它信息 */ /* 步骤 3：输入并存储顶点信息 */ for ( i=0; i<G.vexnum ; i++) scanf ( &G.vexs[i] ); /* 步骤 4：输入并存储边/弧信息 */ for ( i = 0; i < G.vexnum ; i++) /* 邻接矩阵初始化 */ for ( j = 0; j < G.vexnum ; j++) G.arcs[i][j] = {INFINITY, NULL}; for ( k = 0; k < G.arcnum ; k++){ scanf (&v1, &v2, &w); i = LocateVex(G, v1); j = LocateVex(G, v2); G.arcs[i][j].adj = w; if ( IncInfo) Input( *G.arcs[i][j].info); /* *G.arcs[i][j].info要求G.arcs[i][j].info指向的 空间在调用 Input()前分配 */ } } 7.3 图的遍历 7.3.1 深度优先搜索 1、分析 ·类似于树的先序遍历 ·引入访问标志数组 visit[0:n-1]，区分顶点是否已被访问 ·非连通图，需引入多个深度优先搜索的起始顶点 ·递归算法或基于栈的非递归算法 2、基于 ADT Graph 的 DFS 算法 Boolean visited[MAX_VERTEX_NUM]; void DFSTraverse(Graph G, Status ( *Visit ) (Graph G, int v) ) { for ( v = 0; v < G.vexnum; ++v ) visited[v] = FALSE; for ( v = 0; v < G.vexnum; ++v ) if ( !visited[v] ) DFS(G, v, Visit); }