拓扑排序.cpp

图的DFS遍历

#include <iostream>
using namespace std;
#include "Graph.h"
#define NULL 0
#include<assert.h>
#include<queue>

class stack
{
public:
	int *f;
	int top,ms;
	stack(int s)
	{
		ms=s;
		f=new int[s];
		top=-1;
	}

	int pop()
	{
		assert(!empty());
		return f[top--];
	}



	void push(int i)
	{
		assert(!full());
		top++;
		f[top]=i;
	}

	
	int empty()
	{return top==-1;}


	int full()
	{
		return top==ms-1;
	}

};







struct listUnit
{
	int vertex;
	int weight;
};


template<class Elem>
class Link
{
public:
	Elem element;              
	Link *next;                
	Link(const Elem& elemval,Link *nextval=NULL)
	{
		element=elemval;
		next=nextval;
	}
	Link(Link * nextval=NULL){next=nextval;}
};


template <class Elem>
class LList
{
public:
	Link<Elem>  *head;
	Link<Elem> *tail;
	LList()
	{
		head=tail=new Link<Elem>();
	}


	void removeall()
	{
		Link<Elem> *fence;
		while(head!=NULL)
		{
			fence=head;
			head=head->next;
			delete fence;
		}
	}
	~LList(){removeall();}
	void Insert(int vertex_val=0,int weight_val=0)
	{
		listUnit a;
		a.vertex=vertex_val;
		a.weight=weight_val;
		tail=tail->next=new Link<Elem>(a);
	}



};

class Graphl:public Graph
{
private:
	LList<listUnit> *graList;
	
public:
	Graphl(int numVert):Graph(numVert)
	{
		graList=new LList<listUnit>[numVertex];
	
	}
	~Graphl()
	{
		delete [] graList;
		
	}

	
	Edge FirstEdge(int oneVertex)
	{
		Edge myEdge;
		myEdge.from=oneVertex;
		myEdge.to=-1;
		Link<listUnit> *temp=graList[oneVertex].head;
		if(temp->next!=NULL)
		{
			myEdge.to=temp->next->element.vertex;
			myEdge.weight=temp->next->element.weight;
		}
		return myEdge;
	}

	
	Edge NextEdge(Edge preEdge)
	{
		Edge myEdge;		
		myEdge.from=preEdge.from;
		myEdge.to=-1;
		Link<listUnit> *temp=graList[preEdge.from].head;
		while((temp->next!=NULL)&&(temp->next->element.vertex<=preEdge.to))
			temp=temp->next;
		if(temp->next==NULL)
			return myEdge;
		else
		{
			myEdge.to=temp->next->element.vertex;
			myEdge.weight=temp->next->element.weight;
			return myEdge;
		}
	}



	void setEdge(int from,int to,int weight)
	{
		Link<listUnit> *temp=graList[from].head;
		while(temp->next!=NULL&&temp->next->element.vertex<to)
			temp=temp->next;
		if(temp->next==NULL)
		{
			temp->next=new Link<listUnit>;
			temp->next->element.vertex=to;
			temp->next->element.weight=weight;
			numEdge++;
			Indegree[to]++;
			outdegree[from]++;
			return;
		}
		if(temp->next->element.vertex==to)
		{
			temp->next->element.weight=weight;
			return;
		}
		if(temp->next->element.vertex>to)
		{
			Link<listUnit> *other=temp->next;
			temp->next=new Link<listUnit>;
			temp->next->element.vertex=to;
			temp->next->element.weight=weight;
			temp->next->next=other;
			numEdge++;
			Indegree[to]++;
			outdegree[from]++;
			return;
		}
	}

	void delEdge(int from,int to)
	{
		Link<listUnit> *temp=graList[from].head;
		while(temp->next!=NULL&&temp->next->element.vertex<to)
			temp=temp->next;
		if(temp->next==NULL)
			return;
		if(temp->next->element.vertex>to)
			return;
		if(temp->next->element.vertex==to)
		{
			Link<listUnit> *other=temp->next->next;
			delete temp->next;
			temp->next=other;
			numEdge--;
			Indegree[to]--;
			outdegree[from]--;
			return;
		}
	}

	
	void init(int **mt)
	{
		int n=VerticesNum();
		int m=0;
		for(int i=0;i<n;i++)
		{	for(int j=0;j<n;j++)
			{
				if(*((int *)mt+n*i+j)!=0)
					setEdge(i,j,1);
			}
		}
	}




    
	void print2()
	{
		
		int n=VerticesNum();
		for(int i=0;i<n;i++)
		{
			Link<listUnit> * temp=graList[i].head;
			while(temp->next!=NULL)
			{
				cout<<"("<<i<<","<<temp->next->element.vertex<<")"<<",";
				temp=temp->next;
			}
			cout<<endl;
		}
	}

	void verticesoutnum()
	{
		int n=VerticesNum();
		for(int i=0;i<n;i++)
		{

			int k=0;
			Link<listUnit> * temp=graList[i].head;
			while(temp->next!=NULL)
			{
				k++;
				temp=temp->next;
			}
			cout<<i<<"的出度为："<<k<<endl;
		}
	}


