链式前向星详解

链式前向星

图的存储一般有两种：邻接矩阵、邻接表（邻接表包括一种东西叫前向星）。
若图是稀疏图，边很少，开二维数组a[][]很浪费;
若点很多(如10000个点)a[10000][10000]又会爆.只能用前向星做.
前向星的效率不是很高，优化后为链式前向星，直接介绍链式前向星。
数据结构

struct edg
{
    int to;//用来存储终点
    int w;//用来存储权值
    int next;//用来存储相同开始点的下一条边的编号；（用来通过下一条边寻找这一条边；
};

链式前向星的思想类似于数组模拟链表，利用next不断的寻找相同起点的上一个点的值；

存图函数

   for(int i = 1; i <= m; i++)//存图
    {
        int a, b, c;
        cin >> a  >> b >> c;
        edgs[i].to = b;//终点
        edgs[i].w = c;//权值
        edgs[i].next = head[a];//以a为起点的下一点的编号，如果值为-1就代表没有下一点了；
        head[a] = i;//不断的松弛head的值
    }

在存图函数中的精髓是head的松弛操作，每次找到具有相同起点的边时都要对head进行一次松弛操作；

对于数据：
5 7
1 2 1
2 3 2
3 4 3
1 3 4
4 1 5
1 5 6
4 5 7
edgs[1].to = 2 edgs[1].next = -1;
edgs[2].to = 3 edgs[2].next = -1;
edgs[3].to = 4 edgs[3].next = -1;
edgs[4].to = 3 edgs[4].next = 1;
edgs[5].to = 1 edgs[5].next = -1;
edgs[6].to = 5 edgs[6].next = 4;
edgs[7].to = 5 edgs[7].next = 5;
head数组中存储的数据分别是6 2 3 7 -1；
那么为什么next中会有 -1 呢？原因很简单我们先来看一下打印函数

for(int i = 1; i <= m; i++)//输出图；第一层遍历节点，第二层遍历一i为起点的边；
    {
        cout << i << " : " << endl;
        for(int j = head[i]; j != -1; j = edgs[j].next)
        {
             cout << i << " " << edgs[i].to << " " << edgs[i].next  << endl;
        }
        cout << endl;
    }

我们注意一下第二层遍历中的结束条件j != -1;也就是说只有以i为起点的第一条边的next中才会存储-1值，也是我们的结束条件；

完整代码

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
const int maxn = 10005;
struct edg
{
    int to;//用来存储终点
    int w;//用来存储权值
    int next;//用来存储相同开始点的下一条边的编号；（用来通过下一条边寻找这一条边；
}edgs[maxn];//用来存储边的集合
int head[maxn];//head[i]表示以i为起点的最后一条边在edgs中的位置；
int main()
{
    int n, m;//分别表示点的数量和边的数量。
    cin >> n >> m;
    memset(head, -1, sizeof(head));//对head进行初始化为-1；
    for(int i = 1; i <= m; i++)//存图
    {
        int a, b, c;
        cin >> a  >> b >> c;
        edgs[i].to = b;//终点
        edgs[i].w = c;//权值
        edgs[i].next = head[a];//以a为起点的下一点的编号，如果值为-1就代表没有下一点了；
        head[a] = i;//不断的松弛head的值
    }
    for(int i = 1; i <= m; i++)//输出图；第一层遍历节点，第二层遍历一i为起点的边；
    {
        cout << i << " : " << endl;
        for(int j = head[i]; j != -1; j = edgs[j].next)
        {
             cout << i << " " << edgs[i].to << " " << edgs[i].next  << endl;
        }
        cout << endl;
    }
    for(int i = 1; i <= n; i++)
    cout << head[i] << endl;

}

原创转载请注明出处