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

一、 需求分析：（1） 本程序利用邻接表存入一个图，并将其使用广度和深度遍历，并将其使用拓扑排序输出来。（2） 本程序的目的在于了解图的存储结构，以及其遍历的方法和拓扑排序的应用。（3） 测试数据请参见测试结果那里。二、 概要设计：（1） 数据类型：ADT graphcsint vex；/结点的号码int next；/该结点所连接的下一个结点（2） 基本操作：class graphicscreate（int i，int j）初始条件：存在邻接数组操作结果：将结点i和结点j相连接，从而形成邻接表graphics（）操作结果：初始化各个数据init（）操作结果：做完深度遍历后重新初始化所需要的数据findfree（）操作结果：存在顶点数组，找到未用结点的下标并返回start(int i) 操作结果：启用结点，创建邻接数组dfs(int i,int n)初始条件：图已经创建。操作结果：对图进行广度优先遍历bfs(int i,int n)初始条件：图已经创建。操作结果：对图进行深度优先遍历toposort(int n)初始条件：有向图已经建立操作结果：输出拓扑排序的顺序（3） 主函数main（）声明类对象，调用各个函数。（4） 调用关系： 类graphics create（） main（） start（） toposort() bfs（），dsf（）三、详细设计：#includestruct graphics/声明所需的私有数据int vex50;/用于存入顶点的号码int next50;/用于存入指示字bool visited50;/表示该结点是否被访问 int front,rear;/队列的头尾指针int queue50;/队列，队列足够大所以不必判断它是否满int in50;/统计每个结点的入度public:/公有函数graphics()/构造函数，用于初始化数据for(int i=0;i50;i+)vexi=nexti=-1;/-1代表空，没有使用过ini=0;/先初始化为0visitedi=false;/false表示没有访问过void init()/做完深度遍历后，重新初始化数据front=-1;rear=-1;for(int i=0;i50;i+) visitedi=false;queuei=-1;int findfree()/找到可用的结点int i=0;while(vexi!=-1)i+;return i;void start(int i)/启用结点，创建邻接数组vexi=i;void create(int i,int j)/构造邻接表int k=findfree();/找到可用结点vexk=j;/记录结点号码int p=i; while(nextp!=-1)/寻找链尾指针p=nextp;nextp=k;/存入指示字 void dfs(int i,int n)/深度优先法遍历if(!visitedi)/判断有没被访问过 coutit;visitedi=true;/表示已被访问过 int p=nexti;while(p!=-1)int j=vexp;/访问下一个结点if(!visitedj)dfs(j,n);p=nextp; void bfs(int i,int n)/广度优先法遍历if(!visitedi) coutit;visitedi=true;/表示已经被访问rear+;/入队 queuerear=i;while(front!=rear)front+;/出队int k=queuefront;int p=nextk;while(p!=-1)/访问所连接的结点int j=vexp;if(!visitedj)coutjt;visitedj=true;/入队rear+;queuerear=j;p=nextp;void toposort(int n)/拓朴排序int i,j,k,top,m=0;/m用于判断是否有回路，在拓仆排序中这是不允许的int p;/声明一个指示字（相当于指针的功能）for(i=0;in;i+)/利用in数组记录每一个结点的入度p=nexti;while(p!=-1)j=vexp;/访问到该结点，入度加1inj+;p=nextp;top=-1;/初始化栈for(i=0;in;i+)/找到入度为0的一个结点if(ini=0)ini=top;top=i;while(top!=-1)j=top;top=intop;coutj ;/打印入度为0的结点号码m+;/统计打印结点数目p=nextj;while(p!=-1)/该结点所连接的结点入度减1，该结点的入度设为-1/以后不再访问k=vexp;ink-;if(ink=0)ink=top;top=k;p=nextp;coutendl;if(mn)/有回路的情况cout#Error! The network has a cycle#n;void main()int n;/结点的数目graphics obj;/类对象coutn;int i=0;for(i=0;in;i+)/启用结点obj.start(i);int j=0;for(i=0;in;i+)/构造邻接表cout#输入一个结点的连接结点结束时请输入-1#n;cout请输入结点ij;if(j=0&jn&i!=j)obj.create(i,j);else if(j!=-1)cout输入错endl;j=0;cout深度优先法遍历:;for(i=0;in;i+)/用一个循环，即使是非连通图也能访问所有的结点obj.dfs(i,n); coutn广度优先法遍历：;obj.init();for(i=0;in;i+)obj.bfs(i,n);coutn;cout拓朴排序为：;obj.toposort(n);函数调用如下： main()start() create() bfs() dfs() init( toposort() findfree() 类graphics 四、设计和调试分析：1 原设计在深度和广度遍历的时候，一开始没有加入if语句判断有没有访问过，导致多访问了几个结点。2 程序的实现我们使用了静态连接结构，故存储空间主要使用在各个数组上为空间复杂度O（n）。在时间复杂度上主要是创建邻接表的时候以及拓扑排序要花比较多的时间。最坏情况为n2故时间复杂度为O（n2）。3 虽然静态存储结构没有动态结构可以随时申请空间，我们需要将数组元素的个