图的存储方式很多,常用的有邻接矩阵、邻接表、逆邻接表、十字链表、链式前向星等,邻接表和逆邻接表采用数组和链表方式存储,程序代码相对容易,邻接表求某顶点的出度容易但求入度较麻烦,逆邻接表求某顶点的入度容易但求出度较麻烦,为了达到鱼和熊掌兼得的效果,人们发明了十字链表的存储方式。
在十字链表中,顶点设计为一种结构体,并采用一维数组存储顶点。顶点结构体含有三个域,data存储顶点名称(序号),firstin存储以该顶点为头的第一个边的结点,firstout存储以该顶点为尾的第一个边的结点。
边设计为一种结构体,采用链表方式存储。边的结构体含有五个域,tailvex存储该边的尾顶点的名称(序号),headvex存储该边的头顶点的名称(序号),hlink存储头相同的下一条边的结点,tlink存储尾相同的下一条边的结点,info存储边的信息(如权值)。
下面以一个有向图为例来编写代码:
首先定义边结构体和顶点结构体:
struct EdgeNode{
int tail;
int head;
EdgeNode* hlink;
EdgeNode* tlink;
int info;
};
struct VerNode{
int num;
EdgeNode* firstin;
EdgeNode* firstout;
};
在main程序中开两个数组,一个存储顶点结点,一个存储边结点:
VerNode vn[4];
EdgeNode en[7];
初始化顶点:
for(int i=0;i<4;i++){
vn[i].num=i;
vn[i].firstin=NULL;
vn[i].firstout=NULL;
}
输入边的信息(增加新的边结点时,链表前用前插方式,这样比较方便):
for(int i=0;i<7;i++){
int tv,hv,val;
cin>>tv>>hv>>val;
en[i].tail=tv;
en[i].head=hv;
en[i].info=val;
en[i].tlink=vn[tv].firstout;
vn[tv].firstout=&en[i];
en[i].hlink=vn[hv].firstin;
vn[hv].firstin=&en[i];
}
对于上图,输入边的数据(尾、头、权值):
0 1 1
0 2 1
2 0 1
2 3 1
3 0 1
3 1 1
3 2 1
输出各个顶点出度、入度信息:
for(int i=0;i<4;i++){
cout<<"从"<<i<<"出发的边:"<<endl;
EdgeNode* p=vn[i].firstout;
while(p!=NULL){
cout<<i<<"-->"<<p->head<<endl;
p=p->tlink;
}
cout<<"到达"<<i<<"的边:"<<endl;
EdgeNode* q=vn[i].firstin;
while(q!=NULL)
cout<<q->tail<<"-->"<<i<<endl;
q=q->hlink;
}
}
十字链表存储图示如下:
从上图中可以看出,边结点tailvex值相同的为以该顶点为尾的边的集合,以链表方式存储;headvex相同的为以该顶点为头的边的集合,以链表方式存储。
其实,我们也可以根据自己需要灵活设计顶点和边的结构体来存储图,以达到解决某特定问题的目的。所以,数据结构决定了算法,选择好的数据结构可以减轻算法的压力。