-
邊表
（算法領域術語）
鎖定
- 中文名
- 邊表
- 適用領域
- 算法領域
- 別 名
- 邊集表
邊表簡介
邊表是圖的一種存儲結構，用來描述圖上的每一個點。對圖的每個邊進行編號，對圖的每個頂點建立一個鏈表（n個頂點建立n個鏈表），第i個容器中的結點包含以頂點Vi為起點的所有邊的編號。
邊表與鄰接表的區別：邊表存儲了以點為起點的邊的信息，鄰接表存儲了以點為出發點的點的信息。
邊表用一個容器存儲了所有的邊，與前向星有相似之處。
邊表代碼實現
#include <stdio.h>
#include <string.h>
#define MAXM 1000000 //最大邊數
#define MAXN 100000 //最大頂點數
int n, m, i, j, u, v, w;
int V[MAXM], W[MAXM], head[MAXN], next[MAXM], tot;
void add(int u, int v, int w){
//第tot條邊的信息被存入
V[tot] = v;
W[tot] = w;
//將第tot條邊插入到以i為起點的鏈表中，鏈表以-1為終點
//*不區分重邊
next[tot] = head[u];
head[u] = tot;
tot++;
}
int main(){
scanf("%d %d", &n, &m);
memset(head, -1, sizeof(head));
for(i=0; i<m; i++){
scanf("%d %d %d", &u, &v, &w);
add(u, v, w); //以有向圖為例
//add(v, u, w); //圖為無向圖時相當於雙向連通
}
for(i=1; i<=n; i++){
printf("%d:\n", i);
//search
for(j=head[i]; j != -1; j=next[j])
printf("%d %d\n", V[j], W[j]);
}
return 0;
}
- 參考資料
-
- 1. 圖的三種存儲方式 ．博客園[引用日期2015-08-21]
