拓扑排序---（图的领接表实现）
#include<iostream>using namespace std;#define MAX_NODE 30#define MAX_INFO 10bool 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);}