數據結構：圖的表示

liuzhaoq18 9年前發布 | 9K 次閱讀數據結構

任何一本講到圖算法的算法書，都會講到圖的表示方法有兩種

1 鄰接矩陣，對于N個點的圖，需要N×N的矩陣表示點與點之間是否有邊的存在。這種表示法的缺點是浪費空間，尤其是對于N×N的矩陣是稀疏矩陣，即邊的數目遠遠小于N×N的時候，浪費了巨大的存儲空間

2 鄰接鏈表，對于任何一個node A，外掛一個鄰接鏈表，如果存在 A->X這樣的邊，就將X鏈入鏈表。這種表示方法的優點是節省空間，缺點是所有鏈表都存在的缺點，地址空間的不連續造成緩存命中降低，性能有不如臨界矩陣這樣的數組。

一直以來，我也是覺得，魚和熊掌不可兼得，這是無可奈何的事情。直到我看到了一份比較完美的code。他有動態分配的數組來存放鄰接節點。一起欣賞下這份代碼吧。年前我第一次看到這份代碼的時候，激動的我晚上半天睡不著覺。平時自己寫的代碼，一板一眼，雖說功能無誤，總少了那么幾分靈氣。看了C算法，也算對圖的表示方法知道一些，卻寫不出這么優美的代碼。

我以前覺得，自己大量練習聯系寫代碼是學習編程的最好的方法，是最開但是看了這份代碼后，覺得，學習前輩高人優秀的代碼，是提高自己的一條捷徑，對我們這些普通的coder而言，我們看代碼的時間是超過寫代碼的時間的。閱讀前輩優秀代碼，會更快的提升自己的編程能力。對于初學者尤其是這樣，這也是進入一個優秀的開發team的重要性，能更快的成長。

欣賞代碼Yale大學前輩的代碼吧。

#ifndef __GRAPH_H__
#define __GRAPH_H__
 
typedef struct graph *Graph;
 
Graph graph_create(int n);
void graph_destroy(Graph);
void graph_add_edge(Graph, int source, int sink);
int graph_vertex_count(Graph);
int graph_edge_count(Graph);
int graph_out_degree(Graph, int source);
int graph_has_edge(Graph, int source, int sink);
void graph_foreach(Graph g, int source,
        void (*f)(Graph g, int source, int sink, void *data),
        void *data);
 
#endif

#include <stdlib.h>
#include <assert.h>
 
#include "graph.h"
 
/* basic directed graph type */
/* the implementation uses adjacency lists
* represented as variable-length arrays */
 
/* these arrays may or may not be sorted: if one gets long enough
* and you call graph_has_edge on its source, it will be */
 
struct graph {
    int n;                                             /* number of vertices */
    int m;                                             /* number of edges */
    struct successors {
        int d;                                         /* number of successors */
        int len;                                       /* number of slots in array */
        char is_sorted;                                /* true if list is already sorted */
        int list[1];                                  
                                                       /* actual list of successors */
    } *alist[1];
};
 
/* create a new graph with n vertices labeled 0..n-1 and no edges */
Graph
graph_create(int n)
{
    Graph g;
    int i;
 
    g = malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1));
    assert(g);
 
    g->n = n;
    g->m = 0;
 
    for(i = 0; i < n; i++) {
        g->alist[i] = malloc(sizeof(struct successors));
        assert(g->alist[i]);
 
        g->alist[i]->d = 0;
        g->alist[i]->len = 1;
        g->alist[i]->is_sorted= 1;
    }
    
    return g;
}
 
/* free all space used by graph */
void
graph_destroy(Graph g)
{
    int i;
 
    for(i = 0; i < g->n; i++) free(g->alist[i]);
    free(g);
}
 
/* add an edge to an existing graph */
void
graph_add_edge(Graph g, int u, int v)
{
    assert(u >= 0);
    assert(u < g->n);
    assert(v >= 0);
    assert(v < g->n);
 
    /* do we need to grow the list? */
    while(g->alist[u]->d >= g->alist[u]->len) {
        g->alist[u]->len *= 2;
        g->alist[u] =
            realloc(g->alist[u],
                sizeof(struct successors) + sizeof(int) * (g->alist[u]->len - 1));
    }
 
    /* now add the new sink */
    g->alist[u]->list[g->alist[u]->d++] = v;
    g->alist[u]->is_sorted = 0;
 
    /* bump edge count */
    g->m++;
}
 
/* return the number of vertices in the graph */
int
graph_vertex_count(Graph g)
{
    return g->n;
}
 
/* return the number of vertices in the graph */
int
graph_edge_count(Graph g)
{
    return g->m;
}
 
/* return the out-degree of a vertex */
int
graph_out_degree(Graph g, int source)
{
    assert(source >= 0);
    assert(source < g->n);
 
    return g->alist[source]->d;
}
 
/* when we are willing to call bsearch */
#define BSEARCH_THRESHOLD (10)
 
static int
intcmp(const void *a, const void *b)
{
    return *((const int *) a) - *((const int *) b);
}
 
