graph.cpp

数据结构实验课中的所有实验程序

#include "stdafx.h"
#include "Graph.h"
#include "string.h"
#include "fstream.h"

Graph::Graph (const int sz=DefaultSize):NumVertices(0),MaxNumVertices(sz),NumEdges(0)
{
	int nn, e, k, j;  
	char name[50], tail[50], head[50],inf[500]; 
    int weight;
    NodeTable=new Vertex[MaxNumVertices];                     //创建顶点表
    cin>>nn;			                                      //输入顶点个数
    for(int i=0;i<nn;i++)                                     //输入各顶点信息
	{ 
		cin>>name;  
		InsertVertex(name);
		cin>>inf;
		InsertInfo(inf);
	}
    cin>>e;                                                   //输入边条数
    for (i=0;i<e;i++) 
	{                                                         //逐条边输入
       cin>>tail>>head>>weight;
       k=GetVertexPos(tail);
       j=GetVertexPos(head);
       InsertEdge (k,j,weight);
	   InsertEdge (j,k,weight);
	} 
}

Graph::~Graph( ) 
{
    for (int i=0;i<NumVertices;i++) 
	{
       Edge *p=NodeTable[i].adj;
       while(p!=NULL) 
	   {                                                     //逐条边释放
            NodeTable[i].adj=p->link;
			delete p; 
            p=NodeTable[i].adj; 
	   }
	}
       delete [] NodeTable;                                  //释放顶点表
}
int Graph::GetVertexPos(char vertex[]) 
{

    for (int i=0;i<NumVertices;i++)
       if (strcmp(NodeTable[i].data,vertex)==0) return i;
    return -1;
}
int Graph::GetFirstNeighbor(const int v)
{
    
   if(v!=-1) 
   {		                                                //若顶点存在
       Edge *p = NodeTable[v].adj;
       if(p!= NULL) 
		   return p->dest;  
   } 
    return -1;                                              //若顶点不存在
}
int Graph:: GetNextNeighbor(const int v1, const int v2) 
{

    if ( v1 != -1 )
	{
       Edge *p = NodeTable[v1].adj;    
	   while ( p != NULL ) 
	   {
           if (p->dest==v2&&p->link!=NULL)
	            return p->link->dest;    
                                                            //返回下一个邻接顶点在邻接表中的位置
	       else p = p->link;
       }
    }
    return -1;                                              //没有查到下一个邻接顶点返回-1
}

int Graph::GetWeight (const int v1, const int v2)//得到权重
{
	if(v1==v2) return 0;
    else if ( v1 != -1 && v2 != -1 ) 
	{
       Edge *p=NodeTable[v1].adj;
       while(p!=NULL) 
	   {
	        if (p->dest==v2) return p->cost;
            else p=p->link;
       }
    }
    return 100000;
}
void Graph::InsertVertex (const char vertex[])
{
	strcpy(NodeTable[NumVertices].data,vertex);
	
}

void Graph::InsertInfo(const char inf[])//插入信息
{
	strcpy(NodeTable[NumVertices].info,inf);
	NodeTable[NumVertices].adj=NULL;
	NumVertices++;
}

void Graph::SearchInfo(char name[])//查询顶点信息
{
    for(int i=0;i<NumVertices;i++)
	{
		if(strcmp(NodeTable[i].data,name)==0)
		{
		  cout<<"The information about"<<name<<"is:";
          cout<<NodeTable[i].info<<endl;
		  return ;
		}
	}
	cout<<"Sorry! It's not exist!"<<endl;
}


void Graph::InsertEdge(const int v1, const int v2, const int weight)//插入边
{
	Edge *p=new Edge;
	p->dest=v2;
	p->cost=weight;
	p->link=NodeTable[v1].adj;
	NodeTable[v1].adj=p;
	NumEdges++;
}

