2023年山东大学数据结构实验报告七.docx
数据结构实验报告实验七实验题目：图的算法学号：日期: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<qu e u e ># incl u de <i o s t r e a m> u s i ng nam e space std;templa t e <class T>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 T>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;/返回图顶点数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> 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 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 <cl a s s T >c 1 as s adjac e nc y Wgra p h : p ub 1 ic gra p h <T> / / 加权图的邻接矩 阵结构(pro t e ct e d :i nt 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 )th r o w " n um b er of vertices mu s t be >=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);)-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)是图的一条边if (i<l II J <1 II i>n |j>n | |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(w>m a xWeigh t ) maxW e ight=w;ed g e <int> 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;a j i= no Edge；e；)bool c hec k Ve r t e x(in t th e Ve r tex)拟定为有效顶点i f (theVertex< 1 | t h eVcrt e x>n) 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 eVertex«e n dl；return -1;)i nt sum=O;fo r (int i= l;i<=n;i+)i f (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+) cout«a i j «"cou t<<end 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<i n t> aw g 0(n,no E d g e);i n t r e a ch n+1;fb r (int i=l;i<= n ; i +)reach i =0; queue< i n t> *q = n e w q ueue< i n t >();reach v = 1 ;q>p 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<= n ;u+)i f( a w u !=noEdge && rea c hu=0) awgO.in s Edge(w, u , a w E u );q-> p ush(u);r eachf u =-i;)c ou生成树邻接矩阵:u«endl;a w g O.out p u t ();c o u tV<"生成树 b f s ： M«en d 1 ;a wgO. b fs(v);cout<< e ndl;)vo i d makeMinTr e e(int theV e r t ex)/输出最小生成a d j a cen c y Wg r aph<int> 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 + +)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 ； j <=n ;j+)i f (a i 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) 创建二维数组x = n e wT * r ows ;/创建行指针fo r (i n t i=0;i<r o ws ； i + + )/ /为每一行分派空间x i =new T cl o s ；f or(int j =0; j<rows;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<T> 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 r tex2;i f (v 1 <1 | v2<l | v 1 > 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<int> * q =n e w queue< i n t>();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 t«w<< ""for( i nt u =1; u <=n; u +)if(awu !=noEdge&&reach u =0)q->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 ( v , reach, 1 a b le);)；#endif/GRAPH_H#incl u d e <iost r eam>#include <grap h . h> usi n g namespace std;i nt main()(a d jace n c yWgraph<int> 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(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 );cout<<end 1 ;cout<<“生成树:" <vendl；a wg. makeTre e (5);cou tV”最小生成树：H «e n dl;awg.makeMi n Tree ；r e tu 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.
