#ifndef _GRAPH_H
#define _GRAPH_H
#define DEFAULT_VERTEX_SIZE 10
typedef struct
{
int x;
int y;
int cost;
}edge;
template<class Type>
class Graph;
class Edge
{
public:
Edge(int num,int c):dest(num),cost(c),link(NULL)
{}
~Edge()
{}
int dest;
Edge* link;
int cost;
};
template<class Type>
class Vertex
{
friend Graph<Type>;
public:
Vertex():data(Type()),adj(NULL)
{}
~Vertex()
{}
private:
Edge *adj;
Type data;
};
template<class Type>
class Graph
{
public:
Graph(int sz=DEFAULT_VERTEX_SIZE)
{
MaxVertices=sz>DEFAULT_VERTEX_SIZE?sz:DEFAULT_VERTEX_SIZE;
NumVertices=NumEdge=0;
NodeTable=new Vertex<Type>[MaxVertices];
}
~Graph()
{
Edge *t;
for(int i=0;i<NumVertices;++i)
{
Edge *w;
t=NodeTable[i].adj;
while(t!=NULL)
{
w=t;
t=t->link;
delete w;
}
}
delete[] NodeTable;
//////
}
int GetPosOfVertex(const Type &v)const
{
for(int i=0;i<NumVertices;++i)
{
if(NodeTable[i].data==v)
return i;
}
return -1;
}
void InsertVertex(const Type &val)
{
if(NumVertices<MaxVertices)
{
NodeTable[NumVertices++].data=val;
}
}
bool InsertEdge(const Type &vertex1, const Type &vertex2,int cost)
{
int v1 = GetPosOfVertex(vertex1);
int v2 = GetPosOfVertex(vertex2);
if(v1==-1 || v2==-1)
return false;
//v1 --> v2
Edge *e = new Edge(v2,cost);
e->link = NodeTable[v1].adj;
NodeTable[v1].adj = e;
//v2 --> v1
e = new Edge(v1,cost);
e->link = NodeTable[v2].adj;
NodeTable[v2].adj = e;
NumEdge++;
return true;
}
/*
bool InsertEdge(const Type &v1,const Type &v2)
{
int V1=GetPosOfVertex(v1);
int V2=GetPosOfVertex(v2);
if(V1==-1||V2==-1)
return false;
//v1-->v2
cout<<"v1: "<<V1<<" v2: "<<V2<<endl;
Edge *s=new Edge(V2);
s->link=NodeTable[V1].adj;
NodeTable[V1].adj=s;
//v2-->v1
Edge *s1=new Edge(V1);
s1->link=NodeTable[V2].adj;
NodeTable[V1].adj=s1;
++NumEdge;
return true;
}
*/
int NumOfVertex()const
{
return NumVertices;
}
int NumOfEdge()const
{
return NumEdge;
}
Type GetValueByIndex(int i)
{
if(i<=NumVertices&&i>=0)
return NodeTable[i].data;
}
int GetFirstNeighbor(const Type &vertex)const
{
int v=GetPosOfVertex(vertex);
if(v==-1)
return -1;
if( NodeTable[v].adj!=NULL)
return NodeTable[v].adj->dest;
else
return -1;
}
int GetNextNeighbor(const Type &vertex1,const Type &vertex2)const
{
int v1=GetPosOfVertex(vertex1);
int v2=GetPosOfVertex(vertex2);
if(v1==-1||v2==-1)
return -1;
if(NodeTable[v1].adj==NULL)
return -1;
Edge *t=NodeTable[v1].adj;
while(t!=NULL&&t->dest!=v2)
t=t->link;
if(t==NULL)
return -1;
else
if(t->link!=NULL)
return t->link->dest;
else
return -1;
}
bool RemoveEdge(const Type &vertex1,const Type &vertex2)
{
int v1=GetPosOfVertex(vertex1);
int v2=GetPosOfVertex(vertex2);
if(v1==-1||v2==-1)
return false;
Edge *t=NodeTable[v1].adj;
Edge *p=t;
while(t!=NULL&&t->dest!=v2)
{
p=t;
t=t->link;
}
if(t==NULL)
return false;
else
{
if(p==t)
{
Edge *w=NodeTable[v1].adj;
NodeTable[v1].adj=NodeTable[v1].adj->link;
delete w;
}
else
{
Edge *w=p->link;
p->link=t->link;
delete w;
}
//
t=p=NodeTable[v2].adj;
while(t->dest!=v1)
{
p=t;
t=t->link;
}
if(t==p)
{
Edge *w=NodeTable[v2].adj;
NodeTable[v2].adj=NodeTable[v2].adj->link;
delete w;
}
else
{
Edge *w=p->link;
p->link=t->link;
delete w;
}
--NumEdge;
return true;
}
}
bool RemoveVertex(const Type &vertex)
{
int v=GetPosOfVertex(vertex);
if(v==-1)
return false;
Edge* t=NodeTable[v].adj;
while(t!=NULL)
{
Edge *p=NodeTable[t->dest].adj;
Edge *p1=p;
while(p!=NULL)
{
while(p->dest!=v)
{
p1=p;
p=p->link;
}
if(p==p1)
{
Edge *w=NodeTable[t->dest].adj;
NodeTable[t->dest].adj=NodeTable[t->dest].adj->link;
delete w;
break;
}
else
{
Edge* w=p1->link;
p1->link=p->link;
delete w;
break;
}
}
p1=t;
t=t->link;
delete p1;
--NumEdge;
}
if(v!=NumVertices-1)
{
NodeTable[v].data=NodeTable[NumVertices-1].data;
NodeTable[v].adj=NodeTable[NumVertices-1].adj;
Edge *t1=NodeTable[NumVertices-1].adj;
while(t1!=NULL)
{
Edge *p3=NodeTable[t1->dest].adj;
while(p3->dest!=NumVertices-1)
p3=p3->link;
p3->dest=v;
t1=t1->link;
}
}
--NumVertices;
return true;
}
void DFSTraverse()//深度遍历
{
bool *visited=new bool[NumVertices];
for(int i=0;i<NumVertices;++i)
visited[i]=false;
for(int i=0;i<NumVertices;++i)
if(!visited[i])
DFS(i,visited);
}
void DFS(int v,bool *&visited)
{
if(v<=-1&&v>=NumVertices)
return ;
visited[v]=true;
cout<<NodeTable[v].data<<" ";
for(int w=GetFirstNeighbor(GetValueByIndex(v));w>=0;w=GetNextNeighbor(GetValueByIndex(v),GetValueByIndex(w)))
if(!visited[w])
DFS(w,visited);
}
void DFSTraverse_1(Type val)
{
bool *visited=new bool[NumVertices];
for(int i=0;i<NumVertices;++i)
visited[i]=false;
int x=GetPosOfVertex(val);
visited[x]=true;
cout<<NodeTable[x].data<<" ";
for(int w=GetFirstNeighbor(val);w>=0;w=GetNextNeighbor(val,GetValueByIndex(w)))
{
if(!visited[w])
{
visited[w]=true;
cout<<NodeTable[w].data<<" ";
}
}
for(int i=0;i<NumVertices;++i)
{
if(!visited[i])
{
visited[i]=true;
cout<<NodeTable[i].data<<" ";
for(int w=GetFirstNeighbor(GetValueByIndex(i));w>=0;w=GetNextNeighbor(GetValueByIndex(i),GetValueByIndex(w)))
if(!visited[w])
{
visited[w]=true;
cout<<NodeTable[w].data<<" ";
}
}
}
}
void BFSTraverse()//广度遍历
{
bool *visited=new bool[NumVertices];
for(int i=0;i<NumVertices;++i)
visited[i]=false;
queue<int> Q;
for(int i=0;i<NumVertices;++i)
{
if(!visited[i])
{
visited[i]=true;
cout<<NodeTable[i].data<<" ";
}
Q.push(i);
while(!Q.empty())
{
int u=Q.front();
Q.pop();
Edge *s=NodeTable[u].adj;
while(s!=NULL)
{
if(!visited[s->dest])
{
visited[s->dest]=true;
cout<<NodeTable[s->dest].data<<" ";
Q.push(s->dest);
}
s=s->link;
}
}
}
}
void BFSTraverse_1(Type v)
{
bool *visited=new bool[NumVertices];
queue<int> Q;
int x=GetPosOfVertex(v);
if(x==-1)
return;
Q.push(x);
cout<<v<<" ";
visited[x]=true;
Edge *s=NodeTable[x].adj;
while(s!=NULL)
{
if(!visited[s->dest])
{
visited[s->dest]=true;
Q.push(s->dest);
cout<<NodeTable[s->dest].data<<" ";
}
s=s->link;
}
while(!Q.empty())
{
int u=Q.front();
Q.pop();
s=NodeTable[u].adj;
while(s!=NULL)
{
if(!visited[s->dest])
{
visited[s->dest]=true;
cout<<NodeTable[s->dest].data<<" ";
Q.push(s->dest);
}
s=s->link;
}
}
}
void MinSpinTree(Type v)
{
int x=GetPosOfVertex(v);
cout<<v<<"-->"<<endl;
int *adjvertex=new int[NumVertices];
int *lowcost=new int [NumVertices];
for(int i=0;i<NumVertices;++i)
{
if(x!=i)
{
lowcost[i]=10000;
}
else
lowcost[i]=0;
adjvertex[i]=x;
}
Edge* p=NodeTable[x].adj;
while(p!=NULL)
{
lowcost[p->dest]=p->cost;
p=p->link;
}
for(int i=0;i<NumVertices;++i)
cout<<lowcost[i]<<" ";
cout<<endl;
for(int i=1;i<NumVertices;++i)
{
int min=1000;
int min_index;
for(int j=0;j<NumVertices;++j)
{
if(lowcost[j]!=0)
{
if(lowcost[j]<min)
{
min=lowcost[j];
x=j;
}
}
}
cout<<NodeTable[adjvertex[x]].data<<"-->"<<NodeTable[x].data<<":"<<min<<endl;
lowcost[x]=0;
p=NodeTable[x].adj;
while(p!=NULL)
{
if(p->cost!=0&&lowcost[p->dest]>p->cost)
{
lowcost[p->dest]=p->cost;
adjvertex[p->dest]=x;
}
p=p->link;
}
lowcost[x]=0;
// /*
for(int q=0;q<NumVertices;++q)
cout<<lowcost[q]<<" ";
cout<<endl;
//*/
}
}
void MinSpanTree_Kruskal();
void ShowGraph()
{
for(int i=0;i<NumVertices;++i)
{
cout<<i<<" "<<NodeTable[i].data<<" "<<"-->";
Edge* e=NodeTable[i].adj;
while(e!=NULL)
{
cout<<e->dest<<"("<<e->cost<<")"<<"-->";
e=e->link;
}
cout<<"NUL"<<endl;;
}
}
private:
Vertex<Type>*NodeTable;
int MaxVertices;
int NumVertices;
int NumEdge;
};
template<class Type>
void Graph<Type>::MinSpanTree_Kruskal()
{
}
#endif