学步园

拓扑排序是图的算
法中经常碰到的一个算法，也经常用来判断图是否存在环等问题，算法的过程主要是：开始将所有入度为0的顶点进入一个阶列，将队列中的顶点出队列，即相当于
将该顶点从图中删除，同时删除与此顶点关联的边，删除边导致与顶点相关联的边的另一个顶点的入度减1，如果该同时入度又等于0，则将其放入队列中，循环下
去直至队列为空为止。循环开始前设置一个counter计数器，计算出队列的顶点数，如果循环结束后，出队列的顶点数不等于图的顶点的个数，那么即存在环。

在程序当前目录下建立graph.txt文件，写入下面内容，VC++ 6.0下程序运行通过。

v1  v2
v1  v3
v1  v4
v2  v4
v2  v5
v3  v6
v4  v3
v4  v6
v4  v7
v5  v4
v5  v7
v7  v6

/*<br /> # Graph Topsort Algorithm<br /> # Copyright (C) 2010-**** Long Cheng <fantasywindy@gmail.com><br /> # @version 1.1.1-20100720<br /> */<br /> #include <iostream><br /> #include <string><br /> #include <queue><br /> #include <fstream><br /> #include <sstream><br /> using std::cout;<br /> using std::cin;<br /> using std::endl;<br /> using std::string;<br /> using std::queue;<br /> using std::istringstream;<br /> using std::getline;<br /> using std::ifstream;<br /> #define MAX 100 //定义图的最大顶点数量为了100<br /> typedef struct Edge //定义图的边<br /> {<br /> int weight; //边的权值,此程序中没有用上<br /> int next; //边的结束顶点，如边v1->v2的话，那么next就是顶点v2的编号<br /> struct Edge *nextEdge; //下一个邻边<br /> } Edge;<br /> typedef struct Node<br /> {<br /> Edge *firstEdge; //从该顶点出发的第一条边<br /> int no; //顶点的编号(程序中的内部编号)<br /> int degree; //顶点的入度<br /> string val; //顶点的标签,如v1顶点显示为字符串"v1"<br /> }Node;<br /> typedef Node NodeList[MAX];<br /> typedef struct Graph //定义图的数据结构<br /> {<br /> int n; //图的顶点数<br /> int e; //图的边数(此程序中没有用上)<br /> NodeList nodes; //图的顶点数组<br /> }Graph;<br /> int SearchVertex(Graph *g, string str) //在图中寻找标记为"XXX"的顶点是否已经出现过<br /> {<br /> for(int i=0; i<g->n; ++i)<br /> {<br /> if( str == g->nodes[i].val )<br /> {<br /> return i;<br /> }<br /> }<br /> return -1;<br /> }<br /> void Topsort(Graph *g)<br /> {<br /> queue<int> q; //初始化队列<br /> for(int i=0; i<g->n; ++i) //开始时将入度为0的顶点先入栈<br /> {<br /> if( g->nodes[i].degree == 0 )<br /> {<br /> q.push(i);<br /> }<br /> }<br /> int counter=0; //出队列的顶点个数<br /> while( q.empty() == false )<br /> {<br /> int k=q.front(); //取队列首元素的编号后将其出队列<br /> q.pop();<br /> counter++; //出队列的顶点个数加1<br /> cout<<g->nodes[k].val<<endl;<br /> Edge *p=g->nodes[k].firstEdge; //遍历出队列的顶点的边，将所有与其相连的顶点的入度减1，如果某顶点的入度恰好变为0，则将其入队列<br /> while( p != NULL )<br /> {<br /> if( --(g->nodes[p->next].degree) == 0 )<br /> {<br /> q.push(p->next);<br /> }<br /> p=p->nextEdge;<br /> }<br /> }<br /> if( counter != g->n ) //如果最终出队列的顶点个数不等于图的顶点数，那么存在环。<br /> {<br /> cout<<"There is a circle!"<<endl;<br /> }<br /> }<br /> int main()<br /> {<br /> Graph *g=new Graph;<br /> string v1;<br /> string v2;<br /> int nodecount=0;<br /> int edgecount=0;<br /> cout<<"please input the edge of the graph. ( eg: a b )"<<endl;<br /> ifstream file("graph.txt");<br /> string line;<br /> while(getline(file,line)) //输入所有的边<br /> {<br /> istringstream istr(line);<br /> istr>>v1>>v2;<br /> int v1_no;<br /> int v2_no;<br /> if( ( v1_no=SearchVertex(g, v1) ) == -1 ) //判断边的两个顶点是否之前已经出现过，若未出现过，则初始化此顶点<br /> {<br /> g->nodes[nodecount].val=v1;<br /> g->nodes[nodecount].no=nodecount;<br /> g->nodes[nodecount].firstEdge=NULL;<br /> g->nodes[nodecount].degree=0;<br /> v1_no=nodecount;<br /> ++nodecount;<br /> g->n=nodecount;</p> <p> }<br /> if( ( v2_no=SearchVertex(g, v2) ) == -1 )<br /> {<br /> g->nodes[nodecount].val=v2;<br /> g->nodes[nodecount].no=nodecount;<br /> g->nodes[nodecount].firstEdge=NULL;<br /> g->nodes[nodecount].degree=0;<br /> v2_no=nodecount;<br /> ++nodecount;<br /> g->n=nodecount;</p> <p> }<br /> g->nodes[v2_no].degree++;</p> <p> Edge *e=new Edge; //将边插入对应的顶点的边链表<br /> e->next=v2_no;<br /> e->nextEdge=NULL;<br /> Edge *p=g->nodes[v1_no].firstEdge;<br /> Edge *q=NULL;<br /> while( p != NULL )<br /> {<br /> q=p;<br /> p=p->nextEdge;<br /> }<br /> if( q == NULL )<br /> {<br /> g->nodes[v1_no].firstEdge=e;<br /> }<br /> else<br /> {<br /> q->nextEdge=e;<br /> }<br /> }<br /> /*<br /> for( int i=0; i<g->n; ++i)<br /> {<br /> cout<<g->nodes[i].no<<'/t'<<g->nodes[i].val<<endl;<br /> }<br /> */<br /> Topsort(g);<br /> for(int i=0; i<g->n; ++i) //释放边new出来的堆空间<br /> {<br /> Edge *pre, *cur;<br /> cur=g->nodes[i].firstEdge;<br /> pre=NULL;<br /> while( cur != NULL )<br /> {<br /> pre=cur;<br /> cur=cur->nextEdge;<br /> delete pre;<br /> }<br /> }<br /> delete g; //释放图new 出来的空间<br /> return 0;<br /> }