首页 考试资料幻灯片工程技术公务员考试小学教学中学教学大学教学外语资料
数据结构实验书


Step Step Step Step

7: 8: 9: 10:

发现顶点 8 的邻接点还有 6、7 未访问,因此访问顶点 6,并将 6 入栈。 顶点 6 的邻接点为 3、8,而 8 已访问了,因此访问顶点 3,并将 3 入栈。 而顶点 3 的邻接点为 1、6、7;而 1 和 6 已访问,因此访问顶点 7,并将 7 入栈。 顶点 7 的邻接点为 3、8 已访问过了,因此从栈中取出,而栈中所有顶点已全部访问完,故遍

历结束。最后得到的遍历序列是:1,2,4,8,5,6,3,7

2. 广度优先搜索(BFS) (1) 基本思想:假设从图中某个顶点 v 出发,在访问了 v 之后依次访问 v 的未被访问的邻接点,然后分 别从这些邻接点出发一次访问它们的邻接点,并使“先访问的顶点的邻接点”先于“后访问的顶点的邻接 点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中还有顶点未被访问到,则 另选图中一个未曾被访问的顶点做始点,重复上述过程,直至图中所有顶点都被访问到为止。 (2) 遍历过程示例分析: 以图 G2 为例,了解对图的广度优先法的描述,且采用队列来描述。其搜索过程中队列的变化见图 7-4。 Step Step Step 1: 2: 3: 若从顶点 4 开始广度优先法搜索,将 4 入队列。 访问 4,并将 4 出队列,且将顶点 4 的邻接点 2 和 8 入队列。 访问顶点 2,将 2 的邻接点 1、4、5 入队列,而 4 已访问过,不必入队列,因此只有 4、5 进入

队列,且将 2 出队列。 Step Step Step Step Step Step 4: 5: 6: 访问顶点 8,将顶点 8 的邻接点 5、6、7 入队列,并将顶点 8 出队列。 访问顶点 1,将顶点 1 的邻接点 3 入队列,并将顶点 1 出队列。 访问顶点 5,没有顶点入队列。将顶点 5 出队列。

7:访问顶点 6,将顶点 7 入队列。并将顶点 6 出队列。 8:访问顶点 7,没有顶点入队列。并将顶点 7 出队列。 9:访问顶点 3,没有顶点入队列。并将顶点 3 出队列。此时队列为空,整个遍历结束。

所以最后的遍历的顺序为: 4,2,8,1,5,6,7,3。 因为图的深度优先搜索和广度优先搜索时,由于一个结点的邻接点有多个,并可从中选择一个进行深度/ 广度搜索,因此最后的搜索顺序不是唯一的。但可通过约定,来得到唯一的搜索序列。 根据深度优先搜索法的过程,其实质是利用栈 来进行的。所以可充分利用栈的递归性质来进行。 我们以深度优先搜索为例来写源程序。 变化 【C 源程序】 #include <stdlib.h> 9 /*定义顶点数*/ 图 7-4 广度搜索图 G2 队列的

#define vertexnum struct { node

/*图顶点结构:用邻接表存储*/

int vertex; /*邻接顶点数据*/ struct }; typedef struct node *graph; /*定义图结构*/ struct node head[vertexnum]; node *next; /*下一个邻接顶点*/

int visited[vertexnum]; /*用于标记结点是否已访问*/ void {graph dfs(int vertex) /*深度优先搜索法*/ pointer;

visited[vertex]=1; /*标记此结点已访问*/ printf("[%d]==>",vertex); pointer=head[vertex].next; while (pointer!=NULL) {if (visited[pointer->vertex]==0) dfs(pointer->vertex); /*递归调用*/ pointer=pointer->next; /*下一个邻接点*/ } } void { create_graph(int graph pointer,new; node));/*配置内存*/ vertex1,int vertex2)/*建立邻接顶点到邻接表内*/

new=(graph)malloc(sizeof(struct if (new!=NULL)/*成功*/

{ new->vertex=vertex2; /*邻近接点*/ new->next=NULL; pointer=&(head[vertex1]); /*设为顶点数组之首结点*/ while (pointer->next!=NULL) pointer=pointer->next; /*下一个结点*/ pointer->next=new; /*串在链尾*/ } } void print_graph(struct node *head) /*输入出邻接表数据*/

{ graph pointer; pointer=head->next; /*指针指向首结点 while (pointer!=NULL) { printf("[%d]",pointer->vertex); pointer=pointer->next; /*往下结点 } printf("n"); } void {int int node[20][2]={{1,2},{2,1},{1,3},{3,1},{2,4},{4,2},{2,5},{5,2},{3,6},{6,3},{3,7}, ,{8,4},{5,8},{8,5},{6,8},{8,6},{7,8},{8,7}}; /*图 G3 的所有结点的邻接点的邻接表*/ for (i=0;i<vertexnum;i++) { head[i].vertex=i; {7,3},{4,8} main() /*主程序 i;

head[i].next=NULL; } for (i=0;i<vertexnum;i++) visited[i]=0; for (i=0;i<20;i++) create_graph(node[i][0],node[i][1]);/*建立邻接表*/ printf("graphn"); for (i=1;i<vertexnum;i++) {printf("vertex[%d]: ",i); /*配置所有结点均未访问*/

print_graph(&head[I]); } printf("the depth of the graph is:n");

printf(" dfs(1); printf(" } 【实验题】

[开始]==> "); /*首先从结点 1 开始 [结束] ");

1. 试设计一个广度优先搜索法来遍历一个图(以图 G2 为例)程序。 2. 将邻接表换成邻接矩阵来存储图,改写上面的深度优先搜索算法。

第三节 图的最小生成树实验

【问题描述】 最小生成树问题:在网上,选择一棵生成树,使树上各边的代价之和为最小。解决该问题有两个经典的算 法:普里姆算法和克鲁斯卡尔算法。 【算法描述】 1. 普里姆(Prim)算法:它的思想是每次加入一个邻接边来建立最小生成树,直到 N-1 条边为止。设 G= (V,E)是连通网,TE 是 G 上最小生成树中边的集合,初值为空,U 为顶点集合,初值 U=(U0)重复执行: 在所有 u U,v V-U 的边(u,v) E 中找一条代价最小的边(U0, V0)并入 TE,同时,V0 并入 U。

直到 U=V,此时最小生成树=(V,TE)。该算法的时间复杂度为 O(n2)。 图 7-5 中的 G3 最后由普里姆算法求得的最小生成树见图 7-6。

图 7-6

G3 的最小生成树

2. 克鲁斯卡尔(Kruskal):设G=(V,E)是连通网。令最小生成树T的初始状态为:T=(V,φ ) 重复在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T的边集 中,否则舍去此边而选择下一条代价最小的边,直至T中所有顶点都在同一连通分量上为止。该算法的时 间复杂度为 O(eloge)。 以图 G3 进行描述:首先,将图形中的所有边按递增排列如下:

123456789101112131415161718192021222324252627282930

 


 

  【Top

最新搜索

 


 

热点推荐