邊集數組

邊集數組

邊集數組(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)。從空間複雜性上講,邊集數組也適合表示稀疏圖。圖的鄰接矩陣、鄰接表和邊集數組表示各有利弊,具體套用時,要根據圖的稠密和稀疏程度以及運算的要求進行選擇。

相關詞條

熱門詞條

聯絡我們