對于圖來說，鄰接矩陣是不錯(cuò)的一種圖存儲結(jié)構(gòu)，但是我們也發(fā)現(xiàn)，對于邊數(shù)相對頂點(diǎn)較少的圖，這種結(jié)構(gòu)是存在對存儲空間的極大浪費(fèi)的。因此我們考慮另外一種存儲結(jié)構(gòu)方式：鄰接表（Adjacency List），即數(shù)組與鏈表相結(jié)合的存儲方法。

鄰接表的處理方法是這樣的。

1、圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲，另外，對于頂點(diǎn)數(shù)組中，每個(gè)數(shù)據(jù)元素還需要存儲指向第一個(gè)鄰接點(diǎn)的指針，以便于查找該頂點(diǎn)的邊信息。

2、圖中每個(gè)頂點(diǎn)vi的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表，由于鄰接點(diǎn)的個(gè)數(shù)不定，所以用單鏈表存儲，無向圖稱為頂點(diǎn)vi的邊表，有向圖稱為頂點(diǎn)vi作為弧尾的出邊表。

例如圖7-4-6就是一個(gè)無向圖的鄰接表結(jié)構(gòu)。

?

若是有向圖，鄰接表的結(jié)構(gòu)是類似的，如圖7-4-7，以頂點(diǎn)作為弧尾來存儲邊表容易得到每個(gè)頂點(diǎn)的出度，而以頂點(diǎn)為弧頭的表容易得到頂點(diǎn)的入度，即逆鄰接表。

?

對于帶權(quán)值的網(wǎng)圖，可以在邊表結(jié)點(diǎn)定義中再增加一個(gè)weight的數(shù)據(jù)域，存儲權(quán)值信息即可，如圖7-4-8所示。

?

下面示例無向圖的鄰接表創(chuàng)建：（改編自《大話數(shù)據(jù)結(jié)構(gòu)》）

C++ Code 

#include
using  namespace std;

#define MAXVEX  100  /* 最大頂點(diǎn)數(shù),應(yīng)由用戶定義 */
typedef  char VertexType;  /* 頂點(diǎn)類型應(yīng)由用戶定義 */
typedef  int EdgeType;  /* 邊上的權(quán)值類型應(yīng)由用戶定義 */

typedef  struct EdgeNode /* 邊表結(jié)點(diǎn)  */
{
     int adjvex; /* 鄰接點(diǎn)域,存儲該頂點(diǎn)對應(yīng)的下標(biāo) */
    EdgeType weight; /* 用于存儲權(quán)值,對于非網(wǎng)圖可以不需要 */
     struct EdgeNode *next;  /* 鏈域,指向下一個(gè)鄰接點(diǎn) */
} EdgeNode;

typedef  struct VextexNode /* 頂點(diǎn)表結(jié)點(diǎn) */
{
    VertexType data; /* 頂點(diǎn)域,存儲頂點(diǎn)信息 */
    EdgeNode *firstedge; /* 邊表頭指針 */
} VextexNode, AdjList[MAXVEX];

typedef  struct
{
    AdjList adjList;
     int numNodes, numEdges;  /* 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù) */
} GraphAdjList;


void CreateALGraph(GraphAdjList *Gp)
{
     int i, j, k;
    EdgeNode *pe;
    cout <<  "輸入頂點(diǎn)數(shù)和邊數(shù)(空格分隔）:" << endl;
    cin >> Gp->numNodes >> Gp->numEdges;

     for (i =  0 ; i < Gp->numNodes; i++)
    {
        cout <<  "輸入頂點(diǎn)信息：" << endl;
        cin >> Gp->adjList[i].data;
        Gp->adjList[i].firstedge =  NULL; /* 將邊表置為空表 */
    }

     for (k =  0; k <  Gp->numEdges; k++) /* 建立邊表 */
    {
        cout <<  "輸入邊(vi,vj)的頂點(diǎn)序號i,j（空格分隔）:" << endl;
        cin >> i >> j;
        pe = (EdgeNode *)malloc( sizeof(EdgeNode));
        pe->adjvex = j; /* 鄰接序號為j */
         /* 將pe的指針指向當(dāng)前頂點(diǎn)上指向的結(jié)點(diǎn) */
        pe->next = Gp->adjList[i].firstedge;
        Gp->adjList[i].firstedge = pe; /* 將當(dāng)前頂點(diǎn)的指針指向pe */

        pe = (EdgeNode *)malloc( sizeof(EdgeNode));
        pe->adjvex = i;
        pe->next = Gp->adjList[j].firstedge;
        Gp->adjList[j].firstedge = pe;

    }
}

int main( void)
{
    GraphAdjList GL;
    CreateALGraph(&GL);

     return  0;
}

這里的鄰接點(diǎn)插入使用了單鏈表創(chuàng)建中的頭插法，對于無向圖來說，一條邊對應(yīng)都是兩個(gè)頂點(diǎn)，所以在循環(huán)中，一次就針對i和j分別進(jìn)行了插入。