《数据结构图的遍历C++实现》由会员分享，可在线阅读，更多相关《数据结构图的遍历C++实现（5页珍藏版）》请在金锄头文库上搜索。
1、实 验 报 告一、实验目的 1.掌握图的基本概念和邻接表的储存结构。 2.掌握图的邻接表存储结构的算法实现。 3.掌握图的邻接表存储结构上的遍历算法的实现。 二、实验内容 对给定的图，用邻接表实现该图的广义优先搜索遍历。三、实验与算法分析 先定义图的邻接表数据类型， 建立该图的邻接表， 然后在用子函数写出广度 优先搜索遍历的遍历算法， 最后用主函数调用它。 实现广度优先搜索遍历可以利 用队列的原理。 用到两个类， 一个用于定义链表类型， 每个结点含有一个数据域和一个指针 域。另一个类用于定义邻接表的表头类型并在其中实现建立邻接表，用邻接表从 顶点 i 出发进行广度优先搜索遍历。2、队列：用于实
2、现广度优先搜索遍历。 广度优先遍历的思想：广度优先遍历类似于树的按层次遍历。设图G 的初 态是所有顶点均未访问，在G 中任选一顶点作为初始点，则广度优先搜索的基 本思想是： （1） 首先访问顶点 i， 并将其访问标志置为已被访问， 即 visitedi=true ； （2）接着依次访问与顶点i 有边相连的所有顶点W1，W2,.Wt;(3)然后再按 顺序访问与W1，W2,.Wt 有边相连又未曾访问过的顶点； （4）依此类推， 直到图中所有顶点都被访问完为止。 四、可执行程序及注释 #include const int n=8; /表示图中的最大顶点数 const int e=15; /图中的最大
3、边数 typedef int elemtype; bool visitedn+1; /标志数组用于记载某个顶点是否被访问过 class link /定义链表类型 public: elemtype data; link *next; ; class GRAPH /定义邻接表的表头类型 public: link an+1; void creatlink() /建立图的邻接表 int i,j,k; link *s; for(i=1;iij; /输入一条边（ i，j） coutdata=j; s-next=ai.next; /头插法建立链表 ai.next=s; /头插法建立链表 s=new link
4、; s-data=i; s-next=aj.next; /头插法建立链表 aj.next=s; /头插法建立链表 void dfs1(int i) /用邻接表从顶点 i 出发进行深度优先搜索遍 历 link *p; coutdata) dfs1(p-data); p=p-next; void bfs1(int i) /用邻接表从顶点 i 出发进行广度优先搜索遍 历 int qn+1; /定义队列 int f,r; link *p; f=r=0; coutdata) coutdata.datadata=true; r+; qr=p-data; /进队 p=p-next; ; void main() link *p; int yn=1; GRAPH G; G.creatlink(); /建立邻接表 while(yn=1) for(int i=1;i“; while(p-next!=NULL) coutdata“; p=p-next; coutdatai; couti; coutyn; 五、实验小结
