2023年山东大学数据结构实验报告七.docx

《2023年山东大学数据结构实验报告七.docx》由会员分享，可在线阅读，更多相关《2023年山东大学数据结构实验报告七.docx（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构实验报告实验七实验题目：图的算法学号：日期:2023.1 1 .26 班级：计机14. 1姓名：刘方铮Ema i 1:实验目的：1、掌握图的基本概念，描述方法;遍历方法。任务规定：1、创建图类。二叉树的存储结构使用邻接矩阵或链表。2、提供操作:遍历、BFS、DFS3、对建立好的图，执行上述各操作。4、输出生成树。5、输出最小生成树。软件环境：Win7操作系统开发工具：v i s ua 1 C+ 6.0实验代码;i f nde f GRAPH_H#define G RAPH_Hincl u de# incl u de u s i ng nam e space std;templa t e

2、 class edge(p u bli c ：e dg e ( i n t i,int j, i nt w)ver t exl = i ; v erte x 2=j; we i g h t=w; )edge(int i,i n t j)vert e xl =i; vertex2=j； we i ght= 1 ;)T v e r tex 1;T verte x 2；T wei g h t ;；tempi a te c 1 ass g rap hp u blic：gnip h () )gra p h() v i r t u a 1 i n t numberO f V ertices()=0;/返回

3、图顶点数virtu a 1 i n t numb e r0 f Ed g es()=()；/返回图边数vi r tual bool ex i stsEd g e(in t ,int)= 0 ;/ / 假如边(i ,j)存在，返回t ru e，否则返回fal s ev i r tual vo i d i nser t E d ge (edge t h e E dge)= 0 ;/插入边v i r tu a I void era s eEdge(int,int)=O;/删除边r t u al i nt de g ree(int) =0;返回顶点 i 的度，只用于无向图vi r tual i n t

4、 inDegr e e(int)=0；返回顶点 i 的入度virt u al i n t ou t De g r e e (i n t ) =0;返回顶点 i 的出度vir t ual bo o 1 directed() = 0 ;/若为有向图返回truevir t ual bool weigh ted ()=0;/ / 若为加权图返回trueprote c t e d:pr i vate：;tern p 1 at e c 1 as s adjac e nc y Wgra p h : p ub 1 ic gra p h / / 加权图的邻接矩 阵结构(pro t e ct e d :i nt

5、n;顶点个数i n t e；/边的个数T/邻接数组T n oEdge;/表达不存的边T m a xW e igh t ; / /最大权pub 1 i c:adj ace ncyW gra p h(i n t n umbe r O f V e r t ices =0 , T t h eNo Ed g e = 0 )i f ( n umbcrOfV e rtice s =0 ; return； n = n umb e rO f V ertic e s ;e = 0;n oE d ge = t heNoEd g e;ma x W e i ghl= 0 ;make2dArr y (a,n+l, n+1

6、);)-adj a c enc y Wg r aph()(fo r (int i =0； i=n;i+)d e 1 e te _ a i;d e lele a ;a =NU L L;)int num b erOfV e r t i ce s () return n ;i n t n umbe r OfE d ges () r e t urn e;bool w e i ght e d ( ) re t u r n t r ue； )bool directed() retu r n f a 1 se;b o ol exi s t s Edge(int i jnt j)/返回值为真当且仅当(i,j)

7、是图的一条边if (il II J n |jn | |ai j =noEdge) ret urn false;elseretu r n t rue;)vo i d ins Ed g e(i n t i, i n t j,int w)插入边if(wm a xWeigh t ) maxW e ight=w;ed g e ed(i, j ,w)；i n sert E dge(ed);)vo i d eras e E dg e ( i nt i,int j) /删除边(i,j)i f (i=l & j=l & i= n & j=n & ai jj!=no E d ge)aliJUJ = noEdge;

8、a j i= no Edge；e；)bool c hec k Ve r t e x(in t th e Ve r tex)拟定为有效顶点i f (theVertexn) ret u rn fa 1 se;el s e retu r n true;)i n t d e g ree (int th e Vert e x) / /返回顶点 theVerte x 的度i f (! checkVertex( t he V er t ex) )co u t no vertex t h eVertexe n dl；return -1;)i nt sum=O;fo r (int i= l;i=n;i+)i f

9、 (a t he V e rtexil!=noEd g e ) sum+;retur n sum;1int i nDegre e (int the Vertex)(cou t ” inD e grc e () und e fi n cd;return 0;)int o utD e g r e e (in t the Ver t ex)(cout outD e gree() un d e fi n e d;r eturn 0;)vo i d ou t pu t ()输出邻接矩阵for(int i =l;i=n;i+ ) f or(int j =l;j=n;j+) couta i j cou te

