-
前向星
鎖定
一種數據結構，以儲存邊的方式來存儲圖。構造方法如下：讀入每條邊的信息，將邊存放在數組中，把數組中的邊按照起點順序排序(可以使用基數排序，如下面例程)，前向星就構造完了。通常用在點的數目太多，或兩點之間有多條弧的時候。一般在別的數據結構不能使用的時候才考慮用前向星。除了不能直接用起點終點定位以外，前向星幾乎是完美的。
- 中文名
- 前向星
- 性 質
- 一種數據結構
- 用 途
- 以儲存邊的方式來存儲圖
前向星優化
前向星不需要像鄰接表那樣用指針指向下一條邊，還是挺方便的。但是，由於前向星初始化需要快排一遍，相對鄰接表要慢許多。考慮到一般圖論題點數都不會很大，所以可以改為採用基數排序的思想對前向星進行排序。
一開始讀入時，先算出每個點出去的邊有多少條，然後計算出排序後每個點出去的第一條邊位置應在哪裏，最後把全部邊掃一遍放到排序後應在的位置就好了。
這樣排序的話初始化的時間複雜度就降到了O(m)，總體時間並不會遜色於鄰接表。
前向星程序
前向星pascal實現
procedure star; //計數排序的前向星 var i,j,x,num1,num2:longint; begin for i:=1 to m do //m為邊的條數（如果是無向圖，記得要2*m，正反向都要存!!！） begin read(num1,num2); //讀取起點num1和起點num2 a[i,1]:=num1; a[i,2]:=num2; inc(s[a[i,1]]); //s數組存的是以a[i,1]為起點的邊的個數 end; //讀入完畢！ first[1]:=1; //c初始化，準備開始排序 for i:=2 to n do //開始排序 begin first[i]:=first[i-1]+s[i-1]; last[i]:=first[i]-1; end; //first[i]表示以點i為起點的邊在前向星中的開始位置，last為結束位置 //先將last數組初始化作為指針用於下面把各個邊排序，排序完以後就能表示結束位置了 //舉例：若first[4]=5; last[4]=6; 表示map[5,1]-map[6,1]都是以4為起點的邊。 for i:=1 to m do //枚舉所有邊，準備排序。 begin inc(last[a[i,1]]); x:=last[a[i,1]]; map[x,1]:=a[i,1]; map[x,2]:=a[i,2]; //last指針後移一位，x純粹用來增加程序可讀性。將讀入的邊按指針插入到排序用的map數組 end; end; //最終map數組存的就是前向星，first和last數組存的是起始和結束位置。構造完畢
前向星c++實現
#include <bits/stdc++.h>
using namespace std;
struct Node {
int v, next;
} E[100001];
int p[100001], eid = 0;
inline void insert(int u, int v) {
eid++;
E[eid].v = v;
E[eid].next = p[u];
p[u] = eid;
}