图的广度优先遍历的算法实现

图的广度优先遍历的算法实现 杜恒 ( ,) 473009河南工业职业技术学院河南 南阳 : ,, 摘 要图的广度优先遍历与树的按层次遍历相似遍历的思路是对图中的每个顶点进行访问且只访问一次要遍历 ,, ,,图首先要把图采用某种存储结构存到内存之中本文采用邻接表存储并在此基础上进行广度优先遍历 : ; ; 关键词图的遍历邻接表广度优先 , 6TP 301:: A: 1671 , 6132( 2012) 12 , 0026 , 04中图分类号文献标志码文章编号 、, ，图是一种非常重要的数据结构图在日常生活十字链表等其中邻接表是一种顺序和重邻接表 ，，，中应用异常广泛在对图进行研究的时候首先要 链式结合的存储方式也是经常使用的一种存储方 ，，，研究顶点中蕴含的信息然后再去研究图的其他相 式先构造一个顶点向量图中顶点之间的关系较 ，，关问题那么在研究图中所有顶点信息的过程就是 为复杂邻接表表示法是在顶点向量中增加一个指 ，,图的遍历也叫图的访问 ，，针域来解决顶点之间的指向关系再构造邻接表，我们借助计算机来研究图的问题首先把图采 把和该顶点有关系的全部顶点用一个单链表链接，用某种存储结构存储起来然后进一步去遍历图中 , ，到其后如果是无向图直接连接所有与这个顶点 ，，顶点的信息按照图的遍历的要求在对图进行遍 , ，有连线的顶点对于有向图只考虑从该顶点出发 ，历时要访问图中的所有顶点而且每个顶点只能访 ( ) ，的弧的弧头指向的那些顶点邻接点然后将其 ,问一次 ,连接到顶点的后面 1 ，，如图 所示是一个有向图按照图中顶点的 ，，序号先构造一个顶点向量然后将每个顶点的所 1图的邻接表存储及算法实现 ，、、图有多种存储方法如数组表示法邻接表多 ，，有邻接点连接到这个顶点的后面构成一个单链表 ,2, , CAPM ，，李嘉李从珠吴富锁在上海股票市场上的实 参考文献J,, ( 1 ) :7 8,，2004，16 证研究北 方 工 业 大 学 学 报 , 82, , J, ,,，,1,李海艳 浅析贝塔系数内蒙古科技与经济 2007( 19) : 13 , 14, CAPM test on Chinese security market ZHU Qi-feng ( Zhengzhou Chenggong Coege of Fnance and Economcs，Zhengzhou 451200，Chna) lliii Abstract: CAPM( capital asset pricing model) is the important pillar of modern financial market，it is always ap- plied on investment decision-making, But CAPM have too many assumptions which may be not suitable for Chi- nese security market，so the conclusion need to be checked out whetheri t is suitable for Chinese security market, Ths artce test an assumpton and the concuson on Chnese securty market，then study the tesandt fnd the iililiiii dfferences between Chnese securty market and the matures ecurty market, iiii Key words: CAPM; yield return; normal distribution;coefficientβ / ，*点和这个新开辟的结点之间插入一个新的结点如除无效字符 ，此反复进行最后形成一个单链表而且最后一个结 scanf( " c" ，,g,i,, verdata) ;% ,点的指域为空 g,i,, firstedg = NULL; } printf( " : 1 or 2 ( 1: ; 2: 请选择图的类型无向图 ) " ) ;有向图 scanf( " d" ，,tag) ; % switch( tag) { case 1: for( i = 1; i ， = e; i + + ) { printf( “请输入无向图中某条边的两个顶 ”) ;点的数据 scanf( " d d" ，,ver1，,ver2) ; % % f( ver1! = 0,,ver2! = 0) { i p = ( Edgnode * ) maoc( szeof( Edgnode) ) ;lli 1 6 图 具有 个顶点的有向图p , a，dj ver = ver2; p , nex， tar = g,ver1,, firstedg; ，建立邻接表要先定义顶点和邻接点的结构体g,ver1,, frstedg = p; i:定义如下 p = ( Edgnode * ) malloc( sizeof( Edgnode) ) ;typedef structE dgnode{ p , a，dj ver = ver1; p , nex， tar = g,ver2,, int adjver; firstedg; g,ver2,, firstedg = p; } }b reak; struct Edgnode * nextar; }Edgnode; typedef structV ernode{ case 2: for ( i = 1; i ， = e; i + + ) { char verdata; prntf( i“请输入有向图中某条弧的两个顶点 struct Edgnode * firstedg; } : ) ;”的数据 Vernode;scanf( " % d% d" ，,ver1，,ver2) ; Edgnode ，Vernode 为邻接点结构体是顶点向if ( ver2! = 0) { ，Vernode 量中单个数据元素的结构用 去构造一个 ( ) ，，顶点向量结构体数组为了方便操作向量中的 0 , 号存储单元留置不用如此向量在定义时必须多 ，MAXSZE + 1，MAXSZE II一个空间即 为图中顶点 ( Edgnode * ) m alloc ( sizeof ( Edg-p = ，1 6 ，MAXSIZE 6， 的个数如图 所示有 个顶点值为 node) ) ;:定义如下 p , a，d ver = ver2; p , nex， tar =jVernode Adjlist,MAXSIZE + 1,; g,ver1,, firstedg; ，: 下面是建立图的邻接表算法创建的思路是 g,ver1,, firstedg = p; } }b reak; ; ，若为有向图则一次输入数据创建一个邻接点若 ，( 是无向图则每次创建两个邻接点依附于同一条 default: printf ( " ! " ) ;图 的 类 型 有 错) ，，边的两个顶点这样处理会减少循环次数从而 break; } } ,节省算法的开销 2 ,采用该算法创建的邻接表的结果如图 所示 ，，这里需要说明的是在创建图的邻接表时输入顶 ，点顺序不同创建出来的邻接表也不一样继而对图 / *void creatgraph( Adjlist g，int n)逆向建立,广度优先遍历得到的序列也不同 /*链表的函数 { int i，e，ver1，ver2; 2广度优先遍历图及算法实现 int tag;/ * ，标志域标志有向图还是无向 2 ，如图 所示建立好邻接表说明已把这个图存 , */图 ，储在内存中了接下来使用广度优先遍历来实现图 Edgnode * p;，，中顶点的访问要注意的是在遍历过程中对每个 prntf( " : " ) ;i请输入弧或边的数目 ，,顶点只能访问一次不能重复访问 scanf( " % d" ，,e) ; ，，2 ，遍历前要先选一个起始顶点如图 所示可 for( i = 1; i ， = n; i + + ) { A ，以选择向量中排在第一号的顶点 开始为了避免 printf( " Please input the graph data char typedef structQ ueue{ Elemtype * front，* rear; } Que; void Init_Queue( Que * head) { head , ，front = ( Elemtype * ) m alloc ( si- zeof( Elemtype) ) ; head , rear ， = ( Elemtype * ) m alloc ( si- zeof( emtype) ) ;El head , f，ront , next ， = NULL; head , rear， = head , f，ron t; } int IsEmpty( Que *ead) {_h 2 图 图的邻接表if ( head , f，ron t = = head , r，ea r) return ，重复访问还需要在遍历过程中定义一个访问标志 ;1 ，, 数组它的作用是标志该顶点是否被访问过定义 ese return 0; }l:如下 void De_Queue( Que * head) { int visited,MAXSIZE + 1,; Eemtype * t; l ，，在数组中若访问过某个顶点将对应的标志 if ( ! s Empty( head) ) { I_ 1，0，数组中的数组元素置为 否则为 在遍历开始 t = head , f，ron t; ，0，时先把标志数组全部置 在访问每一个顶点之 head , f，ront = head , f，ront , n，ex t; ，，前都要扫描一下标志数组看相应的顶点的标志 free( t) ; 1，, ，是否为 并借此作为循环结束的条件另外还有 } else ，一个问题就是遍历完某一个结点后开始遍历该结 prntf( " s" ，! " ) ; }i% 队列为空 ，，点的所有邻接点所有邻接点遍历完后要按刚才 void EnQueue( Que * head，int id) { _ ，遍历的先后顺序遍历邻接点的邻接点这样就要求 ，再设置一个队列存储刚才遍历的顺序这样可以保 head , rear， , ，next = ( Eemtype *)l，证先 遍 历 的 顶 点同层次遍历完后先遍历其邻 malloc ( sizeof( Elemtype) ) ;,接点 head , rear， = head , rear， , n，ex t; : A ， 遍历过程如下顶点 位于邻接表的第一个head , rear， , i，d = d; } iA，A ，B，B;首先输出顶点 然后找 的邻接点是 输出 :遍历函数如下 B CD，、、E的邻接点是 那么采用广度优先遍历输 void Bfs( Adjlist g，int n) {C、D、E; ，C 出 按照队列的先进先出只能先去找 的 Que * Q; int ver; Edgnode * p; ，C D，邻接点的邻接点只有 但是经过访问标志数 for( ver = 1; ver ， = n; ver + + ) ，D ; D ，D 组已访问过于是接着访问 的所有邻接点visited,ver,= 0; F，; E F的所有邻接点只有 于是输出 接着访问 的 for( ver = 1; ver ， = n; ver + + ) ，F，F 所有邻接点只有 而 经过搜索标志数组发现 if( ! v isited,ver,) ，已经被访问过此时作为一个图的一个最大连通子 ，图已经全部访问完但还要确定是否还有顶点没有 ，，visited,ver,= 1;{被访问过因此接着还要去标志数组继续搜索发 printf( " c " ，g,ver,, verdata) ; % 0 ，现标志数组中已经没有标志为 的顶点说明全部 En_Queue( Q，v) ; ，顶点已经被遍历而且保证了每个顶点最多被遍历 while( ! Is_Empty( Q) ) { ,一次 DeQueue( Q，v) _，在写广度优先遍历的算法时首先要设置一个 for( p = Q , n，ex t; p! = NULL; p =，，队列的结构最好放在程序的前面然后进行队列 ，,初始化同时编写入队和出队函数 p , n，ex t)struct Eemtype{ l f( ! v sted,ver,) {iii visited,ver,= 1; printf( " % c " ，g,ver,, verdata) ; nQueue( Q，v) ; E_ ++，Turboc2 VC 然后利用下面的代码在 或 参考文献6, 0 ,平台进行测试即可 ,1,,C M,, : ，《》, 严蔚敏吴伟民数据结构语言版北京清 / */#defne SZ 6 iMAXIE*定义顶点的个数，1997,华大学出版社 main( ) { ,C M,, : 《》,姚菁数据结构语言版北京机械工业出 ,2, Adjlist g,MAXSIZE+ 1,;2003, ，版社int n = MAXSIZE; , ( C ) ,M,, : 徐翠霞数据结构案例教程语言版北京 ,3,creatgraph( g，n) ; 2009,，北京大学出版社 Bfs( g，n) ; } , C J,，,,杜恒龚茜茹图的深度优先遍历的 语言实现 4,,，2004( 2) : 26 , 27,九江职业技术学院学报 结束语 , J,, ,俞惠芳图的遍历的分析与算法青海师范 32005( 4) : 35 , 36, ， 大学学报,5, ，图的广度优先遍历类似于树的按层次遍历以 , 上内容给出连通图的算法实现如果对于非连通 The algorithm realization of breadth-first-search of the graph DU Heng ( Henan Poytechnc nsttute，Nanyang 473009，Chna) liIii Abstract: According to graphs breadth-first-search similar to thet rees level traverse，train of thoughtof visited’’ is a visit to every elment of the graph, Moreeve，rto traverse thegr aph，first to chart a storage structures ave to memory, In this paper，we can save the graph in the way of adjacency list，the operate theb readth-first-search,K ey words: traversing graph; adjacency list; breadth-first