/* return 1 if edge (source, sink) exists), 0 otherwise */
int
graph_has_edge(Graph g, int source, int sink)
{
    int i;
 
    assert(source >= 0);
    assert(source < g->n);
    assert(sink >= 0);
    assert(sink < g->n);
 
    if(graph_out_degree(g, source) >= BSEARCH_THRESHOLD) {
        /* make sure it is sorted */
        if(! g->alist[source]->is_sorted) {
            qsort(g->alist[source]->list,
                    g->alist[source]->d,
                    sizeof(int),
                    intcmp);
        }
        
        /* call bsearch to do binary search for us */
        return
            bsearch(&sink,
                    g->alist[source]->list,
                    g->alist[source]->d,
                    sizeof(int),
                    intcmp)
            != 0;
    } else {
        /* just do a simple linear search */
        /* we could call lfind for this, but why bother? */
        for(i = 0; i < g->alist[source]->d; i++) {
            if(g->alist[source]->list[i] == sink) return 1;
        }
        /* else */
        return 0;
    }
}
 
/* invoke f on all edges (u,v) with source u */
/* supplying data as final parameter to f */
void
graph_foreach(Graph g, int source,
    void (*f)(Graph g, int source, int sink, void *data),
    void *data)
{
    int i;
 
    assert(source >= 0);
    assert(source < g->n);
 
    for(i = 0; i < g->alist[source]->d; i++) {
        f(g, source, g->alist[source]->list[i], data);
    }
}

這是一份 PineWiki 網站里面提供的一份圖的表示的代碼，實現的很優美吧？動態分配數組，長度可以擴展，既不浪費空間，有不會帶來性能損失。

除此外，graph_foreach這種思想也很不錯啊。最近學習了一段時間的Lisp，這種傳遞函數作用到每一個元素上的方法，相當于Lisp中的mapcar，讓人不僅拍案叫絕，很容易就能擴展出很好的功能。（當然也不是完全沒瑕疵，比如realloc沒有判斷失敗的情景，白璧微瑕）

既然是圖的表示，我們當然很希望能夠看到可視化的圖。我看Land of Lisp一書中，學到了Linux下的neato 命令。 Linux下有工具幫助生成圖的圖片，可以滿足我們可視化的需求。

先看下測試代碼。

#include <stdio.h>
#include <assert.h>
 
#include "graph.h"
 
#define TEST_SIZE (6)
 
static void
match_sink(Graph g, int source, int sink, void *data)
{
    assert(data && sink == *((int *) data));
}
 
static int node2dot(Graph g)
{
    assert(g != NULL);
    return 0;
}
 
static void print_edge2dot(Graph g,int source, int sink, void *data)
{
    fprintf(stdout,"%d->%d;n",source,sink);
}
static int edge2dot(Graph g)
{
    assert( NULL);
    int idx = 0;
    int node_cnt = graph_vertex_count(g);
    for(idx = 0;idx<node_cnt; idx++)
    {
        graph_foreach(g,idx,print_edge2dot,NULL);
    }
    return 0;
}
 
int graph2dot(Graph g)
{
    fprintf(stdout,"digraph{");
    node2dot(g);
    edge2dot(g);
    fprintf(stdout,"}n");
    return 0;
}
 
int main(int argc, char **argv)
{
    Graph g;
    int i;
    int j;
 
    g = graph_create(TEST_SIZE);
 
    assert(graph_vertex_count(g) == TEST_SIZE);
 
    /* check it's empty */
    for(i = 0; i < TEST_SIZE; i++) {
        for(j = 0; j < TEST_SIZE; j++) {
            assert(graph_has_edge(g, i, j) == 0);
        }
    }
 
    /* check it's empty again */
    for(i = 0; i < TEST_SIZE; i++) {
        assert(graph_out_degree(g, i) == 0);
        graph_foreach(g, i, match_sink, 0);
    }
 
    /* check edge count */
    assert(graph_edge_count(g) == 0);
 
    for(i = 0; i < TEST_SIZE; i++) {
        for(j = 0; j < TEST_SIZE; j++) {
            if(i < j) graph_add_edge(g, i, j);
        }
    }
 
 
    for(i = 0; i < TEST_SIZE; i++) {
        for(j = 0; j < TEST_SIZE; j++) {
            assert(graph_has_edge(g, i, j) == (i < j));
        }
    }
     assert(graph_edge_count(g) == (TEST_SIZE*(TEST_SIZE-1)/2));
    graph2dot(g);
    /* free it
     * */
    graph_destroy(g);
 
    return 0;
}

我們這個測試程序基本測試了graph的API，同時利用graph_foreach函數的高效擴展性，輸出了dot文件格式的文件我們看下執行結果。

root@manu:~/code/c/self/graph_2# gcc -o test generate_graph.c graph.c
root@manu:~/code/c/self/graph_2# ./test >test.dot

在我的Ubuntu下面用XDot可以看到test.dot已經是個圖形文件了。圖形如下：

當然了，我們也可以用 dot命令繪制出PNG格式的圖片來：

root@manu:~/code/c/self/graph_2# dot -T png -o graph_test.png test.dot

我們可以看到在當前目錄下產生了一個文件名為graph_test.png的PNG格式的圖片。打開看下和上面的圖是一致的。我就不貼圖了。

參考文獻：

1 Land of Lisp

2 PineWiki

3 算法：C語言實現。

來自：http://www.linuxeden.com/html/news/20161130/167045.html

本文由用戶 liuzhaoq18 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1480559110366.html

數據結構

數據結構：圖的表示

相關經驗

相關資訊

相關文檔

目錄