前向星

百度百科

一种数据结构，以储存边的方式来存储图。构造方法如下：读入每条边的信息，将边存放在数组中，把数组中的边按照起点顺序排序，前向星就构造完了。通常用在点的数目太多，或两点之间有多条弧的时候。一般在别的数据结构不能使用的时候才考虑用前向星。除了不能直接用起点终点定位以外，前向星几乎是完美的。

优化

前向星不需要像邻接表那样用指针指向下一条边，还是挺方便的。但是，由于前向星初始化需要快排一遍，相对邻接表要慢许多。考虑到一般图论题点数都不会很大，所以可以改为采用基数排序的思想对前向星进行排序。
一开始读入时，先算出每个点出去的边有多少条，然后计算出排序后每个点出去的第一条边位置应在哪里，最后把全部边扫一遍放到排序后应在的位置就好了。
这样排序的话初始化的时间复杂度就降到了O(m)，总体时间并不会逊色于邻接表。

前向星C++实现（基数排序优化）

const int MAXN = 1e6 + 117;//最大点数

struct Edge {//定义边
    int v, cost;
    Edge(int _v = 0, int _cost = 0): v(_v), cost(_cost) {}
};

vector<Edge> E[MAXN];

void addEdge(int u, int v, int w) {//加入一个u指向v权值为w的边
    E[u].push_back(Edge(v, w));
}

示例解释

由示例得到的前向星为E[A]={1,2,3} ;E[B]={4,5}; E[C]={6}; E[D]={};
此方法的实质是使用vector来存储以某个点为弧尾的所有弧，无向边需要拆分成两条有向边分别加边。
优点：易于理解，实现简单。
缺点，vector常数大。

链式前向星

百度百科

链式前向星是ssfz神牛Malash创造的（至少Baidu上没有搜到）名词，或许这种数据结构有其他更加正规易懂的名字，但我还是没有搜到。（有一个资料称之为加上next数组前向星，但这个名字实在不好） 该数据结构可能是Jason911神牛或其他神牛发明的。

横向比较

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好些，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。

C++实现

const int MAXN = 5010;//点数的最大值
const int MAXM = 50010;//边数的最大值

int head[MAXN], tot;
struct Edge {//定义边
    int to, next;
} edge[MAXM];

void init() {//初始化图
    tot = 0;
    memset(head, -1, sizeof(head));
}

void addEdge(int u, int v) {//加入一个u指向v权值为w的边
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}

示例解释

• 假设输入边的顺序为：A-->B、B-->C、B-->D、A-->D、C-->D、A-->C。
• 初态为
  
• 输入边A-->B
  
• 输入边B-->C
  
• 输入边B-->D,注意观察head[B]的变化。
  
• 输入边A-->D,注意观察head[A]的变化。
  
• 输入边C-->D
  
• 输入边A-->C,注意观察head[A]的变化。
  

版权属于：小影

本文链接：http://kindkidll.com/index.php/archives/62/

所有原创文章采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可。 您可以自由的转载和修改，但请务必注明文章来源并且不可用于商业目的。