<返回更多

图的十字链表存储方式解析

2020-07-08    
加入收藏

图的存储方式很多,常用的有邻接矩阵、邻接表、逆邻接表、十字链表、链式前向星等,邻接表和逆邻接表采用数组和链表方式存储,程序代码相对容易,邻接表求某顶点的出度容易但求入度较麻烦,逆邻接表求某顶点的入度容易但求出度较麻烦,为了达到鱼和熊掌兼得的效果,人们发明了十字链表的存储方式。

在十字链表中,顶点设计为一种结构体,并采用一维数组存储顶点。顶点结构体含有三个域,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相同的为以该顶点为头的边的集合,以链表方式存储。

其实,我们也可以根据自己需要灵活设计顶点和边的结构体来存储图,以达到解决某特定问题的目的。所以,数据结构决定了算法,选择好的数据结构可以减轻算法的压力。

声明:本站部分内容来自互联网,如有版权侵犯或其他问题请与我们联系,我们将立即删除或处理。
▍相关推荐
更多资讯 >>>