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