graph.h

自己在以前学数据结构时用C++模板写的一些常用数据,都测试过

	}
	else
		verticesList[numberVertices++]=vertex;		//注这等号要重载
}

template <class Type>
void MGraph<Type>::RemoveVetex(int v)//删除结点位置在v处的结点
{
	if(v>numberVertices)
	{
		cerr<<"out of the range:"<<endl;
		exit(1);
	}
	for(int i=0;i<numberVertices;i++)
		for(int j=0;j<numberVertices;j++)
			if((i==v||j==v)&&Edge[i][j]>0&&Edge[i][j]<MaxWeight)
			{
				Edge[i][j]=MaxWeight;
				numberVertices--;
			}
}

template <class Type>
void MGraph<Type>::InsertEdge(int u,int v,int weight)
{
	if(u<0||u>numberVertices||v<0||v>numberVertices)
	{
		cerr<<"out of the range!!"<<endl;
		exit(1);
	}
	Edge[u][v]=weight;
	numberEdges++;
}

template <class Type>
void MGraph<Type>::RemoveEdge(int u,int v)
{
	if(u<0||u>numberVertices||v<0||v>numberVertices)
	{
		cerr<<"out of the range!!"<<endl;
		exit(1);
	}
	Edge[u][v]=Maxweight;
	numberEdges--;	
}

template <class Type>
void MGraph<Type>::DFS(int v,int visit[])
{
	cout<<verticesList[v]<<setw(3);
	visit[v]=1;
	int w=GetFirstNeighbor(v);
	while(w!=-1)
	{
		if(!visit[w])DFS(w,visit);
		w=GetNextNeighbor(v,w);
	}
}

template <class Type>
void MGraph<Type>::DFS()
{
	int v;
	int *visited=new int[numberVertices];
	for(int i=0;i<numberVertices;i++)
		visited[i]=0;
	cout<<"please input the vertex you want to first visit(DFS):";
	cin>>v;
	cout<<"the DFS traverse order is:";
	DFS(v,visited);
	cout<<endl;
}

template <class Type>
void MGraph<Type>::BFS(int v,int visit[])
{
	Type u,w;
	Queue<Type> Q;
	cout<<"the BFS traverse order is:"<<endl;
	cout<<verticesList[v]<<setw(3);
	Q.EnQueue(verticesList[v]);
	visit[v]=1;
	while(!Q.IsEmpty())
	{
		u=Q.DelQueue();
		w=GetFirstNeighbor(GetVertexPos(u));
		while(w!=-1)
		{
			if(!visit[w])
			{
				cout<<verticesList[w]<<setw(3);
				visit[w]=1;
				Q.EnQueue(verticesList[w]);
			}
			w=GetNextNeighbor(u,w);//顶点U的所有邻接顶点入队
		}
	}
}

template <class Type>
void MGraph<Type>::BFS()
{
	int v;
	int *visited=new int[numberVertices];
	for(int i=0;i<numberVertices;i++)
		visited[i]=0;
	cout<<"please input the vertex you want to first visit(BFS):";
	cin>>v;
	BFS(v,visited);
	cout<<endl;
}

template <class Type>
void MGraph<Type>::PrimeMinTree()//普里母算法
{
	minTree=new TreeNode<Type>[numberVertices];
	float *lowcost=new float[numberVertices];
	for(int i=1;i<numberVertices;i++)
	{
		lowcost[i]=Edge[0][i];
		minTree[i].vertex=verticesList[0];
	}
	minTree[0].vertex=verticesList[0];
	cout<<"the first node is:"<<minTree[0].vertex;
	for(i=1;i<numberVertices;i++)
	{
		float mincost=MaxWeight;
		int j=1,k=1;
		while(j<numberVertices)
		{
			if(lowcost[j]<mincost&&lowcost[j]!=0)
			{
				mincost=lowcost[j];
				k=j;
			}
			j++;
		}
		cout<<"the node value is:"<<verticesList[k]<<setw(3)<<mincost<<endl;
		lowcost[k]=0;
		for(j=1;j<numberVertices;j++)
		{
			if(GetWeight(k,j)<lowcost[j])
			{
				lowcost[j]=GetWeight(k,j);
				minTree[j].vertex=verticesList[k];
			}
		}	
	}
}

template <class Type>
void MGraph<Type>::KruskalMinTree(Type vertex);//克鲁思卡算法生成图中最小生成树
{
	int n=numberVertices;
	int *vest=new int[n];
	for(int i=0;i<n;i++)
		vest[i]=i;//初始化
	int k=1,j=0;//k表示当前构造最小生成树的第几条边，初值为１,j为图中边的下标，初值为0
	while(k<n)//生成边数小于Ｎ时循环
	{
		Edge
	}

}

template <class Type>
int MGraph<Type>::NumberOfArray(int *a)
{
	int k=0;
	while(a[k]!=100)k++;
	return k;
}

