圖是數(shù)據(jù)結(jié)構(gòu)里面的重要一章。通過圖，我們可以判斷兩個(gè)點(diǎn)之間是不是具有連通性；通過圖，我們還可以計(jì)算兩個(gè)點(diǎn)之間的最小距離是多少；通過圖，我們還可以根據(jù)不同的要求，尋找不同的合適路徑。當(dāng)然，有的時(shí)候?yàn)榱擞?jì)算的需要，我們還需要從圖中抽象出最小生成樹，這樣在遍歷計(jì)算的時(shí)候就不需要持續(xù)判斷是不是遇到了循環(huán)節(jié)點(diǎn)。當(dāng)然，這所有的一切都是從圖的表示開始的。

1）矩陣表示

矩陣表示可以說是最簡單的表示方法，如果說一個(gè)圖中有5個(gè)點(diǎn)，那么我們就可以構(gòu)建一個(gè)5*5的矩陣。如果點(diǎn)和點(diǎn)之間存在連接，那么填上1；反之如果不存在連接，那么可以用0表示，當(dāng)然對角線上面的點(diǎn)是沒有意義的。如下圖所示：

static int graph[5][5] =   
{  
    {0, 1, 0, 1, 1},  
    {1, 0, 1, 0, 1},  
    {0, 1, 0, 1, 0},  
    {1, 0, 1, 0, 1},  
    {1, 1, 0, 1, 0}  
};  

如果點(diǎn)和點(diǎn)之間還是存在方向的，那么它們關(guān)于(x，x)對稱軸就是不對稱的，所以結(jié)果也可能是這樣的：

static int graph[5][5] =   
{  
    {0, 0, 0, 0, 0},  
    {1, 0, 0, 0, 0},  
    {0, 1, 0, 0, 0},  
    {1, 0, 1, 0, 0},  
    {1, 1, 0, 1, 0}  
};  

當(dāng)然，如果點(diǎn)和點(diǎn)之間的關(guān)系存在某種權(quán)重，比如說距離，那我們可以用它來代替原來的數(shù)據(jù)1：

static int graph[5][5] =   
{  
    {0, 0, 0, 0, 0},  
    {3, 0, 0, 0, 0},  
    {0, 6, 0, 0, 0},  
    {8, 0, 4, 0, 0},  
    {9, 2, 0, 7, 0}  
}; 

矩陣表示下的圖結(jié)構(gòu)非常直觀。但是，矩陣有一個(gè)特點(diǎn)，就是比較浪費(fèi)空間。因?yàn)槲覀冞@里舉例的頂點(diǎn)比較少，只有5個(gè)，但是請大家試想一下，如果一張圖上有10000個(gè)節(jié)點(diǎn)，那么1000010000該是多大的一個(gè)空間啊。重要的是，這1000010000上面大多數(shù)點(diǎn)都是0，所以浪費(fèi)的空間是相當(dāng)可觀的。

2）數(shù)組結(jié)構(gòu)

為了改變矩陣?yán)速M(fèi)空間的特點(diǎn)，我們可以建立一個(gè)只有頂點(diǎn)和邊組成的數(shù)據(jù)空間。比如說，我們定義一個(gè)這樣的結(jié)構(gòu)：

typedef struct _LINE  
{  
    int start;  
    int end;  
    int weight;  
    int isDirection;  
}LINE; 

上面定義的數(shù)據(jù)結(jié)構(gòu)非常簡潔。第1個(gè)為起始頂點(diǎn)，第2個(gè)為終點(diǎn)，第3個(gè)為權(quán)重，第4個(gè)判斷當(dāng)前邊是否有向。圖中要是有多少邊，我們就要定義多少個(gè)這樣的數(shù)據(jù)。如果把這些邊的數(shù)據(jù)都放在一起構(gòu)成一個(gè)數(shù)組，那么我們就可以用這個(gè)數(shù)組來表示圖的全部信息了。

但是，我們還是覺得有遺憾的地方。這個(gè)數(shù)據(jù)結(jié)構(gòu)過分強(qiáng)調(diào)了邊的意義和重要性，忽略了頂點(diǎn)本身的含義。因?yàn)?，我們在?qiáng)調(diào)邊的時(shí)候，應(yīng)該添加進(jìn)頂點(diǎn)的相關(guān)特性。離開頂點(diǎn)的支持，單純的邊信息是沒有什么含義的。

3）基于頂點(diǎn)鏈表的圖表示

首先，我們定義頂點(diǎn)的基本結(jié)構(gòu)：

typedef struct _LINE  
{  
    int end;  
    int weight;  
    struct _LINE* next;  
}LINE;  

typedef struct _VECTEX  
{  
    int start;  
    int number;  
    LINE* neighbor;  
}VECTEX; 

我們用VECTEX記錄頂點(diǎn)的相關(guān)信息，LINE表示節(jié)點(diǎn)的相關(guān)信息。如果LINE是在VECTEX中的變量，那么neighbor表示當(dāng)前所有節(jié)點(diǎn)的起始點(diǎn)都是start點(diǎn)。如果它是PATH中的變量呢，那么next的起始點(diǎn)就是LINE鏈接的前面一個(gè)點(diǎn)，不知道我講清楚了沒有？下面就是點(diǎn)與點(diǎn)之間PATH的定義。

typedef struct _PATH  
{  
    int start;  
    int end;  
    int lenth;  
    LINE* next;  
}PATH; 

其中start為起始點(diǎn)，end為終結(jié)點(diǎn)，next為start鏈接的下一個(gè)點(diǎn)，lenth為路徑的總長度，當(dāng)然也可以修改成其他的權(quán)重形式。

注意事項(xiàng)：

1）數(shù)組和鏈表是圖結(jié)構(gòu)的基礎(chǔ)，朋友們應(yīng)該好好掌握

2）每一種數(shù)據(jù)結(jié)構(gòu)都有自己的應(yīng)用場合，關(guān)鍵是理解其中的思想和方法

3）圖的表示是圖運(yùn)算的基礎(chǔ)，掌握它們是我們進(jìn)一步學(xué)習(xí)的基本條件