	void verticesinnum()
	{
		int n=VerticesNum();
		for(int i=0;i<n;i++)
		{
		
			int k=Indegree[i];
			cout<<i<<"的入度为："<<k<<endl;
		}
	}



int pre(int v)
{
	int m=Indegree[v];
    if(m==0)
		return 1;
	
    else
	{
		int k=0;
		int n=0;
	    for(int i=0;i<numVertex;i++)
		{
			Link<listUnit> * t=graList[i].head;
			while(t->next!=NULL)
			{
		     	t=t->next;
				if (t->element.vertex==v)
                 k++;
			    if ((t->element.vertex==v)&&(Mark[i]==VISITED))
				n++;
			}
	//	if(k==m)
		//	break;
		
		}

	if (n==m)
		return 1;
	else
		return 0;

	}
}			 



void pre1(int v)
{
	int m=Indegree[v];
	int n=0;
	if(m!=0)
	  for(int i=0;i<numVertex;i++)
	  {
		  Link<listUnit> * t=graList[i].head;
			while(t->next!=NULL)
			{
		     	t=t->next;
				if (t->element.vertex==v)
                {
					n++;
					outdegree[i]--;
				} 
			}
		if(n==m)
			break;
	  }
	

}
};


void p(Graphl &g)
{
	for(int i=0;i<g.VerticesNum();i++)
	{
		cout<<g.outdegree[i]<<"  ";
	}
}
void visit(int i)
{
	cout<<i<<",  ";
}

void DFS(Graphl &g,int v)
{
	g.Mark[v]=VISITED;
	cout<<v<<",  ";
	  for(Edge a=g.FirstEdge(v);g.IsEdge(a);a=g.NextEdge(a))
	  if(g.Mark[g.ToVertex(a)]==UNVISITED)
		  DFS(g, g.ToVertex(a));
  }


 void travel(Graphl &g)
  {
	  int n=g.VerticesNum();
	  for(int i=0;i<n;i++)
		  g.Mark[i]=UNVISITED;
	  for(i=0;i<n;i++)
		  if(g.Mark[i]==UNVISITED)
			  DFS(g,i);
 }


void DFS1(Graphl &g,int v,stack &s)
{
	g.Mark[v]=VISITED;
	  for(Edge a=g.FirstEdge(v);g.IsEdge(a);a=g.NextEdge(a))
	  if(g.Mark[g.ToVertex(a)]==UNVISITED)
		  DFS1(g, g.ToVertex(a),s);
	  s.push(v);
	  	
  }



 void NonSuccFirstTopSort1(Graphl &g)
 {
	 int n=g.VerticesNum();
	 stack s(n);
	 for(int i=0;i<n;i++)
		g.Mark[i]=UNVISITED;
	for(i=0;i<n;i++)
		if(	g.Mark[i]==UNVISITED)	
			DFS1(g,i,s);
		while(!s.empty())
			cout<<s.pop()<<"  ";
 }





void NonSuccFirstTopSort(Graphl &g)
{
	int n=g.VerticesNum();
	for(int i=0;i<n;i++)
		g.Mark[i]=UNVISITED;
	stack s(n);
	queue<int>q;
	for( i=0;i<g.VerticesNum();i++)
		if(g.outdegree[i]==0)
		{
		
		    q.push(i);
			g.Mark[i]=VISITED;
		}
		
		while(!q.empty())
		{
			int v=q.front();
			q.pop();
			s.push(v);
		
			g.pre1(v);
			for( i=0;i<g.VerticesNum();i++)
			{
			
				if((g.outdegree[i]==0)&&(g.Mark[i]==UNVISITED))
				{
					q.push(i);
					g.Mark[i]=VISITED;
				}

			}
		
		}

		while(!s.empty())
			cout<<s.pop()<<"  ";
 }

                




void isTopSort(Graphl &g,int *p)
{
	int n=g.VerticesNum();
	int k=1;
	for(int i=0;i<n;i++)
	g.Mark[i]=UNVISITED;
	for( i=0;i<n;i++)
	{
		int j=p[i];
		g.Mark[j]=VISITED;
		if(g.pre(j)==0)	
			k=0;	
	}	
		for( i=0;i<n;i++)
		{
			cout<<p[i]<<" ";
		}

	if(k==0)
			cout<<"不是拓扑排序！"<<endl;
	else
			cout<<"是拓扑排序！"<<endl;
	
}




void main()
{
	int m2[9][9]={{0,0,1,0,0,0,0,1,0},
	{0,0,1,1,1,0,0,0,0},
	{0,0,0,1,0,0,0,0,0},
	{0,0,0,0,0,1,1,0,0},
	{0,0,0,0,0,1,0,0,0},
	{0,0,0,0,0,0,0,0,0},
	{0,0,0,0,0,0,0,0,0},
	{0,0,0,0,0,0,0,0,1},
	{0,0,0,0,0,0,1,0,0}
	};
	Graphl GM2(9);
	GM2.init((int **)m2);
	cout<<endl;
	cout<<"这个图的边数是:"<<GM2.EdgesNum()<<"   "<<"顶点数是:"<<GM2.VerticesNum()<<endl<<endl;
	cout<<"边的情况:"<<endl;
	GM2.print2();
	cout<<endl;
	GM2.verticesinnum();
	cout<<endl;
	GM2.verticesoutnum();
	cout<<endl;
	cout<<"图的DFS遍历:"<<endl;
	travel(GM2);
	cout<<endl<<endl;
	cout<<"用DFS实现的拓扑排序是："<<endl;
	NonSuccFirstTopSort1(GM2);
	cout<<endl;
	cout<<"图的另一种无后继的拓扑排序是："<<endl; 
	NonSuccFirstTopSort(GM2);
	cout<<endl;
	cout<<endl<<endl;
	int m6[9]={1,4,0,7,8,2,3,6,5};
	isTopSort(GM2,m6);
	int m7[9]={0,1,7,2,8,3,4,6,5};
	isTopSort(GM2,m7);
	int m3[9]={0,1,2,3,4,5,7,8,6};
	isTopSort(GM2,m3);
	int m4[9]={0,7,8,1,4,2,3,6,5};
	isTopSort(GM2,m4);
	int m5[9]={6,7,1,4,2,3,5,0,8};
	isTopSort(GM2,m5);
	
}