链式前向星

[外链图片转存失败(img-0ZtAaOKX-1566637663940)(C:Users红豆AppDataRoamingTyporatypora-user-images1565857722159.png)]

链式前向星是邻接矩阵的一种。

如何用链式前向星来存图?

将上图存存完后应该是这个样子...

[外链图片转存失败(img-cSQxmDGc-1566637663941)(C:Users红豆AppDataRoamingTyporatypora-user-images1565858049997.png)]

v表示顶点,len表示长度,eid 代表这条边的编号,next表示指向下一条边的编号

左边数组P[u]表示,以u 为起点 所指的第一条的边的编号

比如1号点和2号点之间有一条边长度为10,还和3号点有一条边长度为5

所以点集可以用数组表示,边集可以用结构体表示

const int max_n = 100;
const int max_m = 10000;
struct node{
    int v,len;
    int next;
}E[max_m];
int p[max_n],eid;

next 是指向下一条边的编号。

构图之前要初始化,顶点之间开始没有边,记为-1,每进入一条边用头插的方式。

编号一开始初始化为0。

void init()
{
    memset(p,-1,sizeof(p));
    eid=0;
}

用头插的方式加边

怎么给每条边编号呢?eid代表编号,初始化为0,每当加入一条边的时候eid++.

void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++; 
}

很明显可以根据每个点,遍历它所有的边,当next为-1时,说明遍历完全

int main()
{
    init();
    insert(1,2,10);
    insert(1,3,5);
    insert(2,3,1);
    insert(3,5,10);
    insert(3,4,6);
    insert(5,4,11);

    for(int u=1;u<=5;++u)
    {
        cout<<u<<": ";
        for(int i = p[u];i+1;i = E[i].next)
        {
            cout<<E[i].v<<" "<<E[i].len<<" "<<i<<" ->";
        }        
        cout<<endl;
    }
    
    return 0;
}

打印的结果和预期一样

[外链图片转存失败(img-14lbcX6O-1566637663944)(C:Users红豆AppDataRoamingTyporatypora-user-images1565858804101.png)]

当加入第一条边时 , P[1] = 0

[外链图片转存失败(img-1rHqWBRS-1566637663945)(C:Users红豆AppDataRoamingTyporatypora-user-images1565858880550.png)]

当加入第二条边时

[外链图片转存失败(img-0p4CB11g-1566637663946)(C:Users红豆AppDataRoamingTyporatypora-user-images1565858948909.png)]

此时p[1] 值为1 E[eid].next值为0

然后整个过程都很好理解

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int max_n = 100;
const int max_m = 10000;
struct node{
    int v,len;
    int next;
}E[max_m];
int p[max_n],eid;
void init()
{
    memset(p,-1,sizeof(p));
    eid=0;
}
void insert(int u,int v,int len)
{
    E[eid].v = v;
    E[eid].len = len;
    E[eid].next = p[u];
    p[u] = eid++; 
}
int main()
{
    init();
    insert(1,2,10);
    insert(1,3,5);
    insert(2,3,1);
    insert(3,5,10);
    insert(3,4,6);
    insert(5,4,11);

    for(int u=1;u<=5;++u)
    {
        cout<<u<<": ";
        for(int i = p[u];i+1;i = E[i].next)
        {
            cout<<E[i].v<<" "<<E[i].len<<" "<<i<<" ->";
        }        
        cout<<endl;
    }
    cout << p[1]<<endl;
    cout << E[1].next<<endl;
    return 0;
}
Last modification:September 18th, 2019 at 11:41 pm
如果觉得我的文章对你有用,请随意赞赏