void Graph::load()             //读取文件
{
   	NumVertices=0;
	NumEdges=0;
    fstream inputf;
	inputf.open("data.dat",ios::in);
	if(!inputf)
	{
		cout<<"Loading Error!"<<endl;
		return;
	}
	int vn;
	int en;
	inputf>>vn;
	MaxNumVertices=vn;
	NodeTable=new Vertex[vn];
	for(int i=0;i<vn;i++)
	{
		char name[50];
		inputf>>name;
		InsertVertex(name);
		char inf[500];
		inputf>>inf;
		InsertInfo(inf);
	}
	inputf>>en;
	for(int j=0;j<en;j++)
	{
		int in1,in2;
		char v1[50],v2[50];
		int length;
		inputf>>v1>>v2>>length;
		in1=GetVertexPos(v1);
        in2=GetVertexPos(v2);
		InsertEdge(in1,in2,length);
		InsertEdge(in2,in1,length);
	}
	inputf.close();
}
void Graph::DFS()              //深度有限算法
{			
    int *visited= new int [NumEdges];                              //创建数组 visited
    for (int i=0;i<NumEdges;i++) visited [i]=0;                                                             //访问标记数组 visited 初始化	
    DFS (0,visited);	  				
    delete []visited;                                              //释放 visited 
}
void Graph::DFS(const int v, int visited [])
{	
    cout<<GetValue(v)<<"\t\t";                                    //访问顶点 v
    visited[v]=1;		                                          //顶点 v 作访问标记
    int w=GetFirstNeighbor(v);	  
                                                                  //取 v 的第一个邻接顶点 w
	while(w!=-1) 
	{	                                                          //若邻接顶点 w 存在
        if(!visited[w])  DFS(w,visited);
                                                                  //若顶点 w 未访问过, 递归访问顶点 w
        w=GetNextNeighbor(v,w);
                                                                  //取顶点 v 的排在 w 后面的下一个邻接顶点
	}
}
void Graph::Components()                   //连通分量
{			
    int *visited=new int[NumVertices];                          //创建visited	
    for (int i=0;i<NumVertices;i++)
       visited[i]=0;	                                        //visited 初始化
    for (i=0;i<NumVertices;i++)			
		if ( !visited[i] ) 
		{	                                                    //检测所有顶点是否访问过
	          DFS(i,visited);                                   //从未访问的顶点出发访问
	          //OutputNewComponent();
	                                                            //输出一个连通分量
        }
       delete [ ] visited;                                      //释放visited
}
void Graph::Prim(MinSpanTree &T)            //最小生成树
{
	T.max=0;
    int NumVer=NumVertices;	                           //图中顶点数
    int *lowcost=new int[NumVer];			
    int *nearvex=new int[NumVer];			
    for (int i=1; i<NumVer; i++) 
	{
        lowcost[i]=GetWeight(0,i);                    //顶点0到各边的代价
        nearvex[i]=0;	                              //及最短带权路径
	}
    nearvex[0]=-1;                                   //顶点0加到生成树顶点集合                                    //生成树边值数组存放指针
    MSTEdgeNode e;                                     //最小生成树结点辅助单
    for(i=0;i<NumVer;i++) 
	{                                                  //循环n-1次, 加入n-1条边			
       int min=100000; 
	   int v=0;		
       for(int j=0;j<NumVer;j++)		
           if (nearvex[j]!=-1&&lowcost[j]<min)
		   { 
			   v=j;
			   min=lowcost[j]; 
		   }
                                                   //求生成树外顶点到生成树内顶点具有最小
                                                   //权值的边, v是当前具最小权值的边的位置
	           if(v) 
			   {                                       //v==0表示再也找不到要求的顶点了
       	                                               //向生成树边值数组内存放
		        e.tail=nearvex[v];  
		        e.head=v;
		        e.cost=lowcost[v];   
		        T.Insert(e);                         //选出的边加入生成树
		        nearvex[v]=-1;                      //作该边已加入生成树标记
		        for (j=1;j<NumVer;j++)
                   if (nearvex[j]!=-1&&GetWeight(v,j)<lowcost[j])
				   {                                               //需要修改
                     lowcost[j]=GetWeight(v,j);
                     nearvex[j]=v;
				   }
		   }
    }
	cout<<T.max<<endl;
}
void Graph::ShortestPath (int n,int v)     //最短路径
{
	int NumVer=NumVertices;	 		
    for(int i=0;i<NumVer;i++)
	{				
        dist[i]=GetWeight(v,i);    
        S[i]=0;					
        if(i!=v&&dist[i]<99999) 
			path[i]=v;
        else path[i]=-1;	        	
    }    
    S[v]=1;
    dist[v]=0;	                                               //选择当前不在集合S中具有最短路径的顶点u
    for(i=0;i<NumVer-1;i++) 
	{			
        int min=99999;
		int u=v;
        for (int j=0;j<NumVer;j++)		
	    if (!S[j]&&dist[j]<min) 
		{ 
			u=j;   
			min=dist[j]; 
		}
        S[u]=1;	                                              //将顶点u加入集合S
        for(int w=0;w<NumVer;w++)                             //修改 
	     if (!S[w] &&GetWeight(u,w)<99999&& dist[u]+GetWeight(u,w)<dist[w]) 
		 {
	       dist[w]=dist[u]+GetWeight(u,w); 
	       path[w]=u;
		 }    
	}
	int nn=n;
	cout<<"Your best route is:"<<endl;
	while(nn!=v)
	{
        cout<<NodeTable[nn].data<<endl;
		cout<<"↓"<<endl;
		nn=path[nn];
	}
	cout<<NodeTable[nn].data<<endl;
	cout<<"This route length is:";
	cout<<dist[n]<<endl;
} 	
void Graph::SP(char n1[],char n2[])             //两点间最短距离
{ 
	int m1=0,m2=0;
	for(int i=0;i<NumVertices;i++)
	{
		if(strcmp(NodeTable[i].data,n1)==0) 
		{
			m1=i;
			break;
		}
			if(i==NumVertices-1) 
		{
			cout<<"NO"<<n1<<"!"<<endl;
			break;
		}
	}
    for(int j=0;j<NumVertices;j++)
	{
		if(strcmp(NodeTable[j].data,n2)==0)  
		{
			m2=j;
			break;
		}
		if(j==NumVertices-1) 
		{
			cout<<"NO"<<n2<<"!"<<endl;
			break;
		}
	}
	if(m1==m2) cout<<"From"<<n1<<"to"<<n2<<"is 0 kilometer forever!"<<endl;
	else ShortestPath(m1,m2);
}