10、nd 1 ;)v oi d bfs(int v)(i n t r e achn+ 1 ；f o r(int i =1； i=n;i+) re a chi=0; b f si ( v ,reach,-l);)v o id dfs (i n t v)in t reachn4-1;for (int i=l;i=n； i+) r each i= 0 ; d fsl (v, rea c h,-l);void ma keT r ee(in t v)输出生成树ad j ace n cyWg r aph aw g 0(n,no E d g e);i n t r e a ch n+1;fb r (int i=l

11、;i= n ; i +)reach i =0; queue *q = n e w q ueue();reach v = 1 ;qp u s h (v);w h i 1 e(!q-empt y ()i n t w = q -f r on t ();q - P op()；for( i nt u= 1 ;u p ush(u);r eachf u =-i;)c ou生成树邻接矩阵:uendl;a w g O.out p u t ();c o u tV生成树 b f s ： Men d 1 ;a wgO. b fs(v);cout e ndl;)vo i d makeMinTr e e(int theV

12、 e r t ex)/输出最小生成a d j a cen c y Wg r aph awg 1 ( n , noEdge);fo r (in t i=l； i =n； i+)for (i n t j =1; j =n;j + + )awg 1 .aij=a i j;int * *rea c h ;m a k e2 d Arry (reach,n+l,n+l);f o r (i n t k=l;k = (e-n+1) ;k+) / / 删除多余的边 awgl. f in d Max Weight( m ax We i g h t ,reach,-l); for(int h = 0 ;h=n;h

13、+ +)delet e reachh；delete J reach;reach =NULL；cou t V”最小生成树邻接矩阵：Vvend 1 ;awgl.ou t p ut();cou t最小生成树bfs： ”V Vendl； aw g 1 . b fs( t h eV e r t ex);)vo i d fi n dMa x Weight(int w,int *&r e ach, i nt 1 able) 找到“最大权”，删除边int num= n oEd g c,ro w , col;fo r (in t i=l ;i=n ;i+) 找至 lj “ 最大权”边f or(int j= 1

14、； j =num & reachilj != 1 a b le & a i j =w)num=aij;r o w= i ;col= j ；re a chro w col=lable；reach c olrow = lable;if(deg r ee(row) = 1 I | de g ree(c o 1 )V=1)边不能删 fin d MaxWeight( n u m ,re a c h Jab 1 e);else /删除边 er a seEdge( r o w, c ol)； priva t e:void make2 dArr y(T *&x, int rows, i n t clos) 创

15、建二维数组x = n e wT * r ows ;/创建行指针fo r (i n t i=0;ir o ws ； i + + )/ /为每一行分派空间x i =new T cl o s ；f or(int j =0; jrows;j+) / /初始化邻接矩阵f o r(i n t k= 1 ;kv=clos;k+)xj k = noE d ge;1v oid i n s e r t E d ge (ed g e th e Edge) 插入边，假如该边已存在，则修改权值i n t v 1 =t h e E dg e ,v e r t e x 1;int v 2= t he E d g e .ve

16、 r tex2;i f (v 1 1 | v2 n | | v2 n | v l=v2)c o ut (vl, v 2 ) is n o t a p e rm is s i b Ie e dgeH;r eturn;)i f(a vlv2J = noEd g e)新的边e+ + ；a v ljv 2 = theEdg e .weight;a v2f v 1 = theEdg e . weight;)voi d b fsl(i n t v, int r e a ch,in t labl e )广度先搜索,re a ch i用来标记所有邻接顶点v的可达成顶点 q u e u e * q =n e w

17、 queue();reach v =la b Ie;q -p u sh(v);w h il e (!q empty() int w =q-f r o nt ();q-po P ()；co u tw ;for( i nt u =1; u pu s h (u)；rea c h u 1=1 a bl e ;)void dfsl(int v ,in t re a ch ,int 1 able) reachv =1 a b 1 e;cout v u;int i= 1 ；while(a v i =noEd ge | I rcachi=lable) i+ + ; if( i n+l) v=i;dfs 1 (

18、 v , reach, 1 a b le);)；#endif/GRAPH_H#incl u d e #include usi n g namespace std;i nt main()(a d jace n c yWgraph a wg (8, 0 );a wg. in s Edge( 1,2,5);awg. i nsEdge ( 1 , 3, 4);awg.i n sE d g e ( 1 ,4,10);awg.insEdge (2,5, 30)；aw g . i nsE d ge(3, 5 ,2 5 )；a wg.in s E d ge ( 4 , 6,2);aw g .insE d ge

19、(4,7, 60);awg.in s Edge(5,8, 13);awg. i nsEdg e (6, 8 , 1 4 );aw g.insEdge (7,8,17);c outV V”邻接矩阵:endl;awg.output();cou t b f s： e ndl;aw g .b f s (2)； c o u t e n d 1;c o u t d f s :e n dl;awg. d fs( 3 );coutend 1 ;cout“生成树: vendl；a wg. makeTre e (5);cou tV”最小生成树：H e n dl;awg.makeMi n Tree ；r e tu

20、r n 0; 实验结果: F:SEightbinDebugEight.exe邻接矩阵：054 10 00005000 30 0004000 25 00010 0 0 0 0 2 60 0 0 30 25 0 0 0 0 13 0002000 14 0 0 0 60 0 0 0 17 0 0 0 0 13 14 17 0 bfs：2 1 5 3 4 8 6 7 dfs：31258647 生成树：生成树邻接矩阵：050 10 00005000 30 0000000 25 00010 00000000 30 25 0 0 0 0 130000000 140000000 17 0 0 0 0 13 14 17 0 生成树bfs：52381674最小生成树： 最小生成树邻接矩阵： 054 10 0000500000004000000010 00002000000000 130002000 140000000 17 0 0 0 0 13 14 17 0 最小生成树bfs：58674123Process returned 0 (0x0) execution time : 0.188 s Press any key to continue.