圖總結之存儲結構代碼詳解

圖總結之存儲結構代碼詳解

一、圖的存儲結構

1.1 鄰接矩陣

圖的鄰接矩陣存儲方式是用兩個數組來表示圖。一個一維數組存儲圖中頂點信息，一個二維數組（鄰接矩陣）存儲圖中的邊或弧的信息。

設圖G有n個頂點，則鄰接矩陣是一個n*n的方陣，定義為：

看一個實例，下圖左就是一個無向圖。

從上面可以看出，無向圖的邊數組是一個對稱矩陣。所謂對稱矩陣就是n階矩陣的元滿足a_ij = a_{ji<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc3ViPqGjvLS0077Y1fO1xNfzyc+9x7W909LPwr3HtcTW97bUvcfP386q1uGjrNPSyc+9x7XE1Kq6zdfzz8K9x8/gttTTprXE1KrIq7a8ysfP4LXItcShozxicj4KPC9wPgo8cD4KICAgILTT1eK49r7Y1fPW0KOsutzI3dLX1qq1wM281tC1xNDFz6Khozxicj4KPC9wPgo8cD4KICAgIKOoMaOp0qrF0LbPyM7S4sG9tqW148rHt/HT0LHfzt6x377NutzI3dLXwcujuzxicj4KPC9wPgo8cD4KICAgIKOoMqOp0qrWqrXAxLO49ralteO1xLbIo6zG5Mq1vs3Kx9XiuPa2pbXjdmnU2sHavdO+2NXz1tC12mnQ0Lvyo6i12mnB0KOptcTUqsvY1q66zaO7PGJyPgo8L3A+CjxwPgogICAgo6gzo6nH87alteN2abXEy/nT0MHavdO1477Nyse9q77Y1fPW0LXaadDQ1KrL2Mmow+jSu7Hpo6xhcmNbaV1bal3OqjG+zcrHwdq907Xjo7s8L3A+CjxwPgogICAgtvjT0M/yzby9sr6/yOu2yLrNs/a2yKOstqW143ZptcTI67bIzqoxo6zV/brDyse12mnB0Lj3yv3WrrrNoaO2pbXjdmm1xLP2tsjOqjKjrLy0tdpp0NC1xLj3yv3WrrrNoaM8YnI+CjwvcD4KPHA+CiAgICDI9M28R8rHzfjNvKOs09BuuPa2pbXjo6zU8sHavdO+2NXzysfSu7j2biputcS3vdXzo6y2qNLlzqqjujxicj4KPC9wPgo8cD4KICAgIDxpbWcgc3JjPQ=="http://www.2cto.com/uploadfile/Collfiles/20141117/20141117090117363.png" width="362" height="71" alt="\">}

這裡的w_ij表示(v_i,v_j)上的權值。無窮大表示一個計算機允許的、大於所有邊上權值的值，也就是一個不可能的極限值。下面左圖就是一個有向網圖，右圖就是它的鄰接矩陣。

那麼鄰接矩陣是如何實現圖的創建的呢？代碼如下。（有向圖）

#include 
typedef char VertexType;                //頂點類型
typedef int EdgeType;                   //邊權值類型
#define INF    65535               //用65535來代表無窮大
typedef struct
{
    VertexType vexs[MAXVEX];            //頂點表
    EdgeType   arc[MAXVEX][MAXVEX];         //鄰接矩陣，可看作邊
    int numVertexes, numEdges;      //圖中當前的頂點數和邊數
}Graph;

void CreateGraph(Graph *G)
{
	int i,j,k,w;
	printf("輸入頂點數和邊數：\n");
	scanf("%d%d",&G->numVertexes,&G->numEdges);
	getchar();
	printf("輸入%d個頂點符號：\n",G->numVertexes);
	for(i=0;inumVertexes;i++)
		scanf("%c",&G->vexs[i]);
	getchar();
	for(i=0;inumVertexes;i++)
		for(j=0;jnumVertexes;j++)
			G->arc[i][j]=INF;
		for(k=0;k<2*G->numEdges;k++)//關於循環次數無向圖G->numEdges次，有向圖G->numEdges*2次
		{
			printf("輸入邊(vi,vj)上的下標i,j和權w:");//如果是有向圖，就按照方向輸入下標
			scanf("%d%d%d",&i,&j,&w);
			
			
			G->arc[i][j]=w;
			G->arc[j][i]=G->arc[i][j];//有向圖去掉這句
		}
}

//打印圖
void printGraph(Graph g)
{
    int i, j;
    for(i = 0; i < g.numVertexes; i++)
    {
        for(j = 0; j < g.numVertexes; j++)
        {
            printf("%d  ", g.arc[i][j]);
        }
        printf("\n");
    }
}

int main()
{
    Graph g;
	
    //鄰接矩陣創建圖
    CreateGraph(&g);
    printGraph(g);
    return 0;
}

測試數據：

4 6
ABCD
0 1 8
0 2 7
0 3 65535
1 0 65535
1 2 4
1 3 65535
2 0 65535
2 1 65535
2 3 2
3 0 5
3 1 3
3 2 65535

輸出：

1.2 鄰接表

鄰接矩陣是不錯的一種圖存儲結構，但是，對於邊數相對頂點較少的圖，這種結構存在對存儲空間的極大浪費。因此，找到一種數組與鏈表相結合的存儲方法稱為鄰接表。

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

（1）圖中頂點用一個一維數組存儲，當然，頂點也可以用單鏈表來存儲，不過，數組可以較容易的讀取頂點的信息，更加方便。

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

例如，下圖就是一個無向圖的鄰接表的結構。

從圖中可以看出，頂點表的各個結點由data和firstedge兩個域表示，data是數據域，存儲頂點的信息，firstedge是指針域，指向邊表的第一個結點，即此頂點的第一個鄰接點。邊表結點由adjvex和next兩個域組成。adjvex是鄰接點域，存儲某頂點的鄰接點在頂點表中的下標，next則存儲指向邊表中下一個結點的指針。

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

對於鄰接表結構，圖的建立代碼如下。（無向圖）

#include 
#define MAXVEX 1000         //最大頂點數
typedef char VertexType;        //頂點類型
typedef int EdgeType;           //邊上權值類型

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

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

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

//建立圖的鄰接表結構
void CreateGraph(GraphList *g)
{
    int i, j, k;
    EdgeNode *e;
    printf("輸入頂點數和邊數:\n");
    scanf("%d%d", &g->numVertexes, &g->numEdges);
	getchar();
    for(i = 0; i numVertexes; i++)
    {
        printf("請一次一個輸入頂點%d:\n", i);
		scanf("%c",&g->adjList[i].data);          //輸入頂點信息
		getchar();
        g->adjList[i].firstedge = NULL;          //將邊表置為空表
		
    }
	g->adjList[i].firstedge = NULL; 
    //建立邊表
    for(k = 0; k < g->numEdges; k++)//關於鄰接表的循環次數無向圖與與有向圖都是g->numEdges次
    {
        printf("輸入無向圖邊(vi,vj)上的頂點序號和權值:\n");
		int w;
		scanf("%d%d%d",&i,&j,&w);
		e =new EdgeNode;
		
        e->adjvex = j;        //鄰接序號為j
        e->weigth = w;        //邊的權值
        e->next = g->adjList[i].firstedge;//將e指針指向當前頂點指向的結構
        g->adjList[i].firstedge = e;//將當前頂點的指針指向e
		
        e = new EdgeNode;
		
        e->adjvex =i;
		e->weigth = w;        //邊的權值
        e->next = g->adjList[j].firstedge;
        g->adjList[j].firstedge = e;
	}
}

void printGraph(GraphList *g)
{
    int i = 0;
	
    while(g->adjList[i].firstedge != NULL && i < MAXVEX)
    {
        printf("頂點:%c\n", g->adjList[i].data);
        EdgeNode *e = NULL;
        e = g->adjList[i].firstedge;
        while(e != NULL)
        {
			if(e->adjvex!=i)
            printf("鄰接點下標:%d  邊:<%c,%c>  weigth: %d\n", e->adjvex,g->adjList[i].data,g->adjList[e->adjvex].data,e->weigth);
            e = e->next;
        }
        i++;
        printf("\n");
    }
}

int main(int argc, char **argv)
{
    GraphList g;
    CreateGraph(&g);
    printGraph(&g);
    return 0;
}

測試數據：

4 6
A
B
C
D
0 2 5
0 3 7
1 0 8
2 1 3
2 3 2
3 1 4

輸出：

1.3 十字鏈表

對於有向圖來說，鄰接表是有缺陷的。關心了出度問題，想了解入度就必須要遍歷整個圖才知道，反之，逆鄰接表解決了入度卻不了解出度情況。下面介紹的這種有向圖的存儲方法：十字鏈表，就是把鄰接表和逆鄰接表結合起來的。

重新定義頂點表結點結構，如下所示。

其中firstin表示入邊表頭指針，指向該頂點的入邊表中第一個結點，firstout表示出邊表頭指針，指向該頂點的出邊表中的第一個結點。

重新定義邊表結構，如下所示。

其中，tailvex是指弧起點在頂點表的下表，headvex是指弧終點在頂點表的下標，headlink是指入邊表指針域，指向終點相同的下一條邊，taillink是指邊表指針域，指向起點相同的下一條邊。如果是網，還可以增加一個weight域來存儲權值。

比如下圖，頂點依然是存入一個一維數組，實線箭頭指針的圖示完全與鄰接表相同。就以頂點v₀來說，firstout指向的是出邊表中的第一個結點v₃。所以，v₀邊表結點hearvex = 3，而tailvex其實就是當前頂點v₀的下標0，由於v₀只有一個出邊頂點，所有headlink和taillink都是空的。

重點需要解釋虛線箭頭的含義。它其實就是此圖的逆鄰接表的表示。對於v₀來說，它有兩個頂點v₁和v₂的入邊。因此的firstin指向頂點v1的邊表結點中headvex為0的結點，如上圖圓圈1。接著由入邊結點的headlink指向下一個入邊頂點v₂，如上圖圓圈2。對於頂點v₁，它有一個入邊頂點v₂，所以它的firstin指向頂點v₂的邊表結點中headvex為1的結點，如上圖圓圈3。

十字鏈表的好處就是因為把鄰接表和逆鄰接表整合在一起，這樣既容易找到以v為尾的弧，也容易找到以v為頭的弧，因而比較容易求得頂點的出度和入度。

而且除了結構復雜一點外，其實創建圖算法的時間復雜度是和鄰接表相同的，因此，在有向圖應用中，十字鏈表是非常好的數據結構模型。

這裡就介紹以上三種存儲結構，除了第三種存儲結構外，其他的兩種存儲結構比較簡單。