?? setmaxvertices.cpp
字號:
#include <iostream>
#include <String>
#include <time.h>
using namespace std;
//#define DEBUG //add by bighead
#define DEBUG_TIME
#define LOOPS 10000
#include "MinSpanTree.cpp"
#include "MinHeap.cpp"
#include "UFSets.cpp"
#include "SeqList.cpp"
const int MaxNumEdges = 50;//最大邊數
#ifndef SetMaxVertices
#define SetMaxVertices
const int MaxNumVertices=10; //最大頂點數
#endif
//using std::istream;
template <class NameType, class DistType> class Graph { //圖的類定義
private:
SeqList<NameType> VerticesList;//( MaxNumVertices ); //頂點表
DistType Edge[MaxNumVertices][MaxNumVertices]; //鄰接矩陣
int CurrentEdges; //當前邊數
int FindVertex ( SeqList<NameType> & L, const NameType & vertex )
{ return L.Find (vertex); } //在頂點表L中搜索頂點vertex
int GetVertexPos ( const NameType & vertex )
{ return FindVertex (VerticesList, vertex ); }
//給出頂點vertex在圖中的位置
public:
Graph ( const int sz=MaxNumEdges ); //構造函數
int GraphEmpty ( ) const { return VerticesList.IsEmpty ( ); } //判圖空否
int GraphFull ( ) const { return VerticesList.IsFull ( ) || CurrentEdges ==MaxNumEdges; }
int NumberOfVertices ( ) { return VerticesList.Length(); } //返回當前頂點數
int NumberOfEdges ( ) { return CurrentEdges; } //返回當前邊數
NameType GetValue ( const int i ) //取頂點i的值, i不合理則返回空
{ return VerticesList.Get(i); }
DistType GetWeight ( const int v1, const int v2 ); //給出以頂點v1和v2為兩端點的邊上的權值
int GetFirstNeighbor ( const int v ); //給出頂點位置為v的第一個鄰接頂點的位置
int GetNextNeighbor ( const int v1, const int v2 ); //給出頂點位置v1的某鄰接頂點v2的下一個鄰接頂點
void InsertVertex ( NameType & vertex ); //插入一個頂點vertex, 該頂點沒有入邊
void InsertEdge ( const int v1, const int v2, DistType weight ); //插入一條邊(v1, v2), 該邊上的權值為weight
void RemoveVertex ( const int v ); //在圖中刪去頂點vertex和所有與它相關聯的邊
void RemoveEdge ( const int v1, const int v2 ); //在圖中刪去邊(v1,v2)
void Prim ( MinSpanTree &T ) ;
void Kruskal ( MinSpanTree &T );
template <class NameType2, class DistType2>
friend istream& operator >>(istream&, Graph<NameType2, DistType2>& );
template <class NameType2, class DistType2>
friend ostream& operator <<(ostream&, Graph<NameType2, DistType2>& );
};
template <class NameType, class DistType> Graph<NameType, DistType>::Graph (
const int sz ) {
//構造函數
for ( int i=0; i<sz; i++ ) //鄰接矩陣初始化
for ( int j=0; j<sz; j++ ) Edge[i][j] = 0;
CurrentEdges = 0; //圖中當前邊數初始化
#ifdef DEBUG
cout << "Graph construct!" << endl;
#endif
};
template <class NameType, class DistType>
DistType Graph<NameType, DistType>::GetWeight ( const int v1, const int v2 )
{
//給出以頂點v1和v2為兩端點的邊上的權值
if ( v1 != -1 && v2 != -1 ) return Edge[v1][v2];
else return 0; //帶權圖中權值為0, 表示無權值
};
template <class NameType, class DistType>
int Graph<NameType, DistType>::GetFirstNeighbor ( const int v ) {
//給出頂點位置為v的第一個鄰接頂點的位置, 如果找不到, 則函數返回-1。
if ( v != -1 ) {
for ( int col=0; col<VerticesList.Length(); col++ )
if ( Edge[v][col] > 0 ) return col;
}
return -1;
};
template <class NameType, class DistType>
int Graph<NameType, DistType>::GetNextNeighbor ( const int v1, const int v2
) {
//給出頂點v1的某鄰接頂點v2的下一個鄰接頂點
if ( v1 != -1 && v2 != -1 )
{
for ( int col=v2+1; col<VerticesList.Length(); col++ )
if ( Edge[v1][col] > 0 ) return col;
}
return -1;
};
template <class NameType, class DistType>
void Graph<NameType, DistType>::InsertVertex ( NameType & vertex ) //插入一個頂點vertex, 該頂點沒有入邊
{
assert (VerticesList.Insert ( vertex, VerticesList.Length() ));
};
template <class NameType, class DistType>
void Graph<NameType, DistType>:: InsertEdge ( const int v1, const int v2,
DistType weight ) //插入一條邊(v1, v2), 該邊上的權值為weight
{
CurrentEdges++;
Edge[v1][v2]=weight;
Edge[v2][v1]=weight;
};
template <class NameType,class DistType>
void Graph<NameType, DistType>::Prim ( MinSpanTree &T ) {
int NumVertices = VerticesList.Length(); //圖中頂點數
if (NumVertices<=0) return;
int *lowcost,*nearvex;
lowcost = new int[NumVertices]; //創建輔助數組
nearvex = new int[NumVertices]; //創建輔助數組TV
for ( int i=1; i<NumVertices; i++ )
{
if (Edge[0][i]==0)
lowcost[i]=MAXINT;
else
lowcost[i] = Edge[0][i];
nearvex[i] = 0; //頂點0到各邊的代價及最短帶權路徑
}
nearvex[0] = -1; //頂點0加到生成樹頂點集合, 用-1表示
for (int i=1; i<NumVertices; i++ )
{ //循環-1次, 加入n-1條邊
int min = MAXINT; int v = 0; //求生成樹外頂點到生成樹內頂點具有最小權值的邊
for ( int j=0; j<NumVertices; j++ ) //確定當前具最小權值的邊及頂點位置
if ( nearvex[j] != -1 && lowcost[j] < min )
{
v = j;
min = lowcost[j];
}
if ( v )
{ // v==0表示再也找不到要求的頂點了
T.addEdge(nearvex[v],v,lowcost[v]);
nearvex[v] = -1; //加入生成樹頂點集合
for (int j=1; j<NumVertices; j++ )
if ( (nearvex[j] != -1) && (Edge[v][j]!=0) && (Edge[v][j] < lowcost[j]) )
{
lowcost[j] = Edge[v][j];
nearvex[j] = v;
} //修改
}
}
};
template <class NameType, class DistType>
void Graph< NameType, DistType>::Kruskal ( MinSpanTree &T )
{ //克魯斯卡爾算法
MSTEdgeNode e;
MinHeap<MSTEdgeNode> H (CurrentEdges ); //最小堆
int NumVertices = VerticesList.Length(); //圖中頂點個數
#ifdef DEBUG
cout << "Kruskal is in use!" <<endl;
#endif
UFSets F (NumVertices); //連通分量
for ( int u=0; u<NumVertices; u++ ) //建立最小堆的數據
for ( int v=u+1; v<NumVertices; v++ )
if ( Edge[u][v] != 0 ) { //插入新邊值結點到最小堆中
e.tail=u;e.head=v;e.key=Edge[u][v];
H.Insert (e);
}
int count = 1; //生成樹邊計數
while ( count < NumVertices ) { //反復執行, 取n-1條邊
H.RemoveMin (e ); //從最小堆中退出具最小權值的邊
int u = F.Find ( e.tail );
int v = F.Find ( e.head ); //取兩頂點所在集合的根
if ( u != v ) { //不是同一集合, 說明不連通
F.Union ( u, v );
T.addEdge(e.tail,e.head,e.key);
count++; //合并, 連通它們, 該邊加入生成樹
}
}
};
template <class NameType, class DistType>
istream& operator >>(istream& is, Graph<NameType,DistType>& g)
{
int n,e,k,j;
NameType head,tail,name;
DistType weight;
cout << "Input Vertices num = ";
is >> n; //輸入頂點個數
cout << "Vertices Name = " << endl;
for ( int i=0; i<n; i++)
{
is >> name;
g.InsertVertex ( name );
} //依次輸入頂點, 插入圖中
cout << "Input Edges num = ";
is >> e; //輸入邊數
cout << "Edge = <VerticsTail,VerticeHead,Weight>" << endl;
for (int i=0; i<e; i++) { //依次輸入邊信息
is >> tail >> head >> weight; //輸入各邊
k = g.GetVertexPos ( tail );
j = g.GetVertexPos ( head ); //取兩頂點位置
g.InsertEdge ( k, j, weight ); //插入圖中
}
return is;
}
template <class NameType, class DistType>
ostream& operator <<(ostream& strm, Graph<NameType,DistType>& g)
{
int edgeNum,vecticesNum;
edgeNum = g.NumberOfEdges();
vecticesNum = g.NumberOfVertices();
strm << "All the Vectics(" << vecticesNum << ") are below: <index,name>\n";
for(int i=0;i < vecticesNum;i++)
strm << i <<":"<<g.GetValue(i)<<"\t";
strm << "\nAll the edges(" << edgeNum << ") are below:<head,tail,weight>\n";
for(int i=0;i < vecticesNum;i++)
for(int j=i+1;j < vecticesNum;j++)
if(g.GetWeight(i,j) != 0)
strm << "<" << i <<", "<<j<<", "<<g.GetWeight(i,j)<<">\t";
return strm;
}
main()
{
char p;
#ifdef DEBUG_TIME
clock_t start,end;
#endif
int times = 3;
while(times)
{
cout << "\nPlease make your choice! 1, 2, 3 or 4" << endl;
cout << "1:Demo 1 " << endl;
cout << "2:Demo 2 " << endl;
cout << "3:Construct the graph yourself! " <<endl;
cout << "4:Quit " << endl;
cout << "Type q or Q to exit!" << endl;
cin >> &p;
switch (p)
{
case '1':
{
cout << "\nChoice 1:This is in Demo 1 ! "<< endl;
string iVetStr[7]={"0","1","2","3","4","5","6"};
Graph<string,int> iGraph(7);
for(int i=0;i<7;i++)
iGraph.InsertVertex(iVetStr[i]);
iGraph.InsertEdge(0,1,28);
iGraph.InsertEdge(0,5,10);
iGraph.InsertEdge(1,2,16);
iGraph.InsertEdge(1,6,14);
iGraph.InsertEdge(2,3,12);
iGraph.InsertEdge(3,4,22);
iGraph.InsertEdge(3,6,18);
iGraph.InsertEdge(4,6,24);
iGraph.InsertEdge(5,4,25);
//display the graph
cout << iGraph <<endl;
#ifdef DEBUG_TIME
start = clock();//t.start();
#endif
MinSpanTree iMinSpanTreeK(iGraph.NumberOfVertices());
iGraph.Kruskal(iMinSpanTreeK);
for(int i=0;i < LOOPS;i++)
{
MinSpanTree iMinSpanTreeK_tmp(iGraph.NumberOfVertices());
iGraph.Kruskal(iMinSpanTreeK_tmp);
}
#ifdef DEBUG_TIME
end = clock();
cout << "start:" << start << " end:" << end << endl;
cout << "Loops = " <<LOOPS<<" Kruskal Used Time: (ms) " << (end - start) << endl;
#endif
cout<<iMinSpanTreeK<<endl;
#ifdef DEBUG_TIME
start = clock();//t.start();
#endif
MinSpanTree iMinSpanTreeP(iGraph.NumberOfVertices());
iGraph.Prim(iMinSpanTreeP);
for(int i=0;i < LOOPS;i++)
{
MinSpanTree iMinSpanTreeP_tmp(iGraph.NumberOfVertices());
iGraph.Prim(iMinSpanTreeP_tmp);
}
#ifdef DEBUG_TIME
end = clock();
cout << "start:" << start << " end:" << end << endl;
cout << "Loops = " <<LOOPS<<" Prim Used Time: (ms) " << (end - start) << endl;
#endif
cout<<iMinSpanTreeP<<endl;
}
break;
case '2':
cout << "\nchoice 2:This is in Demo 2" << endl;
{
string iVetStr[9]={"A","B","C","D","E","F","G","H","I"};
Graph<string,int> iGraph(9);
for(int i=0;i<9;i++)
iGraph.InsertVertex(iVetStr[i]);
iGraph.InsertEdge(0,1,28);
iGraph.InsertEdge(0,5,10);
iGraph.InsertEdge(1,2,16);
iGraph.InsertEdge(1,6,14);
iGraph.InsertEdge(2,3,12);
iGraph.InsertEdge(3,4,22);
iGraph.InsertEdge(3,6,18);
iGraph.InsertEdge(4,6,24);
iGraph.InsertEdge(5,4,25);
iGraph.InsertEdge(5,7,2);
iGraph.InsertEdge(5,6,15);
iGraph.InsertEdge(6,8,21);
iGraph.InsertEdge(8,4,15);
iGraph.InsertEdge(7,3,25);
//display the graph
cout << iGraph <<endl;
#ifdef DEBUG_TIME
start = clock();//t.start();
#endif
MinSpanTree iMinSpanTreeK(iGraph.NumberOfVertices());
iGraph.Kruskal(iMinSpanTreeK);
for(int i=0;i < LOOPS;i++)
{
MinSpanTree iMinSpanTreeK_tmp(iGraph.NumberOfVertices());
iGraph.Kruskal(iMinSpanTreeK_tmp);
}
#ifdef DEBUG_TIME
end = clock();
cout << "start:" << start << " end:" << end << endl;
cout << "Loops = " <<LOOPS<<" Kruskal Used Time: (ms) " << (end - start) << endl;
#endif
cout<<iMinSpanTreeK<<endl;
#ifdef DEBUG_TIME
start = clock();//t.start();
#endif
MinSpanTree iMinSpanTreeP(iGraph.NumberOfVertices());
iGraph.Prim(iMinSpanTreeP);
for(int i=0;i < LOOPS;i++)
{
MinSpanTree iMinSpanTreeP_tmp(iGraph.NumberOfVertices());
iGraph.Prim(iMinSpanTreeP_tmp);
}
#ifdef DEBUG_TIME
end = clock();
cout << "start:" << start << " end:" << end << endl;
cout << "Loops = " <<LOOPS<<" Prim Used Time: (ms) " << (end - start) << endl;
#endif
cout<<iMinSpanTreeP<<endl;
}
break;
case '3':
cout << "\nChoice 3:Construct the Graph yourself! "<<endl;
{
cout << "Begin MaxVertices = " << MaxNumVertices << endl;
Graph<string,int> iGraph(MaxNumVertices);
cin >> iGraph;
cout << iGraph <<endl;
#ifdef DEBUG_TIME
start = clock();
#endif
MinSpanTree iMinSpanTreeK(MaxNumVertices);
iGraph.Kruskal(iMinSpanTreeK);
for(int i=0;i < LOOPS;i++)
{
MinSpanTree iMinSpanTreeK_tmp(MaxNumVertices);
iGraph.Kruskal(iMinSpanTreeK_tmp);
}
#ifdef DEBUG_TIME
end = clock();
cout << "start:" << start << " end:" << end << endl;
cout << "Loops = " <<LOOPS<<" Kruskal Used Time: (ms) " << (end - start) << endl;
#endif
cout<<iMinSpanTreeK<<endl;
#ifdef DEBUG_TIME
start = clock();
#endif
MinSpanTree iMinSpanTreeP(MaxNumVertices);
iGraph.Prim(iMinSpanTreeP);
for(int i=0;i < LOOPS;i++)
{
MinSpanTree iMinSpanTreeP_tmp(MaxNumVertices);
iGraph.Prim(iMinSpanTreeP_tmp);
}
#ifdef DEBUG_TIME
end = clock();
cout << "start:" << start << " end:" << end << endl;
cout << "Loops = " <<LOOPS<<" Prim Used Time: (ms) " << (end - start) << endl;
#endif
cout<<iMinSpanTreeP<<endl;
}
break;
case '4':
return 1;
break;
case 'q':
return 1;
break;
case 'Q':
return 1;
break;
default:
times--;
cout << "\nare you kidding? Please input correctly! "<< times <<" times left!"<<endl;
break;
}
}
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -