以下内容轉自http://blog.chinaunix.net/uid-24774106-id-3505579.html
其中添加了一些個人學習過程中的注釋和繪圖,會特别标出
下述代碼均在vs2010中測試通過,成功運作
任何一本講到圖算法的算法書,都會講到圖的表示方法有兩種
1 鄰接矩陣 ,對于N個點的圖,需要N×N的矩陣表示點與點之間是否有邊的存在。這種表示法的缺點是浪費空間,尤其是對于N×N的矩陣是稀疏矩陣,即邊的數目遠遠小于N×N的時候,浪費了巨大的存儲空間。
2 鄰接連結清單,對于任何一個node A,外挂一個鄰接連結清單,如果存在 A-<X這樣的邊,就将X鍊傳入連結表。 這種表示方法的優點是節省空間,缺點是所有連結清單都存在的缺點,位址空間的不連續造成緩存命中降低,性能有不如臨界矩陣這樣的數組。
一直以來,我也是覺得,魚和熊掌不可兼得,這是無可奈何的事情。直到我看到了一份比較完美的code。他有動态配置設定的數組來存放鄰接節點。一起欣賞下這份代碼吧。年前我第一次看到這份代碼的時候,激動的我晚上半天睡不着覺。平時自己寫的代碼,一闆一眼,雖說功能無誤,總少了那麼幾分靈氣。看了C算法,也算對圖的表示方法知道一些,卻寫不出這麼優美的代碼:
我以前覺得,自己大量練習聯系寫代碼是學習程式設計的最好的方法,是最開但是看了這份代碼後,覺得,學習前輩高人優秀的代碼,是提高自己的一條捷徑,對我們這些普通的coder而言,我們看代碼的時間是超過寫代碼的時間的。閱讀前輩優秀代碼,會更快的提升自己的程式設計能力。對于初學者尤其是這樣,這也是進入一個優秀的開發team的重要性,能更快的成長。
下圖是自己畫的這份代碼的資料結構圖,可以輔助了解
#ifndef __GRAPH_H__
#define __GRAPH_H__
typedef struct graph *Graph; //這裡定義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
// Graph.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#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 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 */
};
struct graph {
int n; /* number of vertices */
int m; /* number of edges */
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 =(graph*) malloc(sizeof(struct graph) + sizeof(struct successors *) * (n-1));
//這裡是n-1而不是n的原因是graph内部已經包含了一個
//successors *alist[1]
assert(g);
g->n = n;
g->m = 0;
for(i = 0; i < n; i++) {
g->alist[i] =(successors*) 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) //添加一個節點u--->節點v 的邊
{
assert(u >= 0);
assert(u < g->n);
assert(v >= 0);
assert(v < g->n); //u,v的必須在圖的結點編号範圍内
/* do we need to grow the list? */
while(g->alist[u]->d >= g->alist[u]->len) {
g->alist[u]->len *= 2;
g->alist[u] =(successors*)
realloc(g->alist[u],
sizeof(struct successors) + sizeof(struct successors) * (g->alist[u]->len - 1));
//這裡原部落格的語句是
//sizeof(struct successors) + sizeof(struct 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);
}
}
#include "stdafx.h"
#include <assert.h>
#include <stdlib.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(g != 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);
system("pause");
return 0;
}
測試代碼中設計到dot工具的使用,轉載部落格中有相關文章可以學習,使用dot工具後,測試代碼中構造的圖是這樣的