【算法与数据结构】——链式前向星

阳光穿透心脏的1/2处 2022-08-30 04:09 194阅读 0赞

# 简介 #

链式前向星在我写的[【算法与数据结构】——离散化、拓扑排序以及最短路算法的堆优化][Link 1]这个里面有提到，但是当时描述的比较简单，现在印象有所加深，在详细描述一下。  
总的来说链式前向星跟邻接表有些相似，不过邻接表是将与头结点所存储的顶点相连的顶点的值存到相同的结构体中，将他们连接在一起。而链式前向星是将一个顶点所连接的顶点的值放到一个数组里。

### 原理 ###

一般会需要如下内容  
存储边信息的结构体

struct Edge{ 
    int to;		//存储与a顶点相连的顶点
    int val;	//存储边的权值
    int next;	//下一个与a顶点相连的顶点

需要两个数组

Edge edge[];//存储边的数组
    int head[a];//存储a顶点对应边的下标

### 实现 ###

有向图

for(int i=0;i<vexnumber;i++)
        { 
            head[i]=-1;
        }
        cin>>edgenum;
        //由于是有向图，只需要建一个边
        for(int i=0;i<edgenum;i++)
        { 
            int from,to,v;
            cin>>from>>to>>v;
            edge[i].to=to;
            edge[i].val=v;
            edge[i].next=head[from];//类似链表头插
            head[from]=i;
        }

无向图，两个方向都要存储

for(int i=0;i<vexnumber;i++)
        { 
            head[i]=-1;
        }
        cin>>edgenum;
        //由于是无向图，要正向反向都建边
        for(int i=0;i<2*edgenum;i+=2)
        { 
            int from,to,v;
            cin>>from>>to>>v;
            //第一条
            edge[i].to=to;
            edge[i].val=v;
            edge[i].next=head[from];//类似链表头插
            head[from]=i;
            //第二条
            edge[i+1].to=from;
            edge[i+1].val=v;
            edge[i+1].next=head[to];
            head[to]=i+1;
        }

[Link 1]: https://blog.csdn.net/qq_45488453/article/details/115013482