[算法导论读书笔记]拓扑排序

算法思想：

算法导论中关于拓扑排序部分，讲得真是太好了。比按节点的入度的贪心法的拓扑排序容易理解，且容易实现。实现方法是这样的，用DFS遍历整个图，得出个节点的完成时间，然后按完成时间倒序排列就得到了图的拓扑排序序列。

例子：

[算法导论读书笔记]拓扑排序

伪代码：

[算法导论读书笔记]拓扑排序

代码示例：

#include <iostream>
#include <stdio.h>
#include <string.h>

#include <list>
using namespace std;

class Graph
{
private:
	int v;
	int times;//时间戳
	list<int> *adj;
	int *f;//记录节点的完成时刻
	int *tp;// 按finish的时间倒序存放在tp序列中
	void DFSUtil(int v, bool visited[]);
public:
	Graph(int v);//Construtor
	~Graph();//Construtor
	void addEdge(int v, int w);//function to add an edge to graph
	void DFS( /*int v*/);//DFS traversal of the vertices reachable from v
	void TopolgicalSort();
};

Graph::Graph(int v)
{
	this->v = v;
	this->times = 0;
	adj = new list<int>[v];
	f = new int[v];
	tp = new int[v];
	memset(f, 0, sizeof(f[0])*v);
	memset(tp, 0, sizeof(tp[0])*v);
}

void Graph::addEdge(int v, int w)
{
	adj[v].push_back(w);//Add w to v's list.
}

void Graph::DFSUtil(int v, bool visited[])
{
	//Mark the current node as node visited and print it
	if( visited[v] == false)
	{
		visited[v] = true;
		printf("%c  ", 'A' + v);

		//Recur for all the vertices adjacent to this vertex
		list<int>::iterator i;
		for( i = adj[v].begin(); i != adj[v].end(); ++i)
		{
			if( !visited[*i])
			{
				DFSUtil(*i, visited);
			}
		}
	f[v] = ++times;
	}
}

void Graph::DFS(/*int v*/)
{
	//Mark all the vertices as not visited
	bool *visited = new bool[v];
	for( int i = 0; i < v; i++)
		visited[i] = false;
	//Call the recrusive helper function to print DFS tracersal
	for( int i = 0; i < v; i++)
		DFSUtil(i, visited);
	printf("\n");
}

void Graph::TopolgicalSort()
{
	for( int i = 0; i < v; i++)
	{
		tp[v - f[i]] = i;// f的取值为 1——v,正好，tp[ v - fp[i]] 是节点的正确位置
	}

	for( int j = 0; j < v; j++)
	{
		printf("%c  ", tp[j] + 'A');
	}
	printf("\n");
}

Graph::~Graph()
{
	delete [] f;
	delete [] tp;
	delete [] adj;
}

int main(int argc, char* argv[])
{
// 0:A 1:B 2:C 3:D 4:E 5:F 6:G 7:H 8:I
	Graph g(9);
	g.addEdge(0, 1);
	g.addEdge(0, 5);
	g.addEdge(1, 5);
	g.addEdge(3, 2);
	g.addEdge(3, 7);
	g.addEdge(4, 1);
	g.addEdge(5, 7);
	g.addEdge(6, 2);
	g.addEdge(6, 4);
	g.addEdge(8, 2);
	g.addEdge(8, 4);


	g.DFS();
	g.TopolgicalSort();

	return 0;
}

参考资料：

http://blog.sina.com.cn/s/blog_6ec5c2d00100szit.html

相关题目：

poj 1094 Sorting It All Out

这个是个很经典的拓扑排序的题目，涉及到topsort的好几种操作；

首先是用邻接表存储各个点的先后顺序；

再用cnt【】数组存储每个点的入度；

每输入一条边就需判断一下，是否是矛盾（产生环），还是顺序已经确定；

如果输入完后，仍然不能判断就是“Sorted sequence cannot be determined.“；

贴段代码吧。。好长时间木贴过代码了。。 [算法导论读书笔记]拓扑排序

// poj 1094 TopSort
#include<iostream>
using namespace std;
#define MAXN 29

int N,M;
bool adj[MAXN][MAXN];
int cnt[MAXN];
char order[MAXN];
void joy_init()
{
     memset(adj,false,sizeof(adj));
}
int joy_topsort()
{
     memset(cnt,0,sizeof(cnt));
     memset(order,'\0',sizeof(order));
    int i,j,k;
    bool flag=true;
    for(i=1;i<=N;i++)
     {
        for(j=1;j<=N;j++)
         {
            if(adj[i][j]) cnt[j]++;
         }
     }
    for(i=1;i<=N;i++)cout<<cnt[j]<<" ";cout<<endl;
    for(k=1;k<=N;k++)
     {
         i=0;
        for(j=1;j<=N;j++)
         {
            if(cnt[j]==0)
             {
                if(i==0) i=j;
                else flag=false;          //找出入度为0的点
             }
         }

        if(i==0) return 0;          // 0 是矛盾（表示成环了）；1，是确定；2是不确定；
         cnt[i]=-1;
         order[k-1]=i+'A'-1;
        for(j=1;j<=N;j++)
         {
            if(adj[i][j]) cnt[j]--;
         }
     }
    if(flag) return 1;
    else return 2;
}
int main()
{
    int i,j,a,b,result;
    char s[10];
    while(scanf("%d%d",&N,&M))
     {
        if(N==0&&M==0) break;
         joy_init();
        bool h=false;
        for(i=1;i<=M;i++)
         {
             scanf("%s",s);
            if(h) continue;
             a=s[0]-'A'+1;b=s[2]-'A'+1;
             adj[a][b]=true;
             result=joy_topsort();
            if(result==0)
             {
                 printf("Inconsistency found after %d relations.\n",i);
                 h=true;
             }
            else if(result==1)
             {
                 printf("Sorted sequence determined after %d relations: %s.\n",i,order);
                 h=true;
             }
         }
        if(!h) printf("Sorted sequence cannot be determined.\n");
     }
     system("pause");
    return 0;
}

poj 2367 Genealogical tree

这个题灰常基本，尽管题目说的很深。。

就是找出符合条件的一组拓扑排序情形；

搞定poj1094后这个问题，就不是问题啦。。

poj 3272 Cow Traffic

这个题让老衲很无语啊。。题目的sample误导人误导的灰常绝啊。。

不过有点topsort的意思。。还有点动态规划的意思

也挺简单，计算出每条路径的前个点能从初始点到它的情况和后个点从目的地到他的情况；

我原来当成点中出现频率最大的了。。wa了。N久。。55555.。。

poj 3687 Labeling Balls

这个是windy出的题目，也是灰常经典的topsort题目；

要反向拓扑排序，按照weight从大到小分配；最后分配得到的正好是题目要求；

想明白的话，就很简单了。。topsort；

参考资料：http://hi.baidu.com/rain_bow_joy/blog/item/28daec17a049634020a4e9fd.html

秒客网

[算法导论读书笔记]拓扑排序

相关文章