《以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历》由会员分享,可在线阅读,更多相关《以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历(13页珍藏版)》请在金锄头文库上搜索。
1、【基本要求】以邻接多重表为存储结构,实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成树的边集头文件;无向图的邻接多重表存储表示;每个顶点所表示的数据 ; ; ;访问标记,;该边依附的个顶点位置,;分别指向依附这个顶点的下一条边;该边信息指针;指向第一条依附该顶点的边; ;,;无向图的当前顶点和边数;队列的定义;,;,;寻找指定数据寻找输入的数据在图中的位置,若不存在则返回(,);(;)(, );构造无向图采用邻接多重表存储表示,构造无向图()请输入图的顶点数:;输入图当前的顶点数请输入图的弧数:;输入图当前的边数请输入每个顶点所对应的值
2、:;(;) ;输入顶点值 ;初始化指针,;每条弧所关联的两个结点(;)请输入第弧的始点和终点:;(,) ;(,) ;确定和在图中的位置()() ) ;对弧结点进行赋值() ;() ;() ;() ;() ; ;返回的值(,)()() ; ;返回的第一个邻接点的序号,若没有则返回(,);(,) ;();( )有邻接结点( ) ; ;返回的(相对于)的下一个邻接结点的序号,若是的最后一个邻接结点,则返回(,),;(,) ;(,) ;(); ;()(!);(!);();();();();();();队列的操作 ;访问标志数组() () ;(,);( ) ;该顶点已经被访问 ;()?:;(! )(,)
3、 ;?:;深度优先搜索(,()() ),;(;);请输入你要开始进行查找的位置:;按广深度优先搜索的结果是:;(;)()(;)(! )(,) ;内层(! )(,) ;外层;队列的初始化()() () ()() ) ;(!() )() ;() ;判断队列是否为空,为空则返回,否则返回()();向队列中插入元素(,)()() ) ;(!)() ;() ;() ;若队列不为空,则删除对头元素,并返回;否则返回(,);() () );() ;() ;() )() () ;() ; ;访问标志数组() () ;函数变量(,()() )对图做深度优先遍历使用全局变量,使不必设函数指针参数(;);访问标志数组初始化(;)(! )(,) ;对尚未访问的顶点调用(,)从第个顶点出发递归地深度优先遍历图;() ;访问第个顶点(,) ;(,)(! )(,) ;广度优先搜索广度优先非递归遍历图(,()() ),;,