基本介紹
- 中文名:邊集數組
- 外文名:edgeset array
- 類別:表示方法
- 特點:可任意安排,也可根據具體而定
- 適用範圍:程式設計
- 領域:計算機
定義,例子,適用範圍,
定義
邊集數組是由兩個一維數組構成,一個是存儲頂點的信息,另一個是存儲邊的信息,這個邊數組每個數據元素由一條邊的起點下標(begin),終點下標(end)和權(weight)組成。帶權圖(網)的另一種存儲結構是邊集數組,它適用於一些以邊為主的操作。用邊集數組表示帶權圖時,列出每條邊所依附的兩個頂點及邊上的權,即每個數組元素代表一條邊的信息。
例子
前向星是一個邊集數組,把邊的起點終點和權值存起來,然後以起點從小到大或者從大到小排序,記錄每個頂點在數組中的起始位置和長度.。適用於點多邊少的稀疏圖,或兩點之間有多條弧的時候。
下面介紹一下鏈式前向星構造方法如下:
(1)每讀入一條邊i的信息;
(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)。從空間複雜性上講,邊集數組也適合表示稀疏圖。圖的鄰接矩陣、鄰接表和邊集數組表示各有利弊,具體套用時,要根據圖的稠密和稀疏程度以及運算的要求進行選擇。