教察 第七章图 程序设计—数据结构 图的遍历算法及其应用 q=p; /*q指示当前生成树的根/ EnQueue(Q,v,p); while(!QueueEmpty(Q)){ 序出队，访问出队元素的邻接点*/ DeQueue(Q,u,q); first=TRUE; for w=FirstAdjVex(G,u);ww=NextAdjVex(G,u,w)) if(!visited[w]){ 体访问顶点u的尚未访问的邻接点并入队*/ visited[w]=TRUE; p=(CSTree)malloc(sizeof(CSNode));/:分配孩子结点*/ *p={GetVex(G,w),NULL,NULL); if first){ :w是V的第一个未访问的邻接点*/ q->firstchild p;first FALSE; :是根的第一个孩子*/ else{ q->nextsbling=p; :是上一邻接点的右兄弟结点*/ } q=p; :修改上一孩子结点的指针* EnQueue(Q,w,p); } 7.5.2最小生成树 1、概念 ·应用的图的类型：连通网（无向带权） ·最小生成树：树上各边权值之和最小的生成树 ·MST性质 2、普里姆算法 己知网N=(V,E}), 普里姆算法的求解过程是最小生成树不断壮大的过程 ·初始：最小生成树仅包括一个顶点U={u0},无边TE={}: ·循环处理：从V-U中选择一个顶点vo, 选择条件：所有u∈U,v∈V-U的边(u,v)∈E中，找一条权值最小的边(u',vo) vo加入到U,(u',vo)加入到TE 循环结束条件：V=U 3、克鲁斯卡尔算法 克鲁斯卡尔算法的求解过程是连通分量不断合并的过程 ·初始：n个顶点组成n个连通分量 ·循环处理：在两连通分量中选择一条边(u',v) 选择条件：权值最小，连接两连通分量 循环结束条件：一个连通分量 7.6有向无环图及其应用 1、拓扑排序 AOV-网 文档编号 完成时间 完成人张昱 修改时间20026-6 第12页程序设计——数据结构 第七章 图 图的遍历算法及其应用 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 12 页 q = p; /* q 指示当前生成树的根 */ EnQueue(Q, v, p); while( !QueueEmpty(Q) ){ /* 出队，访问出队元素的邻接点 */ DeQueue(Q,u, q); first = TRUE; for ( w = FirstAdjVex( G, u) ; w ; w = NextAdjVex(G, u, w)) if ( !visited[w] ){ /* 访问顶点 u 的尚未访问的邻接点并入队 */ visited[w] = TRUE; p = ( CSTree ) malloc(sizeof(CSNode)); /* 分配孩子结点 */ *p = {GetVex(G, w), NULL, NULL}; if ( first ){ /* w 是 v 的第一个未访问的邻接点 */ q->firstchild = p; first = FALSE; /*是根的第一个孩子 */ } else { q->nextsbling = p; /* 是上一邻接点的右兄弟结点 */ } q = p; /* 修改上一孩子结点的指针 */ EnQueue(Q, w, p); } } } } 7.5.2 最小生成树 1、概念 ·应用的图的类型：连通网（无向带权） ·最小生成树：树上各边权值之和最小的生成树 ·MST 性质 2、普里姆算法 已知网 N = (V, {E}), 普里姆算法的求解过程是最小生成树不断壮大的过程 ·初始：最小生成树仅包括一个顶点 U={u0}，无边 TE = {}； ·循环处理：从 V-U 中选择一个顶点 v0, 选择条件：所有 u∈U, v∈V-U 的边(u , v)∈E 中，找一条权值最小的边( u’, v0) v0 加入到 U，( u’, v0)加入到 TE 循环结束条件：V = U 3、克鲁斯卡尔算法 克鲁斯卡尔算法的求解过程是连通分量不断合并的过程 ·初始：n 个顶点组成 n 个连通分量 ·循环处理：在两连通分量中选择一条边( u’, v’) 选择条件：权值最小，连接两连通分量 循环结束条件：一个连通分量 7.6 有向无环图及其应用 1、拓扑排序 AOV-网