資料結構與演算法 - 圖的鄰接表 （思想以及實現方式）
摘要：
PS：鄰接表，儲存方法跟樹的孩子連結串列示法相類似，是一種順序分配和鏈式分配相結合的 儲存結構 。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向連結串列中。圖的鄰接表儲存方式相對於鄰接矩陣比較節約空間，對於鄰接矩陣需要分別把頂點和邊（頂點之間的關係）用一維...
PS：鄰接表，儲存方法跟樹的孩子連結串列示法相類似，是一種順序分配和鏈式分配相結合的 儲存結構 。如這個表頭結點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放於表頭結點所指向的單向連結串列中。圖的鄰接表儲存方式相對於鄰接矩陣比較節約空間，對於鄰接矩陣需要分別把頂點和邊（頂點之間的關係）用一維陣列和二維陣列儲存起來。而鄰接表則是把頂點按照順序儲存到一維陣列中，然後再通過鏈式方式，把有關係的頂點下標連結到後方，咱們先不考慮權重問題，結構體定義簡單一點，當然加上權值也不難。下方看圖解釋。
鄰接表
- 有向圖
- 無向圖
逆鄰接表
- 有向圖
鄰接表實現步驟
- 結構體
- 建立圖
- 頂點和邊數，頂點需要用一維陣列儲存
- 獲取頂點的下標，因為連結結點中的index域是頂點的下標值。
- 建立結點，通過頭插法（或尾插法）把結點連結到頭結點的尾部
- 列印（遍歷方式後序介紹）
1：結構體
我們可以分為頭和表結構，如圖所示
那麼結構體就可以這樣設計
/**
* 表頭連線的表中結點定義
* */
typedef struct tableBody {
int vexIndex;//鄰接點在陣列中的位置下標
struct tableBody *nextarc;//指向下一個鄰接點的指標
} tableBody;
/**
* 表頭結點定義
* */
typedef struct tableHead {
char data;//頂點的資料域
struct tableBody *firstarc;//指向鄰接點的指標
} tableHead, *tableHeadArr;//儲存各連結串列頭結點的陣列
/**圖-鄰接表定義*/
typedef struct {
tableHead vertices[20];//圖中頂點及各鄰接點陣列
int vexnum, arcnum;//記錄圖中頂點數和邊或弧數
} LJBGraph;
2：建立表
內部註釋涵蓋了上述步驟。
void createGraph(LJBGraph *g) {
//總頂點個數，總邊數
int i, j, k;
tableBody *tb;
printf("輸入頂點數和邊數");
scanf("%d %d", &g->vexnum, &g->arcnum);//獲取頂點數和邊數
//gettchar();
for (i = 0; i < g->vexnum; i++) {
char c;
printf("輸入%d 個頂點值", (i + 1));
getchar();
scanf("%c", &c);
g->vertices[i].data = c;//獲取頂點值，
g->vertices[i].firstarc = NULL;//將邊表置為空
}
for (k = 0; k < g->arcnum; k++) {
printf("輸入a,b 在圖中有a-->b:");
getchar();
char a,b;
scanf("%c %c", &a, &b);//輸入i,j 在圖中有i-->j
tb = (tableBody *) malloc(sizeof(tableBody));
i=localIndex(g,a); //a頂點所在頂點陣列中的下標值。
j=localIndex(g,b); //b頂點所在陣列中的下標值。
tb->vexIndex = j;
tb->nextarc = g->vertices[i].firstarc;//頭插法建立邊表
g->vertices[i].firstarc = tb;//把新建的結點連結在頂點後面
/*如果為無向圖，則加入以下程式碼
e=(EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = i;
e->next = g->adjList[j].firstedge;
g->adjList[j].firstedge= e;*/
}
printfL(g);
DFSTraverse(g);
}
尋找下標值，就是普通的遍歷，在頂點陣列中遍歷返回下標。
int localIndex(LJBGraph *g,char data){
for(int i=0;i<g->vexnum;i++){
if(g->vertices[i].data == data){
return i;
}
}
printf("沒有這個字元");
return -1;
}
所得有向圖和無向圖的結構圖不一樣
3：列印
void printfL(LJBGraph *g) {
//輸出圖的資訊
printf("表為 :\n");
tableBody *p;
printf("\n");
//鄰接表不需要表標題。
int i;
for (i = 0; i < g->vexnum; i++) {
printf("%d%c\t",(i),g->vertices[i].data);//表頭結點
p = g->vertices[i].firstarc;
while (p) {
printf("%d\t", p->vexIndex);//外表結點
p = p->nextarc;//外表結點下移
}
printf("\n");
}
}
主方法
是不是程式碼很簡單，所有東西都封裝起來。
int main(void) {
LJBGraph *g;
createGraph(g);
return 0;
}
注：比較鄰接矩陣和鄰接表的區別
| 儲存結構 | 儲存方式 | 操作特性 |
| 鄰接矩陣 | 一維陣列（頂點） 二維陣列（鄰接關係） |
1：易於判定頂點是否鄰接，查頂點的鄰接點 2：插入、刪除頂點複雜 |
| 鄰接表 | 頭結點（頂點） 表結點（鄰接關係） |
1 ：易於：查詢某頂點的鄰接點，邊或弧的插入、刪除 2：判定頂點是否鄰接，比鄰接矩陣低效。 |
4：逆鄰接表
所謂逆鄰接表就是方向相反的連結到頂點後面，一看圖便知。
