c++课程设计-图的遍历和拓扑排序.doc

c+课程设计-图的遍历和拓扑排序#include#include#includeusing namespace std;const int MAX=20;/预定义图的最大结点数int visitedMAX;/用于深度优先遍历和广度优先遍历的标志数组class EdgeNode/边表结点类public:int adjvex;/邻接点的位序EdgeNode* next;/指向下一个邻接点的指针;class VertexNode/头结点类public:VertexNode()/无参构造函数，将入度值初始为零id=0;char vertex;/顶点信息EdgeNode* FirstEdge;/邻接表头指针int id;/该结点的入度;class Graph/图类public:VertexNode adjlistMAX;/存放头结点的顺序表int n,e;/图的顶点数和边数;void CreateFile();/建立存储有向图信息的txt文档void CreateDirectedGraph(Graph& g,char filename);/从文件中读取信息，创建有向图的邻接表void Dfs(Graph g,int i);/从结点i开始深度优先遍历图g的连通分量void DfsTraverse(Graph g);/深度优先遍历图gvoid Bfs(Graph g,int i);/从顶点i出发广度优先遍历图g的连同分量int BfsTraverse(Graph g);/广度优先遍历图g,返回值为强连通分量个数void TopSort(Graph g);/拓扑排序int main()Graph graph;/图对象CreateFile();/创建存放图信息的文件CreateDirectedGraph(graph,data.txt);/图对象初始化DfsTraverse(graph);/深度优先遍历BfsTraverse(graph);/广度优先遍历TopSort(graph);/拓扑排序return 0;void CreateFile()int n;/图的结点数int e;/图的边数int x,y;/有向边序列char data;/结点数据ofstream os(data.txt);/输出流对象，创建文件data.txtcoutn;osnn;coutendl;/输入顶点数，并且放入文件中，用回车与后面的数据分离coute;osen;coutendl;/输入边数，并且放入文件中，用回车与后面的数据分离cout请依次输入顶点数据：data;osdata ;osn;cout请依次输入边的有向序列对：endl;for(int i=0;i!=e;+i)cout第i+1xy;osx yn;coutendl;cout有向图文件建立完成！endl;cout按下回车继续.g.ng.e;/读入顶点数和边数for(i=0;ig.adjlisti.vertex;/读入顶点信息g.adjlisti.FirstEdge=NULL;/边表置为空for(int k=0;kij;s=new EdgeNode();/创建一个边表结点s-adjvex=j;/位序为js-next=g.adjlisti.FirstEdge;/将next指针指向序号为i的结点边表的头部g.adjlisti.FirstEdge=s;/将新结点s插入到序号为i的结点的头部g.adjlistj.id+;/将序号为j的顶点入度数加1is.close();/关闭文件流elseg.n=0;/如果文件打开失败，就将图的边数置为0void Dfs(Graph g,int i)EdgeNode* p;coutg.adjlisti.vertexadjvex)/如果没有访问过该顶点，就访问该顶点Dfs(g,p-adjvex);p=p-next;/如果访问过该顶点，就让它指向边表的后一个结点void DfsTraverse(Graph g)cout深度优先遍历:endl;for(int i=0;i!=g.n;+i)/n次循环将标记数组全部初始化为0visitedi=0;for(int i=0;i!=g.n;+i)if(!visitedi)/如果没有访问过该顶点，即访问该顶点Dfs(g,i);void Bfs(Graph g,int i)int j;EdgeNode* p;int queueMAX,head,tail;/先入先出队列head=-1;tail=-1;/初始化空队列couthead)/当队列非空时，执行下列循环体j=queue+head;/出队p=g.adjlistj.FirstEdge;while(p)/广度优先搜索邻接表if(0=visitedp-adjvex)coutadjvex.vertex;queue+tail=p-adjvex;visitedp-adjvex=1;p=p-next;int BfsTraverse(Graph g)cout广度优先遍历：;int count=0;/强连通分量计数器for(int i=0;i!=g.n;+i)/初始化标志数组visitedi=0;for(int i=0;i!=g.n;+i)if(!visitedi)/如果位序为i的顶点未被访问过coutendl;count+;/计数器加1Bfs(g,i);/从第i个结点出发广度优先遍历coutendl;return count;/返回强连通分量个数void TopSort(Graph g)coutAOV网的拓扑序列是:endl;int k=0,j,v;int queueMAX;/队列int h=0,t=0;EdgeNode* p;for(int i=0;i!=g.n;+i)visitedi=0;/访问标记初始化for(int i=0;i!=g.n;+i)/将所有入度为0的结点进队if(g.adjlisti.id=0 & visitedi=0)queue+t=i;visitedi=1;while(ht)/当队列不为空时v=queue+h;/队首元出对coutadjvex;i