前向星

百度百科

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

优化

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

示例解释

有向图.png

由示例得到的前向星为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
    A-b
  • 输入边B-->C
    B-C
  • 输入边B-->D,注意观察head[B]的变化。
    B-D
  • 输入边A-->D,注意观察head[A]的变化。
    A-D
  • 输入边C-->D
    C-D
  • 输入边A-->C,注意观察head[A]的变化。
    A-D
Last modification:March 27th, 2020 at 05:57 pm
如果觉得我的文章对你有用,请随意赞赏