1、烟台大学数据结构课程设计报告站点分布图（二）问题描述：尽可能多的列出烟台的公交站点。用图创建一个站点分布图，包括站点的增加、删除、从一点出发深度优先搜索所有的站点、从一点出发广度优先搜索所有的站点。数据结构与算法的设计：通过分析决定采用无向图结构，采用了深度优先遍历（DFS） ，广度优先遍历（BFS）等算法。程序实现：实现了深度优先输出所有站点，广度优先输出所有站点，增加站点，删除站点。测试及分析：源代码选摘：/-邻接矩阵转化成邻接表-/void MatToList(MGraph g,ALGraph *ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph
2、);for(i=1;iadjlisti.firstarc=NULL;for(i=1;i=1;j-)if(g.edgesij!=0)p=(ArcNode *)malloc(sizeof(ArcNode); /创建一个节点 *pp-adjvex=j; /该边的终点号p-nextarc=G-adjlisti.firstarc; /采用头插法插入 *pG-adjlisti.firstarc=p; G-n = g.n;G-e = g.e;/-深度优先遍历 -/int visitedMAXV;void DFS(ALGraph *G,int v) /v 表示顶点ArcNode *p;visitedv=1;
3、/置已访问标记coutadjlistv.firstarc;while(p!=NULL)if(visitedp-adjvex=0) /p-adjvex 顶点未访问，递归访问它DFS(G,p-adjvex);p=p-nextarc; /p 指向顶点 V 的下一个邻接点/-广度优先遍历 -/ i 既是他的顶点编号void BFS(ALGraph *G,int v)ArcNode *p;int queueMAXV,front=0,rear=0; /定义循环队列并初始化队头队尾int visitedMAXV; /定义存放顶点的访问标志的数组int w,i;for(i=0;in;i+) /访问标志数组初始
4、化visitedi=0;coutadjlistw.firstarc; /找顶点 W 的第一个邻接点while(p!=NULL)if(visitedp-adjvex=0) /若当前邻接顶点未被访问coutadjvexadjvex=1; /置顶点已被访问的标志为 1rear=(rear+1)%MAXV; /该顶点进队queuerear=p-adjvex;p=p-nextarc; /找顶点 W 的下一个邻接点coutm;g.e=g.e+m;int i,j;int p=0;while(pi;coutj;g.edgesij=1;g.edgesji=1;p+;outputLJJZ(g);MatToList(g,G);/-深度优先遍历-/for(int k=0;kn;k+) /初始化访问标记数组visitedk=0;int start=0; /从哪开始遍历coutstart;coutm;int p=0;while(p=g.n)g.edgesmp=0;g.edgespm=0;p+;
