graph.cpp

图邻接表的建立,深度优先遍历,.广度优先遍历,最小生成树,拓扑排序,单源点到其余各个顶点的最短路径等对图的操作!VC界面!

// Graph.cpp: implementation of the Graph class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "图的操作界面.h"
#include "Graph.h"

#include<queue>
using namespace std;

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////




//////////////////////////////////////////////////////////////////////////////////////////////////


Graph::Graph(int v,int e,CString ch1)   //边的个数和结点个数和各顶点
{
	numVertex=v;
	str=_T("");
	numEdge=e;
	ch=ch1;
	list=new LinkHead[v];        //初始化各值

	for(int i=0;i<v;i++) {list[i].Mark=0;list[i].next=0;}
}

bool Graph::InsertEdge(CString v,CString u,int Mark,int weight) //插入两个顶点的边和权值
{ 
	int i=-1;int j=-1;
	for(int k=0;k<n();k++)   //找两个顶点所在的数组的坐标
	{
		 if(v==ch[k]) i=k;
	     if(u==ch[k]) j=k;
	}
	if(i==-1 || j==-1) return 0;
	Edge current=new EdgeLink(i,j,weight);    //头插入建链
	current->next=list[i].next;
	list[i].next=current;
	if(Mark==0)                  //无向边要作两次的插入
	{
		current=new EdgeLink(i,j,weight);
	    current->next=list[j].next;
    	list[j].next=current;
	}
	return 1;
}

Graph::~Graph()           //析构函数
{
	if(list!=0)
	{
		for(int v=0;v<n();v++)    //先删除链
			while(list[v].next!=0)
			{
				Edge temp=list[v].next;
				list[v].next=list[v].next->next;
                delete temp;  
			}
			delete [] list; //再删除链头
	}
}

Edge Graph::first(int v) {return list[v].next;} //边的下一边

bool Graph::isEdge(Edge w) {return w!=0;}   //边是否存在

Edge Graph::next(Edge w)
{
	if(w!=0) return w->next;
	else return 0;
}

int Graph::v1(Edge w)    //边的第一个顶点
{
	return w->v1;
}

int Graph::v2(Edge w) {return w->v2;} //边的第二个顶点

int Graph::weight(int i,int j)    //两个顶点间的权值
{
	for(Edge curr=list[i].next;curr!=0;curr=curr->next)
		if(curr->v2==j) return curr->weight;
		return 32767;         //无连通时
}

int Graph::weight(Edge w)   //边的权值
{
	if(w!=0) return w->weight;
	else return w->weight;
}

void Graph::ReStart() //恢复数组的记录顶点是否被访问过
{
	for(int i=0;i<n();i++)
		list[i].Mark=0;
}

//**********************************************************************************************//

Graph1::Graph1(int v,int e,CString ch1)  //边的个数和顶点个数，和各顶点
{
	ch=ch1;
	str=_T("");
	numVertex=v;
	numEdge=e;
    matrix=new int[v*v];                    //初始化
	for(int i=0;i<v*v;i++) matrix[i]=32767;
	for( i=0;i<v;i++) matrix[i*v+i]=0;


}

Graph1::~Graph1()   //析构函数
{
	if(matrix!=0) delete [] matrix;
}

bool Graph1::InsertEdge(CString v,CString u,int weight,int Mark) //插入两个顶点的边和权值
{
	int i=-1;int j=-1;
	for(int k=0;k<numVertex;k++)   //找两个顶点所在的数组的坐标
	{
		 if(v==ch[k]) i=k;
	     if(u==ch[k]) j=k;
	}
	if(i==-1||j==-1) return 0;
	matrix[i*n()+j]=weight;       //是否是有向边
	if(Mark==0) matrix[j*n()+i]=weight;
	return 1;
}


Edge1 Graph1::first(int v)
{
	int stop=(v+1)*numVertex;                 //在行里面寻找
	for(int pos=v*numVertex;pos<stop;pos++)
		if(pos==v*numVertex+v) continue;
		else if(matrix[pos]!=32767)  return &matrix[pos];   //找到返回
	return 0;
}

bool Graph1::isEdge(Edge1 w)  //边是否存在
{
	return w!=0;
}

Edge1 Graph1::next(Edge1 w) //边的下一边
{
	int stop=(v1(w)+1)*numVertex;
	for(int pos=(w-matrix)+1;pos<stop;pos++)
		if(pos==v1(w)) continue;                        //（U，U）有它用不算
		else if(matrix[pos]!=32767) return &matrix[pos];
	return 0;
}

int Graph1::v1(Edge1 w)//边的第一个顶点
{
	return (w-matrix)/numVertex;
}

int Graph1::v2(Edge1 w) //边的第二个顶点
{
	return (w-matrix)%numVertex;
}

int Graph1::weight(Edge1 w)  //边的权值，则边的两个顶点的坐标的值
{
	return matrix[(w-matrix)/numVertex*n()+(w-matrix)%numVertex];
}


//**********************************************************************************************//

