题目图（有,无向,加权）的构造,与遍历算法的设计与.doc

《题目图（有,无向,加权）的构造,与遍历算法的设计与.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、题目：图（有向，无向，加权）的构造，与遍历算法的设计与实现一、需求分析1.输入的形式和输入的范围本程序采用相邻的两个点对的形式输入2.输出的形式分为两部分，第一部分为邻接链表的形式输出，第二部分为邻接矩阵的形式输出3.可以实现的功能图（有向、无向、加权）的邻接矩阵和邻接链表建立，并完成图的先深遍历和先广遍历，且以以符号话表示。4.测试数据--------欢迎来到图操作系统--------1.请输入一个图2.利用邻接链表建图3.利用邻接矩阵建图4.退出1请输入节点的个数6请输入相邻的节点，并以00结束123400--------欢迎来到图操作系统---

2、-----1.请输入一个图2.利用邻接链表建图3.利用邻接矩阵建图4.退出2你输入的图为:0->1->22->13->44->35->先广遍历的结果是:01->23->45先深遍历的结果是:01->23->45--------欢迎来到图操作系统--------1.请输入一个图2.利用邻接链表建图3.利用邻接矩阵建图4.退出3你输入的图为:000000001000010000000010000100000000先广遍历的结果是:01->23->45先深遍历的结果是:01->23->45--------欢迎来到图操作系统--------1.请输入一个图2

3、.利用邻接链表建图3.利用邻接矩阵建图4.退出4多谢使用，再见一、概要设计本程序用到的抽象数据类型为：inta[128],b[128]vector>d1;vectormark1;vector>d2;vectormark2;本程序用到的自定义函数如下：voidfirst(intk);voidmakegraph(int*a,int*b,intm);voidprint(void);voidDFS(void);voidBFS(void);voidfirst2(intk);voidmake2

4、(int*a,int*b,int*m);voidprint2(void);voidDFS2(void);voidBFS2(void);main函数中先让用户选择，然后根据选择进行分别调用以上所有的模块，若用户选择退出则程序结束。模块调用关系：主程序->菜单类-邻接链表类邻接矩阵类一、详细设计具体设计见程序注释#include#include#include#include#include#includeusingnamespacestd;

5、intn;//记录节点数vector>d1;vectormark1;vector>d2;vectormark2;voidfirst(intk);邻接链表的初始函数voidmake(int*a,int*b,intm);邻接链表的建图函数voidprint(void);邻接链表的打印函数voidDFS(void);邻接链表的先深遍历voidBFS(void);邻接链表的先广遍历voidfirst2(intk);邻接矩阵的初始函数voidmake2(int*a,int*b,intm);邻

6、接矩阵的建图函数voidprint2(void);邻接矩阵的打印函数voidDFS2(void);邻接矩阵的先深遍历voidBFS2(void);邻接矩阵的先广遍历主函数intmain(void){inta[128],b[128],k,m,x;do{printf("--------欢迎来到图操作系统--------");printf("1.请输入一个图");printf("2.利用邻接链表建图");printf("3.利用邻接矩阵建图");printf("4.退出");scanf("%d",&x);if(x==1){print

7、f("请输入节点的个数");scanf("%d",&k);printf("请输入相邻的节点，并以00结束");m=0;while(cin>>a[m]>>b[m]){if(a[m]==0&&b[m]==0)break;elsem++;}}elseif(x==2){first(k);make(a,b,m);print();printf("");BFS();printf("");DFS();printf("");}elseif(x==3){first2(k);make2(a,b,m);print2();printf("");BFS2

8、();printf("");DFS2();printf("");}elseif(x==4){prin