紙上談兵: 圖 (graph) - vamei－IT工程師數位筆記本

文章出處

作者：Vamei 出處：http://www.cnblogs.com/vamei 歡迎轉載，也請保留這段聲明。謝謝！

圖(graph)是一種比較松散的數據結構。它有一些節點(vertice)，在某些節點之間，由邊(edge)相連。節點的概念在樹中也出現過，我們通常在節點中儲存數據。邊表示兩個節點之間的存在關系。在樹中，我們用邊來表示子節點和父節點的歸屬關系。樹是一種特殊的圖，但限制性更強一些。

這樣的一種數據結構是很常見的。比如計算機網絡，就是由許多節點(計算機或者路由器)以及節點之間的邊(網線)構成的。城市的道路系統，也是由節點(路口)和邊(道路)構成的圖。地鐵系統也可以理解為圖，地鐵站可以認為是節點。基于圖有許多經典的算法，比如求圖中兩個節點的最短路徑，求最小伸展樹等。

圖的經典研究是柯尼斯堡七橋問題(Seven Bridges of Königsberg)。柯尼斯堡是現今的加里寧格勒，城市中有一條河流過，河中有兩個小島。有七座橋橋連接河的兩岸和兩個小島。送信員總想知道，有沒有一個辦法，能不重復的走過7個橋呢？

(這個問題在許多奧數教材中稱為"一筆畫"問題)

歐拉時代的柯尼斯堡地圖

柯尼斯堡的可以看作由7個邊和4個節點構成的一個圖:

這個問題最終被歐拉巧妙的解決。七橋問題也啟發了一門新的數學學科——圖論(graph theory)的誕生。歐拉的基本思路是，如果某個節點不是起點或者終點，那么連接它的邊的數目必須為偶數個(從一個橋進入，再從另一個橋離開)。對于柯尼斯堡的七橋，由于4個節點都為奇數個橋，而最多只能有兩個節點為起點和終點，所以不可能一次走完。

圖的定義

嚴格的說，圖[$G = (V, E)$]是由節點的集合V和邊的集合E構成的。一個圖的所有節點構成一個集合[$V$]。一個邊可以表示為[$(v_1, v_2)$]，其中[$v_1, v_2 \in V$]，即兩個節點。如果[$(v_1, v_2)$]有序，即[$(v_1, v_2)$]與[$(v_2, v_1)$]不同，那么圖是有向的(directed)。有序的邊可以理解為單行道，只能沿一個方向行進。如果[$(v_1, v_2)$]無序，那么圖是無向的(undirected)。無序的邊可以理解成雙向都可以行進的道路。一個無序的邊可以看作連接相同節點的兩個反向的有序邊，所以無向圖可以理解為有向圖的一種特殊情況。

(七橋問題中的圖是無向的。城市中的公交線路可以是無向的，比如存在單向環線)

圖的一個路徑(path)是圖的一系列節點[$w_1, w_2, ..., w_n$]，且對于[$1 \le i < n $]，有[$ (w_i, w_{i+1}) \in E$]。也就是說，路徑是一系列的邊連接而成，路徑的兩端為兩個節點。路徑上邊的總數稱為路徑的長度。乘坐地鐵時，我們會在選擇某個路徑，來從A站到達B站。這樣的路徑可能有不止一條，我們往往會根據路徑的長度以及沿線的擁擠狀況，來選擇一條最佳的路線。如果存在一條長度大于0的路徑，該路徑的兩端為同一節點，那么認為該圖中存在環路(cycle)。很明顯，上海的地鐵系統中存在環路。

找到一條環路

如果從每個節點，到任意一個其它的節點，都有一條路徑的話，那么圖是連通的(connected)。對于一個有向圖來說，這樣的連通稱為強連通(strongly connected)。如果一個有向圖不滿足強連通的條件，但將它的所有邊都改為雙向的，此時的無向圖是連通的，那么認為該有向圖是弱連通(weakly connected)。

如果將有火車站的城市認為是節點，鐵路是連接城市的邊，這樣的圖可能是不連通的。比如北京和費城，北京有鐵路通往上海，費城有鐵路通往紐約，但北京和費城之間沒有路徑相連。

圖的實現

一種簡單的實現圖的方法是使用二維數組。讓數組a的每一行為一個節點，該行的不同元素表示該節點與其他節點的連接關系。如果[$(u, v) \in E$]，那么a[u][v]記為1，否則為0。比如下面的一個包含三個節點的圖:

可以簡單表示為

a	1	2	3
1	0	1	1
2	0	0	0
3	0	1	0

這種實現方式所占據的空間為[$O(|V|^2)$]，[$|V|$]為節點總數。所需內存隨著節點增加而迅速增多。如果邊不是很密集，那么很多數組元素記為0，只有稀疏的一些數組元素記為1，所以并不是很經濟。

更經濟的實現方式是使用鄰接表(adjacency list)，即記錄每個節點所有的相鄰節點。對于節點m，我們建立一個鏈表。對于任意節點k，如果有[$(m, k) \in E$]，就將該節點放入到對應節點m的鏈表中。鄰接表是實現圖的標準方式。比如下面的圖，

可以用如下的數據結構實現：

左側為一個數組，每個數組元素代表一個節點，且指向一個鏈表。該鏈表包含有該數組元素所有的相鄰元素。

總體上看，鄰接表可以分為兩部分。鄰接表所占據的總空間為[$O(|V| + |E|)$]。數組部分儲存節點信息，占據[$|V|$])的空間，即節點的總數。鏈表存儲邊的信息，占據[$|E|$]的空間，即邊的總數。在一些復雜的問題中，定點和邊還可能有其他的附加信息，我們可以將這些附加信息儲存在相應的節點或者邊的位置。

下面為具體的C代碼:

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 5

typedef struct node *position;

/* node */
struct node {
    int element;
    position next;
};

/* 
 * operations (stereotype)
 */
void insert_edge(position, int, int);
void print_graph(position graph, int nv);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    int i;

    // initialize the vertices
    for(i=1; i<NUM_V; i++) {
        (graph+i)->element = i;
        (graph+i)->next    = NULL;
    }

    // insert edges
    insert_edge(graph,1,2);
    insert_edge(graph,1,4);
    insert_edge(graph,3,2);
    insert_edge(graph,4,2);
    insert_edge(graph,4,3);

    print_graph(graph,NUM_V);
}

/* print the graph */
void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=1; i<nv; i++) {
        p = (graph + i)->next;
        printf("From %3d: ", i);
        while(p != NULL) {
            printf("%d->%d; ", i, p->element);
            p = p->next;
        }
        printf("\n");
    }
}

/*
 * insert an edge
 */
void insert_edge(position graph,int from, int to)
{
    position np;
    position nodeAddr;

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    np->next = nodeAddr;
}