邊集數組

邊集數組（edgeset array）是利用一維數組存儲圖中所有邊的一種圖的表示方法。該數組中所含元素的個數要大於等於圖中邊的條數，每個元素用來存儲一條邊的起點、終點（對於無向圖，可選定邊的任一端點為起點或終點）和權（若有的話），各邊在數組中的次序可任意安排，也可根據具體要求而定。

基本介紹

• 中文名：邊集數組
• 外文名：edgeset array
• 類別：表示方法
• 特點：可任意安排，也可根據具體而定
• 適用範圍：程式設計
• 領域：計算機

定義

邊集數組是由兩個一維數組構成，一個是存儲頂點的信息，另一個是存儲邊的信息，這個邊數組每個數據元素由一條邊的起點下標（begin），終點下標（end）和權（weight）組成。帶權圖（網）的另一種存儲結構是邊集數組，它適用於一些以邊為主的操作。用邊集數組表示帶權圖時，列出每條邊所依附的兩個頂點及邊上的權，即每個數組元素代表一條邊的信息。

例子

前向星是一個邊集數組，把邊的起點終點和權值存起來，然後以起點從小到大或者從大到小排序，記錄每個頂點在數組中的起始位置和長度.。適用於點多邊少的稀疏圖，或兩點之間有多條弧的時候。

下面介紹一下鏈式前向星構造方法如下：
(1)每讀入一條邊i的信息；

(2)將邊的終點和權值存放在數組中；

(3)把該條邊的next=headlist[a]。

前向星就構造完了。

代碼如下：

#include <iostream>#include <cstring>#include <cstdio>using namespace std;#define maxedge 20000#define maxn 5000   //結點數#define inf 1<<28bool vist[maxn];struct Edge{    // int s;   //邊的起點    int t;   //邊的終點    int next;//當前下一條邊的編號    int w;  //邊的權值}edge[maxedge];int headlist[maxedge]; //索引  head[i]存放已i為起點的“第一條”邊int n,m;//輸出前向星存儲的圖void show_graph(){    int i,k;    for(i=1;i<=n;i++)    {        for(k=headlist[i];k!=-1;k=edge[k].next)        {            printf("(%d --- > %d)==%d\n", i, edge[k].t, edge[k].w);        }    }}int main(){    int i,a,b,c;    while(~scanf("%d%d",&n,&m))    {        for(i=1;i<=n;++i)          headlist[i]=-1;        for(i=1;i<=m;++i)        {            scanf("%d%d%d",&a,&b,&c);            //edge[i].s=a;            edge[i].t=b;            edge[i].w=c;            edge[i].next=headlist[a];//索引：節點i 後一條邊編號為headlist[a]；            headlist[a]=i;        }        show_graph();    }    return 0;}

適用範圍

邊集數組適合那些對邊依次進行處理的運算，不適合對頂點的運算和對任一條邊的運算。

邊集數組表示通常包括一個邊集數組和一個頂點數組，所以其空間複雜性為O（n+e）。從空間複雜性上講，邊集數組也適合表示稀疏圖。圖的鄰接矩陣、鄰接表和邊集數組表示各有利弊，具體套用時，要根據圖的稠密和稀疏程度以及運算的要求進行選擇。