CString Graph::TopSort()
{
	
	int *unsort=new int[n()];  //申请一个数组，用来记录
	CString topsort;          //定义一个串，用来返回
	int top=-1;              //用上面的数组来作栈

	for(int i=0;i<n();i++) unsort[i]=0;  //初始化
	for(i=0;i<n();i++)
		for(Edge w=first(i);isEdge(w);w=next(w))  //计算直接前驱的个数
			unsort[v2(w)]++;
	for(i=0;i<n();i++)
		if(unsort[i]==0)    //把数组值为0的元素压栈
		{ 
			  unsort[i]=top;    
			  top=i;
		}
	while(top!=-1)        //数组值为0的元素出栈
	{
		int v=top;
		top=unsort[top];
		topsort+=ch[v];
        topsort+=" ";
		for(Edge w=first(v);isEdge(w);w=next(w))
		{
			unsort[v2(w)]--;   //直接后继顶点的值减一
			if(!unsort[v2(w)])
			{
				unsort[v2(w)]=top;
				top=v2(w);
			}
		}
	}
	ReStart();
	return topsort;
}

CString Graph::BFS(int start)  //广度优先遍历
{  
	ReStart();
	queue<int> Q;
	Q.push(start);
	CString Bfs="";//定义一个串，以返回串
	list[start].Mark=1;  //记录访问过的顶点
	while(!Q.empty())   //进行遍历直到栈空为止；
	{
		int v=Q.front();
		Q.pop();               //出栈

	   Bfs+=ch[v];
	   Bfs+=" ";
 
		for(Edge w=first(v);isEdge(w);w=next(w))
			if(list[v2(w)].Mark==0)
			{
				list[v2(w)].Mark=1;
			    Q.push(v2(w));            //压栈
			}
	}
	ReStart();   ////恢复邻接表的用来记录顶点是否被访问的数（则将链头组MARK的1改为0）          
	return Bfs;
}


CString Graph::DFS(int v)    //深度优先遍历
{
	list[v].Mark=1;
	str+=ch[v];
	str+=" ";
	for(Edge w=first(v);isEdge(w);w=next(w))
	   if(list[v2(w)].Mark==0)
		  DFS(v2(w));
	return str;
}

//****************************************************************************************//

int Graph1::minVertex(int *D)   //在D数组中找值最小的且没有访问过的顶点
{
	int v;
	for(int i=0;i<n();i++)
		if(matrix[i*n()+i]==0) {v=i;break;}
	for( i=v+1;i<n();i++)
		if((matrix[i*n()+i]==0)&&(D[i]<D[v])) v=i;
	return v;
}

CString Graph1::Prim(CString c)  //最小生成树
{
    int s=0;
	for(;s<n();s++)
		if(c==ch[s]) break;
	if((s==n())&& (c!=ch[s-1])) return str="";
	ReStart();
	int *dist=new int[n()];    //申请一个数组
	int *V=new int[n()];

	for(int i=0;i<n();i++)//初始化dist数组，所有顶点都属于V-TV集合
		dist[i]=32767;

	 dist[s]=0; //为了将s加入生成树中作为“种子”，把s的dist值设为最小

	for(i=0;i<n();i++) //循环n次，每次往T中加入一个新顶点
	{
		int v=minVertex(dist);                             //选择V-TV中dist值最小的顶点v
		if(dist[v]==32767) return str="有无连通的点!";     //有无法到达的顶点

	    matrix[v*n()+v]=1;

	    if(v!=s) matrix[ V[v]*n()+v]=0-matrix[ V[v]*n()+v]; //把边（V[v],v）在原矩阵中作标记
		                                                    //在矩阵中生成树，把原来的权值变
		                                                    //为负，过后再恢复
		                                                

	    for(Edge1 w=first(v);isEdge(w);w=next(w))   //重新计算V-TV中的顶点到TV跌顶点的边的最
			                                        //小权
		if(dist[v2(w)]>weight(w))                   
		{
			dist[v2(w)]=weight(w);
		    V[v2(w)]=v;
		}
	}
   printTree(s,n()); //打印树，以线表形式打印；
   CString str1;
   str1=str;
   str="";
   return str1;
}


void Graph1::printTree(int s,int h)         //打印树函数，类似于深度遍历
{
                                            //h为需要打印的“——”个数
	for(int k=0;k<n()-h;k++) {str+="  ";str+="  ";} //实际上是共读入两个空格

	for(k=0; k<h; k++)       str+="__";

	str+=ch[s];
	str+="\r\n";                        //读入换行回车符
    h--;                                //孩子的深度一样，“——”数一样

	for(Edge1 w=first(s);isEdge(w);w=next(w))  //如果在与结点S有边关系的结点在树中则递归
		if(matrix[v1(w)*n()+v2(w)]<=0)         //权值小于0的为树中的边
		{
			matrix[v1(w)*n()+v2(w)]=0-matrix[v1(w)*n()+v2(w)];
		    printTree( v2(w) ,h);
		}
}

int* Graph1::Dijkstra(CString c)    //求V到其余顶点的最短路径
{

    int v=0;
	for(;v<n();v++)
		if(c==ch[v]) break;
	if( (v==n()) && (c!=ch[v-1]) ) return 0;

	int *dist=new int[n()];
	for(int i=0;i<n();i++) dist[i]=32767;  //初始化数组，各点不连通

	dist[v]=0;       //V已访问

	for(i=0;i<n();i++)
	{
		int u=minVertex(dist);
		matrix[u*n()+u]=1;           //访问U，此时dist[u]为v到u的最短路径的长度

  //存在无法达到的顶点；

		for(Edge1 w=first(u);isEdge(w);w=next(w)) //重新计算数组
			if(dist[v2(w)]>(dist[u]+weight(w)))
               dist[v2(w)]=dist[u]+weight(w);
	}
	ReStart();
	return dist;    //返回数组
}

void Graph1::ReStart()
{
	for(int i=0;i<n();i++)
		matrix[i*n()+i]=0;
}


//**********************************************************************************************//