C++数据结构 22 图-邻接表
#include <iostream>
#include <list>
using namespace std;
class Vertex
{
};
template<class T>
class Graph
{
public:
Graph(const int vertices):n(vertices)
{
VertexList=new T*[n];
HeadList=new list<int>[n];
nVerts=0;
}
~Graph()
{
delete []VertexList;
delete []HeadList;
}
void addVertex(T* v);
void addEdge(int Start,int End);
void PrintVertex(); //打印顶点
void Printadjst(); //打印图表
private:
T** VertexList; //数组 保存链表
list<int>*HeadList; //数组保存顶点
int n; //最大的顶点
int nVerts; //当前顶点
};
template<class T>
void Graph<T>::addVertex(T* v) //增加一个顶点
{
VertexList[nVerts++]=v;
}
template<class T>
void Graph<T>::addEdge(int Start,int End) //增加一条边
{
HeadList[Start].push_back(End);
}
template<class T>
void Graph<T>::PrintVertex() //打印
{
for(int i=0;i<nVerts;i++)
cout<<*VertexList[i]<<" ";
cout<<endl;
}
template<class T>
void Graph<T>::Printadjst() //打印链表
{
for(int i=0;i<nVerts;i++)
{
cout<<i<<"->";
for(list<int>::iterator iter=HeadList[i].begin();iter!=HeadList[i].end();iter++)
cout<<*iter<<"->";
cout<<endl;
}
}
int main()
{
Graph<char> g(5);
char a='A';
char b='B';
char c='C';
char d='D';
char e='E';
g.addVertex(&a);
g.addVertex(&b);
g.addVertex(&c);
g.addVertex(&d);
g.addVertex(&e);
g.PrintVertex();
g.addEdge(0,1);
g.addEdge(0,3);
g.addEdge(1,0);
g.addEdge(1,4);
g.addEdge(2,4);
g.addEdge(3,0);
g.addEdge(3,4);
g.addEdge(4,1);
g.addEdge(4,2);
g.addEdge(4,3);
g.Printadjst();
//cout << "Hello world!" << endl;
return 0;
}