图的邻接存储结构及其遍历和拓扑排序

《图的邻接存储结构及其遍历和拓扑排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、需求分析：（1）本程序利用邻接表存入一个图，并将其使用广度和深度遍历，并将其使用拓扑排序输出来。（2）本程序的目的在于了解图的存储结构，以及其遍历的方法和拓扑排序的应用。（3）测试数据请参见测试结果那里。二、概要设计：（1）数据类型：ADTgraphcs{intvex；//结点的号码intnext；//该结点所连接的下一个结点}（2）基本操作：classgraphics{create（inti，intj）初始条件：存在邻接数组操作结果：将结点i和结点j相连接，从而形成邻接表graphics（）操作结果：初始化各个数据init（）操作结果：做完深度遍历

2、后重新初始化所需要的数据findfree（）操作结果：存在顶点数组，找到未用结点的下标并返回start(inti)操作结果：启用结点，创建邻接数组dfs(inti,intn)初始条件：图已经创建。操作结果：对图进行广度优先遍历bfs(inti,intn)初始条件：图已经创建。操作结果：对图进行深度优先遍历toposort(intn)初始条件：有向图已经建立操作结果：输出拓扑排序的顺序}（3）主函数main（）{声明类对象，调用各个函数。}（4）调用关系：类graphicscreate（）main（）start（）toposort()bfs（），dsf（）

3、第7页共7页三、详细设计：#includestructgraphics{//声明所需的私有数据intvex[50];//用于存入顶点的号码intnext[50];//用于存入指示字boolvisited[50];//表示该结点是否被访问intfront,rear;//队列的头尾指针intqueue[50];//队列，队列足够大所以不必判断它是否满intin[50];//统计每个结点的入度public://公有函数graphics()//构造函数，用于初始化数据{for(inti=0;i<50;i++){vex[i]=next[i]

4、=-1;//-1代表空，没有使用过in[i]=0;//先初始化为0visited[i]=false;//false表示没有访问过}}voidinit()//做完深度遍历后，重新初始化数据{front=-1;rear=-1;for(inti=0;i<50;i++){visited[i]=false;queue[i]=-1;}}intfindfree()//找到可用的结点{inti=0;while(vex[i]!=-1)i++;returni;}voidstart(inti)//启用结点，创建邻接数组{vex[i]=i;}voidcreate(inti,in

5、tj)//构造邻接表第7页共7页{intk=findfree();//找到可用结点vex[k]=j;//记录结点号码intp=i;while(next[p]!=-1)//寻找链尾指针p=next[p];next[p]=k;//存入指示字}voiddfs(inti,intn)//深度优先法遍历{if(!visited[i])//判断有没被访问过cout<

6、);p=next[p];}}voidbfs(inti,intn)//广度优先法遍历{if(!visited[i])cout<

7、[rear]=j;}第7页共7页p=next[p];}}}voidtoposort(intn)//拓朴排序{inti,j,k,top,m=0;//m用于判断是否有回路，在拓仆排序中这是不允许的intp;//声明一个指示字（相当于指针的功能）for(i=0;i

8、]=top;top=i;}}while(top!=-1){j=top;top=i