main.h:
#include <iostream>
#include <queue>
#define DefaultSize 10
#define maxWeight -1
using namespace std;
template<typename T,typename E>
struct Edge
{
int dest;
E cost;
Edge<T,E> *link;
Edge(int d=0,int c=0):dest(d),cost(c),link(NULL){}
};
template<typename T,typename E>
struct Vertex
{
T data;
Edge<T,E> *adj;
};
template<typename T,typename E>
class Base
{
public:
virtual T getValue(int i)=0;
virtual E getWeight(int v1,int v2)=0;
virtual bool insertVertex(const T& vertex)=0;
virtual bool insertEdge(const T& l,const T& r,E cost)=0;
virtual void Show()=0;
virtual bool removeEdge(int v1,int v2)=0;
virtual bool removeVertex(int v)=0;
virtual int getFirstNeighbor(int v)=0;
virtual int NumberOfEdge()=0;
virtual int getNextNeighbor(int v,int w)=0;
};
template<typename T,typename E>
class Graphlnk:public Base<T,E>
{
public:
Graphlnk(int sz=DefaultSize)
{
numVertices=0;
maxVertices=DefaultSize;
numEgde=0;
NodeTable = new Vertex<T,E>[sz];
for(int i=0;i<sz;i++)
{
NodeTable[i].adj=NULL;
}
}
int NumberOfEdge()
{
return numEgde;
}
int getFirstNeighbor(int v)
{
if(v<0||v>=numVertices)return -1;
Edge<T,E> *p = NodeTable[v].adj;
if(p!=NULL)
{
return p->dest;
}
return -1;
}
int getNextNeighbor(int v,int w)
{
if(v<0 || v>=numVertices || w<0 || w>=numVertices)
{
return -1;
}
Edge<T,E> *p = NodeTable[v].adj;
while(p!=NULL)
{
if(p->dest == w)
{
if(p->link!=NULL)
return p->link->dest;
}
p = p->link;
}
return -1;
}
bool removeVertex(int v)
{
Edge<T,E> *p = NodeTable[v].adj;
while(p!=NULL)
{
removeEdge(v,p->dest);
p=p->link;
}
NodeTable[v].data = NodeTable[numVertices-1].data;
NodeTable[v].adj = NodeTable[numVertices-1].adj;
p = NodeTable[numVertices-1].adj;
Edge<T,E> *q = NULL;
while(p!=NULL)
{
int index = p->dest;
q = NodeTable[index].adj;
while(q!=NULL)
{
if(q->dest==(numVertices-1))
{
q->dest = v;
break;
}
q=q->link;
}
p=p->link;
}
numVertices--;
}
bool removeEdge(int v1,int v2)
{
if(v1<0||v1>=numVertices||v2<0||v2>=numVertices)
{return false;}
Edge<T,E> *p = NodeTable[v1].adj;
Edge<T,E> *q = NULL;
while(p!=NULL && p->dest!=v2)
{
q=p;
p=p->link;
}
if(q==NULL && p==NULL)
{
return false;
}
if(q==NULL && p!=NULL && p->dest==v2)
{
NodeTable[v1].adj=p->link;
delete p;
}
if(p==NULL)
{
return false;
}
else if(q!=NULL)
{
q->link=p->link;
delete p;
}
p = NodeTable[v2].adj;
q = NULL;
while(p!=NULL && p->dest!=v1)
{
q=p;
p=p->link;
}
if(q==NULL && p==NULL)
{
return false;
}
if(q==NULL && p!=NULL && p->dest==v1)
{
NodeTable[v2].adj=p->link;
delete p;
}
if(p==NULL)
{
return false;
}
else if(q!=NULL)
{
q->link=p->link;
delete p;
}
numEgde--;
}
bool insertEdge(const T& l,const T& r,E cost)
{
int v1 = getValuePos(l);
int v2 = getValuePos(r);
Edge<T,E> *p = NodeTable[v1].adj;
Edge<T,E> *s = new Edge<T,E>(v2,cost);
Edge<T,E> *q = NULL;
while(p!=NULL && p->dest!=cost)
{
q=p;
p=p->link;
}
if(p!=NULL && p->dest==cost)
{
return false;
}
if(q==NULL)
{
NodeTable[v1].adj = s;
}
if(p==NULL && q!=NULL)
{
s->link = NodeTable[v1].adj;
NodeTable[v1].adj=s;
}
p = NodeTable[v2].adj;
s = new Edge<T,E>(v1,cost);
q = NULL;
while(p!=NULL && p->dest!=cost)
{
q=p;
p=p->link;
}
if(p!=NULL && p->dest==cost)
{
return false;
}
if(q==NULL)
{
NodeTable[v2].adj = s;
}
if(p==NULL&&q!=NULL)
{
s->link = NodeTable[v2].adj;
NodeTable[v2].adj=s;
}
numEgde++;
}
bool insertVertex(const T& vertex)
{
NodeTable[numVertices++].data=vertex;
return true;
}
void Show()
{
Edge<T,E> *p=NULL;
for(int i=0;i<numVertices;i++)
{
cout<<NodeTable[i].data<<"> ";
p=NodeTable[i].adj;
while(p!=NULL)
{
cout<<p->dest<<"--"<<p->cost<<" ";
p=p->link;
}
cout<<endl;
}
}
E getWeight(int v1,int v2)
{
if(v1<0 || v1>=numVertices || v2<0 || v2>=numVertices)
{
return -1;
}
Edge<T,E> *p = NodeTable[v1].adj;
// Edge<T,E> *m = NULL;
while(p!=NULL)
{
//m = p;
if(p->dest==v2)
break;
p=p->link;
}
if(p!=NULL)
{return p->cost;}
else
{return maxWeight;}
}
T getValue(int i)
{
return NodeTable[i].data;
}
int NumberOfVertices()
{
return numVertices;
}
int getValuePos(const T &t)
{
for(int i=0;i<numVertices;i++)
{
if(NodeTable[i].data==t)
return i;
}
return -1;
}
Edge<T,E> * getNodeptr(int i)
{
return NodeTable[i].adj;
}
private:
int numVertices;
int maxVertices;
int numEgde;
Vertex<T,E> *NodeTable;
};
template<typename T,typename E>
void DFS(Graphlnk<T,E>& G,const T& v,bool visted[])
{
int index = G.getValuePos(v);
cout<<G.getValue(index)<<endl;
visted[index]=true;
int w = G.getFirstNeighbor(index);
while(w!=-1)
{
if(!visted[w])DFS(G,G.getValue(w),visted);
w = G.getNextNeighbor(index,w);
}
/* while(index!=-1)
{
int x = 0;
while(!visted[index])
{
cout<<G.getValue(index)<<endl;
visted[index]=true;
x = G.getFirstNeighbor(index);
DFS(G,G.getValue(x),visted);
}
index = G.getNextNeighbor(x,index);
}*/
}
template<typename T,typename E>
void DFS(Graphlnk<T,E>& G,const T& v)
{
int n = G.NumberOfVertices();
bool *visted = new bool[n];
for(int i=0;i<n;i++)
{
visted[i] = false;
}
DFS(G,v,visted);
}
template<typename T,typename E>
void BFS(Graphlnk<T,E>& G,const T& v)
{
int n = G.NumberOfVertices();
bool *visted = new bool[n];
for(int i=0;i<n;i++)
{
visted[i] = false;
}
int i = G.getValuePos(v);
queue<int> Q;
Q.push(i);
int index;
while(!Q.empty())
{
index = Q.front();
Q.pop();
if(!visted[index])
{
cout<<G.getValue(index)<<endl;
visted[index] = true;
}
int x = G.getFirstNeighbor(index);
while(x!=-1)
{
if(!visted[x])
{
Q.push(x);
}
x = G.getNextNeighbor(index,x);
}
}
}
template<typename T,typename E>
void Search(Graphlnk<T,E> &G)
{
bool *visted = new bool[G.NumberOfVertices()];
for(int i=0;i<G.NumberOfVertices();i++)
{
if(!visted[i])
DFS(G,G.getValue(i),visted);
}
}
main.cpp:
#include <iostream>
#include "main.h"
using namespace std;
template<typename T>
class MinHeap
{
public:
MinHeap(int sz)
{
Maxsize = sz;
data = new T[sz];
Numsize = 0;
}
void Insert(T x)
{
data[Numsize++] = x;
int n = Numsize/2;
while(n>=0)
{
Sort(data,n);
n--;
}
}
void Swap(T *a,T *b)
{
T temp = *a;
*a = *b;
*b = temp;
}
T Remove()
{
T temp = data[0];
int n=Numsize;
Numsize=0;
for(int i=1;i<n;i++)
{
Insert(data[i]);
}
return temp;
}
void Sort(T a[],int n)
{
int i = n ;
int j = 2*i+1;
while(j<Numsize)
{
if(j+1<Numsize && a[j]>a[j+1])
j=j+1;
if(j<Numsize && a[i]>a[j])
Swap(&a[i],&a[j]);
i = j;
j = 2*i+1;
}
}
void Show()
{
for(int i=0;i<Numsize;i++)
{
cout<<data[i]<<" ";
}
cout<<endl;
}
private:
T *data;
int Maxsize;
int Numsize;
};
class UFset
{
public:
UFset(int sz)
{
parent = new int[sz];
size = sz;
for(int i=0;i<sz;i++)
{
parent[i]=-1;
}
}
void Show()
{
for(int i=0;i<size;i++)
{
cout<<parent[i]<<" ";
}
cout<<endl;
for(int j=0;j<size;j++)
{
cout<<j<<" ";
}
cout<<endl;
}
void Union(int a,int b)
{
int x = Find(a);
int y = Find(b);
if(x!=y)
{
if(x>y)
{
parent[x]+=parent[y];
parent[y]=x;
}
else
{
parent[y]+=parent[x];
parent[x]=y;
}
}
}
int Find(int x)
{
while(parent[x]>0)
x=parent[x];
return x;
}
private:
int *parent;
int size;
};
#define Default -1
const float maxValue = Default;
template<typename T,typename E>
struct MSTEdgeNode
{
int tail,head;E key;
MSTEdgeNode():tail(-1),head(-1),key(0){}
bool operator > (const MSTEdgeNode<T,E> &MST)
{
return key>MST.key;
}
bool operator < (const MSTEdgeNode<T,E> &MST)
{
return key<MST.key;
}
MSTEdgeNode& operator = (const MSTEdgeNode& MST)
{
tail = MST.tail;
head = MST.head;
key = MST.key;
return *this;
}
};
template<typename T,typename E>
class MinSpanTree
{
protected:
MSTEdgeNode<T,E> *edgevalue;
int MaxSize,n;
public:
MinSpanTree(int sz=Default-1):MaxSize(sz),n(0)
{
edgevalue = new MSTEdgeNode<T,E>[sz];
}
int Insert(MSTEdgeNode<T,E>& item)
{
edgevalue[n++]=item;
}
void Show()
{
for(int i=0;i<n;i++)
{
cout<<edgevalue[i].tail<<":"<<edgevalue[i].head<<":"<<edgevalue[i].key<<" ";
cout<<endl;
}
}
};
template<typename T,typename E>
void Kruskal(Graphlnk<T,E>& G,MinSpanTree<T,E> &MST)
{
MSTEdgeNode<T,E> ed;int u,v,count;
int n = G.NumberOfVertices();
int m = G.NumberOfEdge();
MinHeap<MSTEdgeNode<T,E> >H(m);
UFset F(n);
for(u = 0;u<n;u++)
{
for( v = u+1;v<n;v++)
{
if(G.getWeight(u,v)!=maxValue)
{
ed.tail = u;
ed.head = v;
ed.key = G.getWeight(u,v);
H.Insert(ed);
//H.Show();
}
}
}
count=1;
while(count<m)
{
ed = H.Remove();
u = F.Find(ed.tail);
v = F.Find(ed.head);
if(u != v)
{
F.Union(u,v);
MST.Insert(ed);
}
count++;
}
}
int main()
{
MinSpanTree<char,int> mst(10);
Graphlnk<char,int> gh;
gh.insertVertex('A');
gh.insertVertex('B');
gh.insertVertex('C');
gh.insertVertex('D');
gh.insertVertex('E');
gh.insertVertex('F');
gh.insertVertex('G');
gh.insertEdge('A','B',28);
gh.insertEdge('B','C',16);
gh.insertEdge('C','D',12);
gh.insertEdge('D','E',22);
gh.insertEdge('E','F',25);
gh.insertEdge('F','A',10);
gh.insertEdge('B','G',14);
gh.insertEdge('D','G',18);
gh.insertEdge('E','G',24);
gh.Show();
cout<<"-------------------"<<endl;
Kruskal(gh,mst);
mst.Show();
return 0;
}