/////////////////////////广度优先找最短路线(不足之处：不能记录最小路线)/////////////////////////
template <class Type>
void MGraph<Type>::ShortPath(Type vertex)
{
	int n=numberVertices;
	int pos=GetVertexPos(vertex);
	int *weightFound=new int[n];
	smallestWeight=new float[n];
	Type (*path)[10]=new Type[n][10];		//记录各最小路线,最后以100结束(先且以这个为标记)
	float minWeight;
	int i,j,v,k;
	v=pos;
	for(i=0;i<n;i++)		//将路线数组标记(以100标记)
		for(j=0;j<10;j++)
			path[i][j]=100;
	for(j=0;j<n;j++)
	{	
		smallestWeight[j]=Edge[pos][j];//数组中存放顶点pos到其它各顶点的直接路线的权值
		weightFound[j]=0;		//设标志来标记顶点pos到顶点j的最小是路线是否找到
		path[j][0]=pos;			//路线的第一个为pos
	}
	weightFound[pos]=1;			//顶点pos的最小路线不用找(自己到自己长度为零)
	smallestWeight[pos]=0;
	path[pos][0]=pos;
	for(i=0;i<n-1;i++)		//找出顶点pos到其它各顶点(n-1)个的最小路线
	{
		k=1;
		minWeight=MaxWeight+1;
		for(j=0;j<n;j++)	//找出顶点pos到乘下的要找的顶点的最短路线权值和顶点(利用下的循环来不断更新pos到各顶点的路线权值)
		{
			if(!weightFound[j])
				if(minWeight>smallestWeight[j])
				{
					v=j;
					minWeight=smallestWeight[v];
				}
		}
		weightFound[v]=1;			//顶点的pos到顶点v的最短路线己找到,	//或如果一遍遍历完没有找到比当前路费小的则标志当前的路费最小
		int num=NumberOfArray(path[v]);
		path[v][num++]=v;
		path[v][num++]=100;
		for(j=0;j<n;j++)				//当找一个最小路线(pos->v)时更新顶点pos到顶点j的最短路线(pos->v->j)但这个并不是最终值
		{								//即当找一个最小路线时就要更新pos到其它顶点的最短路线
			if(!weightFound[j])
				if(minWeight+Edge[v][j]<smallestWeight[j])
				{
					smallestWeight[j]=minWeight+Edge[v][j];	
					int num=NumberOfArray(path[j]);
					for(int t=1;path[v][t]!=100;)
						path[j][num++]=path[v][t++];
				}	
		}
		
	}
	cout<<endl<<"the weight is:"<<endl;
	for(i=0;i<n;i++)
		cout<<smallestWeight[i]<<setw(5);	
	for(i=0;i<n;i++)
	{
		cout<<"the "<<i<<" node's short path is:";
		for(j=0;j<10;j++)
			if(path[i][j]==100)
				break;
			else
				cout<<path[i][j]<<setw(3);
		cout<<endl;
	}

}
//-------------------------末完成---------------------------//
template <class Type>
void MGraph<Type>::ShortPathBFS(int pos)
{
	Queue<Type> Q;
	int n=numberVertices;
	int *weightFound=new int[n];
	smallestWeight=new float[n];
	float minWeight;
	int i,j,v,k;
	v=pos;
	k=1;
	for(j=0;j<n;j++)
	{	
		smallestWeight[j]=Edge[pos][j];//数组中存放顶点pos到其它各顶点的直接路线的权值
		weightFound[j]=0;		//设标志来标记顶点pos到顶点j的最小是路线是否找到
	}
	weightFound[pos]=1;			//顶点pos的最小路线不用找(自己到自己长度为零)
	smallestWeight[pos]=0;
	for(i=0;i<n-1;i++)		//找出顶点pos到其它各顶点(n-1)个的最小路线
	{
		minWeight=MaxWeight+1;
		for(j=0;j<n;j++)	//找出顶点pos到乘下的要找的顶点的直接最短线权值和顶点
		{
			if(!weightFound[j])
				if(minWeight>smallestWeight[j])
				{
					v=j;
					minWeight=smallestWeight[v];
				}
		}
		weightFound[v]=1;			//顶点的pos到顶点v的最短路线己找到,	
		Q.EnQueue(v);
		for(j=0;j<n;j++)				//找出顶点pos到顶点j的最短路线
		{
			if(!weightFound[j])
				if(minWeight+Edge[v][j]<smallestWeight[j])
				{
					smallestWeight[j]=minWeight+Edge[v][j];	
					
				}	
		}
		
	}
	cout<<endl<<"the weight is:"<<endl;
	for(i=0;i<n;i++)
		cout<<smallestWeight[i]<<setw(5);	
} 


template <class Type>
void MGraph<Type>::FindInDegree(int *&indegree)
{
	int n=numberVertices;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			if(Edge[i][j]!=0&&Edge[i][j]<MaxWeight)
				indegree[j]++;
}

template <class Type>
void MGraph<Type>::ChangeDegree(int *&indegree,int node)
{
	int n=numberVertices;
		for(int j=0;j<n;j++)
			if(Edge[node][j]!=0&&Edge[node][j]<MaxWeight)
				indegree[j]--;
	indegree[node]=MaxWeight;
}


template <class Type>
void MGraph<Type>::TopologicalOrder()
{
	int n=numberVertices;
	int *indegree=new int[n];
	for(int i=0;i<n;i++)
		indegree[i]=0;
	FindInDegree(indegree);
	
	for(i=0;i<n;i++)
		cout<<indegree[i]<<setw(3);
	cout<<endl;
	
	Stack<int> stk;
	for(i=0;i<n;i++)
		if(!indegree[i])
			stk.Push(i);//入度为零为结点入栈
	int count=0;//对输出的结点数计数
	
	cout<<"the order is:";
	while(!stk.IsEmpty())
	{
		int node=stk.Pop();
		cout<<node<<setw(6);
		count++;
		indegree[node]=MaxWeight;
		ChangeDegree(indegree,node);		
		for(i=0;i<n;i++)
			if(!indegree[i])
				stk.Push(i);
	}
	if(count!=n)cout<<"图中有回路";
}