拓扑排序---（图的领接表实现）

#include<iostream>
using namespace std;

#define MAX_NODE 30
#define MAX_INFO 10
bool isOutput[MAX_NODE];   //记录该节点有没有输出
struct ListNode
{
	ListNode(){next=NULL;}
	int position;				
	ListNode* next;				
};
struct VertexNode
{
	VertexNode()
	{
		head=NULL;
		inDegree=0;
	}
	int currentPosition;		//当前节点在图存储结构中数组的位置
	int inDegree;				//该节点的入度
	char info[MAX_INFO];		//该节点的信息
	ListNode* head;				//该节点相邻节点的第一个节点
};
struct Graphic
{
	int vertex,edge;
	VertexNode vers[MAX_NODE];
};

void createGraphic(Graphic& graphic)
{
	

	cout<<"请输入节点数和边数: ";
	cin>>graphic.vertex>>graphic.edge;

	cout<<"请输入节点信息:"<<endl;
	int i;
	for(i=0;i<graphic.vertex;i++)
	{
		cout<<"请输入第"<<i<<"个节点信息:";
		cin>>graphic.vers[i].info;
		
	}

	cout<<"请输入边信息:"<<endl;

	int first=0;
	int second=0;
	for(i=0;i<graphic.edge;i++)
	{
		cout<<"请输入第"<<i<<"条边信息:";
		cin>>first>>second;
		ListNode* temp=new ListNode;
		temp->position=second;
		temp->next=graphic.vers[first].head;
		graphic.vers[first].head=temp;
		++graphic.vers[second].inDegree;		
	}

	for(i=0;i<graphic.vertex;i++)
	{
		isOutput[i]=false;
	}

	for(i=0;i<graphic.vertex;i++)
	{
		graphic.vers[i].currentPosition=i;
	}
}

void printGraphic(Graphic graphic)
{
	int i;
	ListNode* temp=NULL;
	for(i=0;i<graphic.vertex;i++)
	{
		cout<<graphic.vers[i].info<<"--->";
		temp=graphic.vers[i].head;
		if(!temp)
		{
			cout<<"NULL";
		}
		while(temp)
		{
			cout<<temp->position<<" ";
			temp=temp->next;
		}
		cout<<endl;
	}

	for(i=0;i<graphic.vertex;i++)
	{
		cout<<"节点"<<i<<"的入度:";
		cout<<graphic.vers[i].inDegree<<endl;
	}
	cout<<endl;
}
VertexNode* findZeroInDegreeNode(Graphic& graphic)
{
	int i;
	for(i=0;i<graphic.vertex;i++)
	{
		if(graphic.vers[i].inDegree==0)
		{
			graphic.vers[i].inDegree=1;
			return &graphic.vers[i];			
		}
	}
	return NULL;
}

void TopologicalSortForVertex(Graphic& graphic,int position)
{
	ListNode* head=graphic.vers[position].head;
	while(head)
	{
		if(!isOutput[head->position])
		{
			cout<<graphic.vers[head->position].info<<" ";
			isOutput[head->position]=true;
		}
		TopologicalSortForVertex(graphic,head->position);
		head=head->next;
	}
}
void TopologicalSort(Graphic& graphic)
{
	VertexNode* zeroNode=findZeroInDegreeNode(graphic);
	if(!zeroNode)
		return;
	if(!isOutput[zeroNode->currentPosition])
	{
		cout<<zeroNode->info<<" ";
		isOutput[zeroNode->currentPosition]=true;
	}
	
	TopologicalSortForVertex(graphic,zeroNode->currentPosition);
	TopologicalSort(graphic);
}
void main()
{
	Graphic myGraphic;
	createGraphic(myGraphic);
	printGraphic(myGraphic);
	TopologicalSort(myGraphic);
}

补充：软件开发 , C++ ,

上一个：poj 1523 SPF（tarjan求割点）
下一个：POJ 2828 Buy Tickets