【 聲明：版權所有，歡迎轉載，請勿用於商業用途。 聯系信箱：feixiaoxing @163.com】
圖是數據結構裡面的重要一章。通過圖，我們可以判斷兩個點之間是不是具有連通性；通過圖，我們還可以計算兩個點之間的最小距離是多少；通過圖，我們還可以根據不同的要求，尋找不同的合適路徑。當然，有的時候為了計算的需要，我們還需要從圖中抽象出最小生成樹，這樣在遍歷計算的時候就不需要持續判斷是不是遇到了循環節點。當然，這所有的一切都是從圖的表示開始的。
1）矩陣表示
矩陣表示可以說是最簡單的表示方法，如果說一個圖中有5個點，那麼我們就可以構建一個5*5的矩陣。如果點和點之間存在連接，那麼填上1；反之如果不存在連接，那麼可以用0表示，當然對角線上面的點是沒有意義的。如下圖所示：
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}
};
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}
}; 如果點和點之間還是存在方向的，那麼它們關於(x，x)對稱軸就是不對稱的，所以結果也可能是這樣的：
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}
};
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}
}; 當然，如果點和點之間的關系存在某種權重，比如說距離，那我們可以用它來代替原來的數據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}
};
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}
};
矩陣表示下的圖結構非常直觀。但是，矩陣有一個特點，就是比較浪費空間。因為我們這裡舉例的頂點比較少，只有5個，但是請大家試想一下，如果一張圖上有10000個節點，那麼10000*10000該是多大的一個空間啊。重要的是，這10000*10000上面大多數點都是0，所以浪費的空間是相當可觀的。
2）數組結構
為了改變矩陣浪費空間的特點，我們可以建立一個只有頂點和邊組成的數據空間。比如說，我們定義一個這樣的結構：
typedef struct _LINE
{
int start;
int end;
int weight;
int isDirection;
}LINE;
typedef struct _LINE
{
int start;
int end;
int weight;
int isDirection;
}LINE; 上面定義的數據結構非常簡潔。第1個為起始頂點，第2個為終點，第3個為權重，第4個判斷當前邊是否有向。圖中要是有多少邊，我們就要定義多少個這樣的數據。如果把這些邊的數據都放在一起構成一個數組，那麼我們就可以用這個數組來表示圖的全部信息了。
但是，我們還是覺得有遺憾的地方。這個數據結構過分強調了邊的意義和重要性，忽略了頂點本身的含義。因為，我們在強調邊的時候，應該添加進頂點的相關特性。離開頂點的支持，單純的邊信息是沒有什麼含義的。
3）基於頂點鏈表的圖表示
首先，我們定義頂點的基本結構：
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;
typedef struct _VECTEX
{
int start;
int number;
LINE* neighbor;
}VECTEX;
typedef struct _LINE
{
int end;
int weight;
struct _LINE* next;
}LINE;
typedef struct _VECTEX
{
int start;
int number;
LINE* neighbor;
}VECTEX; 我們用VECTEX記錄頂點的相關信息，LINE表示節點的相關信息。如果LINE是在VECTEX中的變量，那麼neighbor表示當前所有節點的起始點都是start點。如果它是PATH中的變量呢，那麼next的起始點就是LINE鏈接的前面一個點，不知道我講清楚了沒有？下面就是點與點之間PATH的定義。
typedef struct _PATH
{
int start;
int end;
int lenth;
LINE* next;
}PATH;
typedef struct _PATH
{
int start;
int end;
int lenth;
LINE* next;
}PATH; 其中start為起始點，end為終結點，next為start鏈接的下一個點，lenth為路徑的總長度，當然也可以修改成其他的權重形式。
注意事項：
1）數組和鏈表是圖結構的基礎，朋友們應該好好掌握
2）每一種數據結構都有自己的應用場合，關鍵是理解其中的思想和方法
3）圖的表示是圖運算的基礎，掌握它們是我們進一步學習的基本條件
