/*圖實驗報告
姓名:劉議庠  學號:05180220    專業:05級  信息與計算科學
一．	實驗內容：建立一個圖，實現其存儲功能，并通過土求出其最小生成樹。
二．	實驗體會：
1.	本程序主要參照書本完成。
2.	本實驗采用鄰接表對圖進行存儲，建立一個頂點類，一個邊類，
每一個頂點定義一個邊指針，從而以鏈表的形式將于這個結點相連的邊連起來。
3.	圖的插入操作是關鍵，通個插入建立多條鏈表，以后的操作就于鏈表相似。
4.	該圖以深度遍歷的方式實現圖的遍歷。
5.	最小生成樹的建立比較難實現，其中含有多重循環，比較難實現，而書本
又是以鄰接距陣的形式的講解的，不易參考，故該函數比較混亂，其中還有不少問題。
6.	要實驗圖的遍歷和最小生成樹，必須保證該圖為連通圖，但由于時間有限，
該程序沒有實現判斷是否為連通圖的函數。
*/
//本程序采用鄰接表完成
//以頂點為表頭指針建立的多條鏈表很關鍵
//最小生成樹的最難實現(????????/?)
#include<iostream.h>
#include<fstream.h>
#include<string.h>
#include<iomanip.h>
#include<stdlib.h>
//static	int numvertex=0;//當前頂點數
const int defaultsize=10;//缺省頂點個數
class graph;//圖的前視定義
class edge//邊的定義
{
	friend class graph;
	int dest;//邊的一個頂點位置，即為數組中下標
	int cost;//權值
	edge *link;//將這些邊通過指針連接起來，就成了一個頂點發出的一條鏈
	edge(){}//！！！！！！！！！！！所以在頂點里定義了一個edge指針
	edge(int a,int b): dest(a),cost(b),link(NULL){}
	int operator !=(const edge &a)const{return dest!=a.dest;}//不考慮自循環這種情況
};
class vertex//頂點的定義
{
	friend class graph;
	friend class edge;
	char data;//頂點的名字
	edge *adj;//頂點里定義了一個edge指針
};
class graph
{
private:
	vertex *nodetable;//頂點表
	int maxvertex;//最大頂點數
	int numvertex;//當前頂點數
	int numedge;//當前邊數
public:
	graph(){}
	graph(int sz);
	~graph();
	int graphemphy()const{return numvertex==0;}//pan kong 
    int graphfull()const{return numvertex==maxvertex;}//pan man 
	int numberofvertex(){return numvertex;}
	int numberofedge(){return numedge;}
	char getvalue(int i)//取位置為i的頂點的值
	{return i>=0&&i<numvertex?nodetable[i].data:NULL;}
	int getvertexpos(const char &a);//找到a在圖中的位置，即相當于在數組中的下標值
	void insertvertex(const char &a);//在圖中插入一個頂點
	void removevertex(int v);//刪除一個頂點
	edge * insertedge(int v1,int v2,int weight);//插入一條邊
	void removevertex(int v1,int v2);//刪除一條邊
	int getweight(int v1,int v2);//得到一條邊上的權值
	int getfirstneighbor(int v);//取頂點v的第一個鄰接點
	int getnextneighbor(int v1,int v2);//取頂點v1的某鄰接點v2的下一個鄰接點
	//*****************************************
	void DFS();
	void DFS(int a,int b[]);//連通圖的深度搜索遍歷
	void prim();
};
graph::graph(int a=defaultsize):maxvertex(a),numedge(0),numvertex(0)//構造函數
{
   int n,e,k,j,weight;char name,tail,head;
   nodetable =new vertex[maxvertex];cout<<"請輸入插入頂點的個數!!"<<endl;
   cin>>n;//插入的頂點個數
   for(int i=0;i<n;i++)
   {cout<<"第  "<<i+1<<"條頂點的名字"<<endl;cin>>name;insertvertex(name);}
   cout<<"邊的條數"<<endl;cin>>e;//插入邊的條數
   for(i=0;i<e;i++)
   {cout<<"第"<<i+1<<"條邊"<<endl;
	   cin>>tail>>head;cout<<"請輸入權值!!!"<<endl;
	   cin>>weight;
	   k=getvertexpos(tail);j=getvertexpos(head);
	   insertedge(k,j,weight);
   }
}
graph::~graph()//析構函數
{
    for(int i=0;i<numvertex;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(const char&vertex)//找一個給定頂點的位置
{
	for(int i=0;i<numvertex;i++)
		if(nodetable[i].data==vertex) return i;
		return -1;
}
int graph::getfirstneighbor(int v)//給出一個頂點的位置,找其鏈表第一個結點(第一條邊)的位置
{
	if(v!=-1)
	{
		edge *p=nodetable[v].adj;
		if(p!=NULL) return p->dest;
	}
	return -1;
}
int graph::getnextneighbor(int v1,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;
}
int graph::getweight(int v1,int v2)//返回頂點為v1和v2的邊的權值
{
	if(v1!=-1&&v2!=-1)
	{
		edge *p=nodetable[v1].adj;//cout<<"進入權值"<<endl;
		while(p!=NULL)
		{//cout<<"進入權值"<<endl;
			if(p->dest==v2){return p->cost;}
			else p=p->link;
		}
	}
    return 0;
}
void graph::insertvertex(const char &a)//插入一個頂點
{//cout<<"進入插入頂點函數"<<endl;
	nodetable[numvertex].data=a;
	nodetable[numvertex].adj=NULL;
	numvertex++;
}
edge * graph::insertedge(int a,int b,int c)//插入一條邊,需在兩個頂點的鏈表中加入邊
{//cout<<"進入插入邊函數"<<endl;
//	cout<<a<<b<<endl;//*****************
    if(a<=numvertex&&b<=numvertex&&a>=0&&b>=0)
		{
            edge *pt=nodetable[a].adj;  edge *pr=nodetable[b].adj;
		    edge *pointer1=nodetable[a].adj;edge *pointer2=nodetable[b].adj;
			edge *p1=new edge;p1->dest=b;p1->cost=c;p1->link=NULL;
			edge *p2=new edge;p2->dest=a;p2->cost=c;p2->link=NULL;
			if(nodetable[a].adj==NULL)
			{
				nodetable[a].adj=p1;//cout<<"p  kong";
			}
			else
			{
				while(pointer1->link!=NULL)
				{
					pointer1=pointer1->link;//cout<<"p  buwei kong";
				}
				pointer1->link=p1;
			}
			if(nodetable[b].adj==NULL)
			{
				nodetable[b].adj=p2;//cout<<"p  kong";
			}
			else
			{
				while(pointer2->link!=NULL)
				{
					pointer2=pointer2->link;//cout<<"p  buwei kong";
				}
				pointer2->link=p1;
			}

		/*	{p=p1;}
		    int i=0,j=0;
		    edge *p1=new edge;//p1->dest=b;p1->cost=c;p1->link=NULL;
		     whilwhile(nodetable[a].adj!=NULL)
			 {i=1;nodetable[a].adj=nodetable[a].adj->link;cout<<"*****88888888888";}
			 nodetable[a].adj=p1;nodetable[a].adj->dest=b;nodetable[a].adj->cost=c;
			 nodetable[a].adj->link=NULL;
			 if(i==0){cout<<"頭指針不為空"<<endl;}//p=nodetable[a].adj;}
			 else  {cout<<"頭指針還原"<<endl;nodetable[a].adj=pt;}
		     //edge *pp=nodetable[b].adj;
		     edge *p2=new edge;
			 p2->dest=a;p2->cost=c;p2->link=NULL;
		      while(nodetable[b].adj!=NULL)
			 {j=1;nodetable[b].adj=nodetable[b].adj->link;cout<<"*****88888888888";}
			 nodetable[b].adj=p2;
			 if(j==0){cout<<"頭指針不為空"<<endl;}//p=nodetable[a].adj;}
			 else  {cout<<"頭指針還原"<<endl;nodetable[b].adj=pr;}
			  //if(nodetable[a].adj!=NULL)cout<<"jflskjf";*/
		}
	return nodetable[a].adj;
}
void graph::DFS()
{
	int *a=new int[numvertex];
	for(int i=0;i<numvertex;i++) a[i]=0;
	DFS(0,a);
	delete []a;
}
void graph::DFS(int a,int b[])
{
	cout<<getvalue(a)<<"    ";
	b[a]=1;
	int w=getfirstneighbor(a);
	while(w!=-1)
	{
		if(!b[w])DFS(w,b);
		w=getnextneighbor(a,w);
	}
}
void graph::prim()
{
	int *a=new int[numvertex];
	int *b=new int[numvertex];
	int v=0;int key=0;char *mintree=new char[numvertex];
    mintree[0]= nodetable[0].data;
	for(int e=1;e<numvertex;e++){mintree[e]='\0';}
	//edge *p=nodetable[v].adj;
	for(int i=0;i<numvertex;i++)//將兩個數組初始化
	{b[i]=0;}b[0]=-1;
	for(int j=1;j<numvertex;j++)
	{
    //	edge *p=nodetable[key].adj;
	     for(int i=0;i<numvertex;i++)//將兩個數組初始化
		 {a[i]=1000;}int tt=1;
    	while(nodetable[key].adj!=NULL)
		{
           a[nodetable[key].adj->dest]=getweight(key,nodetable[key].adj->dest);
		   cout<<"%%%"<<a[nodetable[key].adj->dest]<<"//以便理解最小二叉樹的生成!!"<<endl;
		   nodetable[key].adj=nodetable[key].adj->link;tt=0;
		}
	//	if(tt){}
		int t=1000;
     	for(i=1;i<numvertex;i++)
		{
	    	if(t>a[i]&&b[i]==0)
			{t=a[i];key=i;}
		}cout<<key<<endl;
	    if(key){mintree[j]= nodetable[key].data;b[key]=-1;}
	}
	for(int k=0;k<numvertex;k++)cout<<mintree[k]<<"    ";
}
void main()
{
	cout<<"首先建立一個圖!!!!"<<endl;
    	graph tu(100);
//	cout<<"這條邊的權值為    "<<tu.getweight(1,0);//得到一條邊的權值
//	cout<<"這條邊的權值為    "<<tu.getweight(0,2);
	
	cout<<endl;
	//插入邊函數連續的問題,lianbiao meiwancheng
	char a,b;
	do{
	    cout<<"              １．建立一個圖"<<endl;
	    cout<<"　　　　　　　２. 深度遍利"<<endl;
	    cout<<"　　　　　　　３．輸出邊的權值"<<endl;
	    cout<<"　　　　　　　４．顯示土圖的狀態"<<endl;
    	cout<<"　　　　　　　５．輸出最小生成樹(首先保證圖連通!!!)"<<endl;
    	cout<<"              ６．退出"<<endl;
 		int i;cin>>i;
		switch(i)
		{
        	case 1:
	          cout<<"圖已經建立!!!"<<endl;
			break;			
    	case 2:
			tu.DFS();//深度優先遍利
			cout<<endl;
			break;
    	case 3: 
			cout<<"請輸入要輸出的頂點值"<<endl;
			cin>>a;cin>>b;
			cout<<"這條邊的權值為    "<<tu.getweight(tu.getvertexpos(a),tu.getvertexpos(b));
			cout<<endl;
			break;
    	case 4:
			if(tu.graphemphy())cout<<"圖為空!!!        ";
			else cout<<"圖不為空!!!";
			if(tu.graphfull())cout<<"圖為滿!!!"<<endl;
			else cout<<"圖沒有滿!!!"<<endl;
				break;
    	case 5:
			tu.prim();//輸出最小生成樹
			cout<<endl;
            break;
    	case 6:
			exit(0);
			break;
		}
	}while(1);
}