链式前项星的概念与应用

链式前向星

• 链式前向星在存储图时十分有用，特别是当边有权值时。我们用过一道题目了来具体分析一下

链式前向星只是一种应用，是一种小技巧。所以我们先要构造一个链式前向星来存储数据。

int n,m,cnt;//全局变量默认为0
int head[N],dis[N];
//head数组就是存储头节点的数组，head[i]就是存储以i为起点的第一条边的下标
struct Edge
{
    //链式前向星的三个空间：to代表这条边连接的另一个方向（因为一个方向就是头节点）
    //c代表权值，在这里就是指颜色
    //next存储的是下一条边的编号，如果没有下一条了，那么就是-1
    int to,c,next;
}e[M];
void add(int u,int v,int c)
{
    //这个add函数就是实现头插
    //cnt代表边序号
    e[++cnt].to = v;
    e[cnt].c = c;
    //这一步，其实就是指向这个头结点指向的第一条边
    e[cnt].next = head[u];
    //然后更新头结点的第一条边，让头结点的第一条边为这条边
   //cnt++就是这条边的序号
    head[u] = cnt;
}

int u,v,c;
while(cin>>n>>m)//输入n也就是最后要达到的目标，m也就是下面数据的组数
{
	memset(head,0, sizeof(head));
    cnt = 0;
    for(int i =1;i<=m;i++)
    {
        //这里，因为我们要存储的是无向图，所以对于每一组数据，都要存储两条边
        //一条从头指向尾，一条反指
    	cin>>u>>v>>c;
        add(u,v,c);
        add(v,u,c);
        
    }
     bfs1();
     cout<<dis[1]<<endl;
     bfs2();
     cout<<endl;
}

• 构建好，并存储好后，开始bfs

//关于为什么要逆向标高
//逆向标高是从目标反向遍历，比如我们要从1找到4，那么从4开始反向便利
//这样，4 的深度为0，1的深度为2，那么1->4 的深度是2
//因为要输出至少经过k条边，那么深度就是边的条数
void bfs1()//逆向标高
{
    int u,v;
    //首先把所有的节点的访问值标为0，在接下来的访问中，凡是访问到，标为1
    memset(vis,false, sizeof(vis));
    //首先把目标的深度标为0
    dis[n]=0;
    //队列q1是保存节点号的
    q1.push(n);
    //然后把n设为已经访问
    vis[n]=true;
    //第一次深度搜索
    while(!q1.empty())
    {
        //每次u设为队列的头节点，
        u = q1.front();
        q1.pop();
        //把u设为已经访问
        vis[u]=true;
        //把头节点出队以后，将这个头结点所有的边连接着的节点入队
        for(int i  = head[u];i;i=e[i].next)
        //因为存储的时候是从1开始的，所以结束条件是i！=0
        {            
            v=e[i].to;
            if(vis[v])//如果v已经被访问过了
                continue;
            //把下一个结点的深度标为出队节点+1
            dis[v]=dis[u]+1;
            //然后把新节点入队
            q1.push(v);
            //把新节点标记为访问
            vis[v]=true;
        }
    }
}

• 反向遍历之后，我们需要从1开始正向遍历

void bfs2()
{
    int u,v,minc,c;
    bool first = true;
    //刚才vis数组已经有改了，现在是正向遍历，所以要重置
    memset(vis,false,sizeof(vis));
    vis[1] = true;
    //从1开始bfs，把1所有连接的节点，而且节点是满足”1的深度“-1的，入队
    for(int i = head[1];i;i = e[i].next)
        if(dis[e[i].to]==dis[1]-1)
        {
            //这里，入队不仅仅是把节点号入队，也要把颜色入队
            q1.push(e[i].to);
            q2.push(e[i].c);
        }
    while(!q1.empty())
    {
        //把最小的颜色号初始化为最大值
        minc = inf;
        while(!q1.empty())
        {
            //和bfs1一样，先出队，然后把符合条件的全部入队
            //q1，q2同时入队，同时出队，能保证他们之间是一一对应的
            v= q1.front();
            q1.pop();
            c= q2.front();
            q2.pop();
            //q3 用来保存色号最小的关联的临节点号
            //如果发现有比q3中存储的更小的色号，那么直接把q3清空
            //再把现有的色号存储进进q3
            if(c<minc)
            {
                while(!q3.empty())
                    q3.pop();
                minc = c;
            }
            if(c==minc)
                q3.push(v);
        }
        if(first)
            first = false;
        else
            cout<<" ";
        //这样，每一次输出的都是当前深度下，最小的色号
        cout<<minc;
        //接下俩这一步就是通过当前q3中存储的这些节点出发，寻找下一层、
        //并且把下一层的节点和色号都入队
        //且能达到清空q3的作用，为下一次循环做准备
        while(!q3.empty())
        {
            u = q3.front();
            q3.pop();
            if(vis[u])
                continue;
            vis[u]=true;
            for(int i = head[u];i;i = e[i].next)
            {
                v=e[i].to;
                if(dis[v]==dis[u]-1)
                {
                    q1.push(v);
                    q2.push(e[i].c);
                }
            }
        }
    }
}