1. 鄰接表概念

鄰接表（Adjacency List）顧名思義，就是通過鏈表或者利用數(shù)組模擬鏈表的方式將圖的相連接關(guān)系表示的一種方法，存儲方法跟樹的孩子鏈表示法相類似，是一種順序分配和鏈式分配相結(jié)合的存儲結(jié)構(gòu)。如這個表頭結(jié)點所對應的頂點存在相鄰頂點，則把相鄰頂點依次存放于表頭結(jié)點所指向的單向鏈表中。

如圖：

(如圖為一個圖關(guān)系)

例圖展示了一個圖狀關(guān)系，結(jié)點1指向2和3，2可以指向4和5，而3指向4……這樣的指向表示該圖是單向的，意思是只允許1到2而不允許2到1（除非有兩個箭頭相互指向），那么，依據(jù)這個指向關(guān)系，可以得到鄰接表如下：

（如圖為該圖所表示的鄰接表）

這里必須要特別注意鄰接表的結(jié)尾以空或者一個特殊的標記，表示到達結(jié)尾。在一些需要快速表達概念的場合，可以將空結(jié)點的指向忽略不表達。

那么如果是雙向圖，意思是1與2聯(lián)通，可以由1走向2，同時也可以由2走向1的情況時，這張表又是如下表示

可以見的，這雙向圖和單向圖的鄰接表表達方式是不一樣的，雙向圖還要將聯(lián)通方式表達，1聯(lián)通2，在1結(jié)點的連接關(guān)系中要將2結(jié)點加入以表達1能夠走向2，此外還需要再2結(jié)點中將1結(jié)點加入以表達2能夠走向1，這可能會稍微顯得麻煩但是確是值得的代價。

具體表達就是：n個頂點e條邊的無向圖的鄰接表表示中有n個頂點表結(jié)點和2e個邊表結(jié)點。(換句話說，每條邊（i,j）在鄰接表 中出現(xiàn)兩次：一次在關(guān)于i的鄰接表中，另一次在關(guān)于j的鄰接表中)。

觀察上面兩個圖，連接到空結(jié)點的那一條邊不算，那么雙向圖的邊正好就是單向圖的兩倍。

2. 鄰接表的特點

在表達鄰接表的適用情況時，我們首先要與鄰接矩陣進行相互比較

鄰接矩陣存在以下缺點

a) 浪費空間—— 存稀疏圖（點很多而邊很少）有大量無效元素

b) 浪費時間—— 統(tǒng)計稀疏圖中一共有多少條邊

恨明顯，使用矩陣的方式，僅僅是讓我們?nèi)祟惛又庇^的觀察圖的關(guān)系而已，對于稀疏圖（即結(jié)點很多但是邊很少的圖，或者表達為弱連接圖）而言時間和空間的浪費還是很大的，鄰接表就相當于是一種改良，對于稀疏圖能夠很好的適應，使用較少的空間和時間就能表達。

在常規(guī)情況下，鄰接表是O(n+e)的復雜程度（n表示節(jié)點數(shù)，e表示邊長），臨界矩陣則是O(n^2)的復雜程度。

3. 代碼構(gòu)成

設(shè)計思路并不唯一，甚至你可以利用結(jié)構(gòu)體數(shù)組進行模擬，本代碼僅提供一份適用指針的單向圖C++設(shè)計代碼，思路是：將節(jié)點的adjvex賦值為v，指向下一條邊的指針賦值為NULL輸入之后判斷圖中的起始頂點指向的第一條邊的指針是否為空假如為空那么將當前頂點的firstarc指針指向這個節(jié)點加入不為空那么調(diào)用插入到鏈表中的insertNode方法，遍歷鏈表將節(jié)點插入到鏈表的最后面。

#include<stdio.h>
#include<iostream>
#include<malloc.h>
#define maxSize 1000         
using namespace std;
typedef struct ArcNode {
    int adjvex;
    struct ArcNode *nextarc;
} ArcNode;
 
typedef struct {
    int data;
    ArcNode *firstarc;
} Vnode;
 
//可以利用結(jié)構(gòu)體整體結(jié)構(gòu)，也可以拆分結(jié)構(gòu)體變?yōu)閱为毸阉?
typedef struct {
    Vnode adjlist[maxSize];
    int n, e;
} AGraph;
 
AGraph *graph;
 
//插入鏈表末尾
void  insertNode(ArcNode *node, ArcNode *newNode) {
    ArcNode *p = node;
    while(p->nextarc != NULL) {
        p = p->nextarc;
    }
    p->nextarc = newNode;
}
 
void create() {
    graph = (AGraph*)malloc(sizeof(AGraph));
    cout << "輸入頂點的數(shù)目: " << endl;
    cin >> graph->n;
    cout << "輸入圖中邊的數(shù)目: " << endl;
    cin >> graph->e;
 
    int u = -1, v = -1;
    for(int i = 0; i < graph->n; i++) {
        graph->adjlist[i].firstarc = NULL;
    }
 
    ArcNode *node;
    for(int i = 0; i < graph->e; i++) {
        cout<<"請輸入聯(lián)通點A與B"<<endl;
        cin >> u >> v ;
        node = (ArcNode *)malloc(sizeof(ArcNode));
        node->adjvex = v;
        node->nextarc = NULL;
        graph->adjlist[u].data = u;
        if(graph->adjlist[u].firstarc == NULL) {
            //邊
            graph->adjlist[u].firstarc = node;
        } else {
            //插入邊
            insertNode(graph->adjlist[u].firstarc, node);
        }
    }
}
 
void  travseTree() {
    for(int i = 0; i < graph->n; i++) {
        if(graph->adjlist[i].firstarc != NULL) {
            cout <<"與"<< i << "連接的點有：";
            ArcNode *p = graph->adjlist[i].firstarc;
            while(p != NULL) {
                cout << p->adjvex <<  " ";
                p = p->nextarc;
            }
            cout << endl;
        }
    }
}
 
int main(void) {
    create();
    travseTree();
    return 0;
}