graph.cpp

数据结构作业图的一些集合 上面有优先遍历 和用链表和堆栈来实现的算法

#include"iostream"
#include"Graph.h"
using namespace std;
//私有成员的实现
int Graph::GetVertexPos(const char & aName)
{
	int temp=0;
	VertexLink.currptr=VertexLink.front;
    while(VertexLink.currptr!=NULL)
	{
		if(VertexLink.currptr->data==aName)
			return temp;
   		VertexLink.currptr=	VertexLink.currptr->NextNode();
        temp++;
	}
	return -1;
}
bool Graph::FindVertex(const char & aName)
{
	VertexLink.currptr=VertexLink.front;
    while(VertexLink.currptr!=NULL)
	{
		if(VertexLink.currptr->data==aName)
			return 1;
   		VertexLink.currptr=	VertexLink.currptr->NextNode();
	}
	return 0;
}
void Graph::GetVertex(const int & item)
{
	VertexLink.currptr=VertexLink.front;
	for(int i=0;i<item;i++)
		VertexLink.currptr=VertexLink.currptr->NextNode();
	cout<<VertexLink.currptr->data<<" ";
}
//构造、析构函数
Graph::Graph(const  int Size):GraphSize(Size)
{
	char name;
	char from,to;
	int weight;
	//初始化数组
	for(int i=0;i<GraphSize;i++)
		for(int j=0;j<GraphSize;j++)
			if(i!=j)
	     		Edge[i][j]=10000;
			else
				Edge[i][j]=0;
	//录入链表
	cout<<"Please input the number of the vertex in the graph:"<<endl;
	cout<<"Make sure that the number must be no more than "<<GraphSize<<endl;
	cin>>CurSize;
	cout<<"Please input the name of the vertex in the graph:"<<endl;
	for(i=0;i<CurSize;i++)
	{
		cin>>name;
		VertexLink.InsertRear(name);
	}
	//录入邻接矩阵
	cout<<"Please input the number of the edge in the graph:"<<endl;
	cin>>EdgeSize;
	cout<<"Please input the start vertex name,the end vertex name,the weight of the edge in the graph:"<<endl;
	cout<<"If the graph is no direction one,Plese input twice in different order!"<<endl;
	for(i=0;i<EdgeSize;i++)
	{
	   cin>>from>>to>>weight;
	   InsertEdge(from,to,weight);
	}
}
Graph::~Graph()
{
	cout<<"The relationship in the graph is:"<<endl;
	VertexLink.currptr=VertexLink.front;
	for(int i=0;i<CurSize;i++)
	{
        cout<<VertexLink.currptr->data<<" ";
		for(int j=0;j<CurSize;j++)
			cout<<Edge[i][j]<<" ";
        VertexLink.currptr=VertexLink.currptr->NextNode();
		cout<<endl;
	}
}
//度处理
void Graph::GetDegree()
{
	int count;
	VertexLink.currptr=VertexLink.front;
	for(int i=0;i<CurSize;i++)
	{
		count=0;
		for(int j=0;j<CurSize;j++)
			if((Edge[i][j]!=0)&&(Edge[i][j]!=10000))
				count++;
		cout<<"The degree of the vertex "<<VertexLink.currptr->data<<" is:"<<count<<endl;
        VertexLink.currptr=VertexLink.currptr->NextNode();
	}
}
void Graph::InDegree()
{
	int count;
	VertexLink.currptr=VertexLink.front;
	for(int j=0;j<CurSize;j++)
	{
		count=0;
		for(int i=0;i<CurSize;i++)
			if((Edge[i][j]!=0)&&(Edge[i][j]!=10000))
				count++;
		cout<<"The in degree of the vertex "<<VertexLink.currptr->data<<" is:"<<count<<endl;
        VertexLink.currptr=VertexLink.currptr->NextNode();
	}
}
void Graph::OutDegree()
{
	int count;
	VertexLink.currptr=VertexLink.front;
	for(int i=0;i<CurSize;i++)
	{
		count=0;
		for(int j=0;j<CurSize;j++)
			if((Edge[i][j]!=0)&&(Edge[i][j]!=10000))
				count++;
		cout<<"The out degree of the vertex "<<VertexLink.currptr->data<<" is:"<<count<<endl;
        VertexLink.currptr=VertexLink.currptr->NextNode();
	}
}
//判满判空
bool Graph::GraphEmpty()
{
	return CurSize==0;                                                                                
}
bool Graph::GraphFull()
{
	return CurSize==GraphSize;
}
//返回指定边的权值
int Graph::GetWeight(const char & aName,const char & anotherName)
{
   int p1=GetVertexPos(aName);
   int p2=GetVertexPos(anotherName);
   if((p1!=-1)&&(p2!=-1))
     return Edge[p1][p2];
    else
		return 10000;
}
//邻接顶点的寻找
int Graph::GetFirstNeighbor(const int & item)
{
	for(int i=0;i<CurSize;i++)
		if((Edge[item][i]!=0)&&(Edge[item][i]!=10000))
			return i;
	return -1;
}
int Graph::GetNextNeighbor(const int & item,const int & temp)
{
	if(item!=-1&&temp!=-1)
	{
		for(int i=temp+1;i<CurSize;i++)
		   if((Edge[item][i]!=0)&&(Edge[item][i]!=10000))
			  return i;
	}
	return -1;
}

