一種數據結構，以儲存邊的方式來存儲圖。構造方法如下：讀入每條邊的信息，將邊存放在數組中，把數組中的邊按照起點順序排序(可以使用基數排序，如下面例程)，前向星就構造完了。通常用在點的數目太多，或兩點之間有多條弧的時候。一般在別的數據結構不能使用的時候才考慮用前向星。除了不能直接用起點終點定位以外，前向星幾乎是完美的。
基本介紹
- 中文名：前向星
- 性質：一種數據結構
- 用途：以儲存邊的方式來存儲圖
最佳化,程式,前向星pascal實現,前向星c++實現,前向星c++實現——非基數排序,
最佳化
前向星不需要像鄰接表那樣用指針指向下一條邊，還是挺方便的。但是，由於前向星初始化需要快排一遍，相對鄰接表要慢許多。考慮到一般圖論題點數都不會很大，所以可以改為採用基數排序的思想對前向星進行排序。
一開始讀入時，先算出每個點出去的邊有多少條，然後計算出排序後每個點出去的第一條邊位置應在哪裡，最後把全部邊掃一遍放到排序後應在的位置就好了。
這樣排序的話初始化的時間複雜度就降到了O(m)，總體時間並不會遜色於鄰接表。
程式
前向星pascal實現
procedure star; //計數排序的前向星var i,j,x,num1,num2:longint; beginfor 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 <vector>#include <cstdio>using namespace std;const int MAXN = 100000;vector<int> edge[MAXN];int main(){ int n, m; //n頂點,m邊 for(int i = 0; i < m; ++i) { int a, b; scanf("%d%d", &a, &b); edge[a].push_back(b); //edge[b].push_back(a); //如果是無向圖要執行這句，來回都要存！ } return 0;}前向星c++實現——非基數排序
#include <vector>#include <cstdio>#include <utility>#include <algorithm>#include <map>using namespace std;vector<pair<int, int> > edge;map<int, int> startPoint; //if the vertex id is small, you can use arrayint main(){ int n, m; //n vertexs, m edges for(int i = 0; i < m; ++i) { int a, b; scanf("%d%d", &a, &b); edge.push_back(make_pair(a, b)); //edge.push_back(make_pair(b, a)); //Execute this if the Graph is undirected } sort(edge.begin(), edge.end()); for(int i = 0; i < m; ++i) { int s = edge[i].first; if(startPoint.count(s)) continue; startPoint[s] = i; } return 0;}