学步园

#include<iostream>
#include<string>
using namespace std;

#define Max_Vex 256

template<class VNode>
class MatUnDirectedGraph
{
public:
MatUnDirectedGraph()
{
num=5;
VNodes=new VNode[num];
nodecount=0;
edgecount=0;
for(int i=0;i<num;i++)
{

for(int j=0;j<num;j++)
{
edges[i][j]=0;
}
}
}

void expand();
void addEdge(VNode start,VNode end,int len);
void removeEdge(VNode start,VNode end);
void addVNode(VNode element);
void removeVNode(VNode element);
void display();
private:
VNode * VNodes;
int  edges[Max_Vex][Max_Vex];
int nodecount;
int edgecount;
int num;

};

template<class VNode>
void MatUnDirectedGraph<VNode>::expand()
{
int i;
if((num+5)<=Max_Vex)
     num+=5;
else
{
cout<<"不能再添加顶点"<<endl;
return ;
}
VNode *larger=new VNode[num];
for(i=0;i<num;i++)
{
larger[i]=VNodes[i];
}

delete[] VNodes;
VNodes=larger;
larger=NULL;
for(i=0;i<num;i++)
for(int j=0;j<num;j++)
edges[i][j]=0;
}

template<class VNode>
void MatUnDirectedGraph<VNode>::addEdge(VNode start,VNode end,int len)
{
int i,j;
for(i=0;i<nodecount;i++)
{
if(start==VNodes[i])
{
break;
}
}

for(j=0;j<nodecount;j++)
{
if(end==VNodes[j])
{
break;
}
}

edges[i][j]=len;
edges[j][i]=len;
edgecount++;
}

template<class VNode>
void MatUnDirectedGraph<VNode>::removeEdge(VNode start,VNode end)
{
int i,j;
for(i=0;i<nodecount;i++)
{
if(start==VNodes[i])
{
break;
}
}

for(j=0;j<nodecount;j++)
{
if(end==VNodes[j])
{
break;
}
}

edges[i][j]=0;
edges[j][i]=0;
edgecount--;

}

template<class VNode>
void MatUnDirectedGraph<VNode>::addVNode(VNode element)
{
if(num==nodecount)
expand();
VNodes[nodecount++]=element;
}

template<class VNode>
void MatUnDirectedGraph<VNode>::removeVNode(VNode element)
{
int k,i,j;
for(k=0;k<nodecount;k++)
{
if(element==VNodes[k])
break;
}

for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(i>k && j>k)
edges[i][j]=edges[i+1][j+1];
else if(i>k)
edges[i][j]=edges[i+1][j];
else if(j>k)
edges[i][j]=edges[i][j+1];
}
}

for(i=0;i<num;i++)
{
edges[num-1][i]=0;
edges[i][num-1]=0;
}

for(i=k;i<nodecount;i++)
VNodes[i]=VNodes[i+1];

nodecount--;
}

template<class VNode>
void MatUnDirectedGraph<VNode>::display()
{
int i,j;
cout<<"图结构的顶点："<<endl<<endl;
for(i=0;i<nodecount;i++)
{
cout<<VNodes[i]<<"  ";
}
cout<<endl<<endl;

cout<<"顶点的关系矩阵："<<endl<<endl;

for(i=0;i<nodecount;i++)
{
for(j=0;j<nodecount;j++)
{
cout<<edges[i][j]<<"  ";
}
cout<<endl;
}
cout<<endl<<endl;
}

int main()
{
MatUnDirectedGraph<string> dg;

dg.addVNode("v0");
dg.addVNode("v1");
dg.addVNode("v2");
dg.addVNode("v3");
dg.addEdge("v0","v1",1);
dg.addEdge("v0","v2",1);
dg.addEdge("v0","v3",1);
dg.addEdge("v1","v2",1);
dg.addEdge("v2","v3",1);
dg.display();
// dg.removeEdge("v0","v2");
// dg.display();
dg.removeVNode("v3");
dg.display();

return 0;
}