存儲結構方式之鄰接表詳解

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

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

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

2、圖中每個頂點vi的所有鄰接點構成一個線性表，由于鄰接點的個數不定，所以用單鏈表存儲，無向圖稱為頂點vi的邊表，有向圖稱為頂點vi作為弧尾的出邊表。

例如圖7-4-6就是一個無向圖的鄰接表結構。

?

若是有向圖，鄰接表的結構是類似的，如圖7-4-7，以頂點作為弧尾來存儲邊表容易得到每個頂點的出度，而以頂點為弧頭的表容易得到頂點的入度，即逆鄰接表。

?

對于帶權值的網圖，可以在邊表結點定義中再增加一個weight的數據域，存儲權值信息即可，如圖7-4-8所示。

?

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

C++ Code 

#include
using  namespace std;

#define MAXVEX  100  /* 最大頂點數,應由用戶定義 */
typedef  char VertexType;  /* 頂點類型應由用戶定義 */
typedef  int EdgeType;  /* 邊上的權值類型應由用戶定義 */

typedef  struct EdgeNode /* 邊表結點  */
{
     int adjvex; /* 鄰接點域,存儲該頂點對應的下標 */
    EdgeType weight; /* 用于存儲權值,對于非網圖可以不需要 */
     struct EdgeNode *next;  /* 鏈域,指向下一個鄰接點 */
} EdgeNode;

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

typedef  struct
{
    AdjList adjList;
     int numNodes, numEdges;  /* 圖中當前頂點數和邊數 */
} GraphAdjList;


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

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

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

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