//对图的修改
void Graph::InsertVertex(const char & aName)
{
	VertexLink.InsertRear(aName);
	CurSize++;
}
void Graph::InsertEdge(const char & aName,const char & anotherName,int weight)
{
   int p1=GetVertexPos(aName);
   int p2=GetVertexPos(anotherName);
   if((p1!=-1)&&(p2!=-1))
      Edge[p1][p2]=weight;
   else
      cout<<"Tere are no those vertexes in the graph! "<<endl;
}
void Graph::DeleteVertex(const char & aName)
{
	int temp=GetVertexPos(aName);
	if(temp!=-1)
	{
		VertexLink.DeleteNode(aName);
		CurSize--;
		for(int i=0;i<temp;i++)
			for(int j=temp+1;j<=CurSize;j++)
				Edge[i][j-1]=Edge[i][j];
		for(i=temp+1;i<=CurSize;i++)
			for(int j=0;j<temp;j++)
				Edge[i-1][j]=Edge[i][j];
		for(i=temp+1;i<=CurSize;i++)
			for(int j=temp+1;j<=CurSize;j++)    
				Edge[i-1][j-1]=Edge[i][j];
		for(i=0;i<=CurSize;i++)
			Edge[i][CurSize]=10000;
		for(int j=0;j<=CurSize;j++)
			Edge[CurSize][j]=10000;
	}
	else
		cout<<"There is no such vertex in the graph!"<<endl;
}
void Graph::DeleteEdge(const char & aName,const char & anotherName)
{
   int p1=GetVertexPos(aName);
   int p2=GetVertexPos(anotherName);
   if((p1!=-1)&&(p2!=-1)&&(Edge[p1][p2]!=0)&&(Edge[p1][p2]!=10000))
      Edge[p1][p2]=0;
   else
	   cout<<"There is no such edge in the graph!"<<endl;
}
//遍历函数
void Graph::DepthFirstSearch(const int & item,int visited[])
{
	GetVertex(item);
    visited[item]=1;
	int temp=GetFirstNeighbor(item);
	while(temp!=-1)
	{
		if(!visited[temp])
			DepthFirstSearch(temp,visited);
		temp=GetNextNeighbor(item,temp);
	}
}
void Graph::DepthFirstSearch()
{
	cout<<"The result of depth first search is:"<<endl;
    for(int i=0;i<CurSize;i++)
		visited[i]=0;
	DepthFirstSearch(0,visited);
	cout<<endl;
}
void Graph::BreadthFirstSearch()
{
	cout<<"The result of breadth first search is:"<<endl;
	for(int i=0;i<CurSize;i++)
		visited[i]=0;
    aqueue.QInsert(0);
    visited[0]=1;
	while(!aqueue.QEmpty())
	{
		int temp=aqueue.QDelete();
		GetVertex(temp);
        int w=GetFirstNeighbor(temp);
		while(w!=-1)
		{
			if(visited[w]!=1)
			{
				aqueue.QInsert(w);
				visited[w]=1;
			}

			w=GetNextNeighbor(temp,w);
		}
	    	
	}
	cout<<endl;
}
/*void Graph::TopoOrder()
{
	cout<<"The topo order of the graph is :"<<endl;

}
//应用
void Graph::MinimumPath(const char & starv,const char & endv)
{}
*/