圖論 (Graph theory) 是數(shù)學的一個分支，圖是圖論的主要研究對象。圖 (Graph) 是由若干給定的頂點及連接兩頂點的邊所構(gòu)成的圖形，這種圖形通常用來描述某些事物之間的某種特定關(guān)系。頂點用于代表事物，連接兩頂點的邊則用于表示兩個事物間具有這種關(guān)系。

圖（graph）是數(shù)據(jù)結(jié)構(gòu)和算法學中最強大的框架之一。圖幾乎可以用來表現(xiàn)所有類型的結(jié)構(gòu)或系統(tǒng)，從交通網(wǎng)絡到通信網(wǎng)絡，從下棋游戲到最優(yōu)流程，從任務分配到人際交互網(wǎng)絡，圖都有廣闊的用武之地。而要進入圖論的世界，清晰、準確的基本概念是必須的前提和基礎(chǔ)。

下面對其最核心和最重要的概念作出說明。關(guān)于圖論的概念異乎尋常的多，先掌握下面最核心最重要的，足夠開展一些工作了，其它的再到實踐中不斷去理解和熟悉吧。

圖（graph）并不是指圖形圖像（image）或地圖（map）。通常來說，我們會把圖視為一種由“頂點”組成的抽象網(wǎng)絡，網(wǎng)絡中的各頂點可以通過“邊”實現(xiàn)彼此的連接，表示兩頂點有關(guān)聯(lián)。注意上面圖定義中的兩個關(guān)鍵字，由此得到我們最基礎(chǔ)最基本的2個概念，頂點（vertex）和邊（edge），如圖所示。

一、頂點（vertex）

上圖中黑色的帶數(shù)字的點就是頂點，表示某個事物或?qū)ο?。由于圖的術(shù)語沒有標準化，因此，稱頂點為點、節(jié)點、結(jié)點、端點等都是可以的。叫什么無所謂，理解是什么才是關(guān)鍵。

二、邊（edge）

上圖中頂點之間藍色的線條就是邊，表示事物與事物之間的關(guān)系。需要注意的是邊表示的是頂點之間的邏輯關(guān)系，粗細長短都無所謂的。包括上面的頂點也一樣，表示邏輯事物或?qū)ο螅嫷臅r候大小形狀都無所謂。

三、同構(gòu)（Isomorphism ）

先看看下面2張圖：

首先你的感覺是這2個圖肯定不一樣。但從圖（graph）的角度出發(fā)，這2個圖是一樣的，即它們是同構(gòu)的。前面提到頂點和邊指的是事物和事物的邏輯關(guān)系，不管頂點的位置在哪，邊的粗細長短如何，只要不改變頂點代表的事物本身，不改變頂點之間的邏輯關(guān)系，那么就代表這些圖擁有相同的信息，是同一個圖。同構(gòu)的圖區(qū)別僅在于畫法不同。

四、有向/無向圖（Directed Graph/ Undirected Graph）

最基本的圖通常被定義為“無向圖”，與之對應的則被稱為“有向圖”。兩者唯一的區(qū)別在于，有向圖中的邊是有方向性的。下圖即是一個有向圖，邊的方向分別是：(1->2), (1-> 3), (3-> 1), (1->5), (2->3), (3->4), (3->5), (4->5), (1->6), (4->6)。要注意，圖中的邊(1->3)和(3->1)是不同的。有向圖和無向圖的許多原理和算法是相通的。

五、權(quán)重（weight）

邊的權(quán)重（或者稱為權(quán)值、開銷、長度等），也是一個非常核心的概念，即每條邊都有與之對應的值。例如當頂點代表某些物理地點時，兩個頂點間邊的權(quán)重可以設(shè)置為路網(wǎng)中的開車距離。下圖中頂點為4個城市:Beijing, Shanghai, Wuhan, Guangzhou，邊的權(quán)重設(shè)置為2城市之間的開車距離。有時候為了應對特殊情況，邊的權(quán)重可以是零或者負數(shù)，也別忘了“圖”是用來記錄關(guān)聯(lián)的東西，并不是真正的地圖。

六、路徑/最短路徑（path/shortest path）

在圖上任取兩頂點，分別作為起點（start vertex）和終點（end vertex），我們可以規(guī)劃許多條由起點到終點的路線。不會來來回回繞圈子、不會重復經(jīng)過同一個點和同一條邊的路線，就是一條“路徑”。兩點之間存在路徑，則稱這2個頂點是連通的（connected）。

還是上圖的例子，北京->上海->廣州，是一條路徑，北京->武漢->廣州，是另一條路徑，北京—>武漢->上海->廣州，也是一條路徑。而北京->武漢->廣州這條路徑最短，稱為最短路徑。

路徑也有權(quán)重。路徑經(jīng)過的每一條邊，沿路加權(quán)重，權(quán)重總和就是路徑的權(quán)重（通常只加邊的權(quán)重，而不考慮頂點的權(quán)重）。在路網(wǎng)中，路徑的權(quán)重，可以想象成路徑的總長度。在有向圖中，路徑還必須跟隨邊的方向。

值得注意的是，一條路徑包含了頂點和邊，因此路徑本身也構(gòu)成了圖結(jié)構(gòu)，只不過是一種特殊的圖結(jié)構(gòu)。

七、環(huán)（loop）

環(huán)，也成為環(huán)路，是一個與路徑相似的概念。在路徑的終點添加一條指向起點的邊，就構(gòu)成一條環(huán)路。通俗點說就是繞圈。

上圖中，北京->上海->武漢->廣州->北京，就是一個環(huán)路。北京->武漢->上海->北京，也是一個環(huán)路。與路徑一樣，有向圖中的環(huán)路也必須跟隨邊的方向。環(huán)本身也是一種特殊的圖結(jié)構(gòu)。

八、連通圖/連通分量（connected graph/connected component）

如果在圖G中，任意2個頂點之間都存在路徑，那么稱G為連通圖（注意是任意2頂點）。上面那張城市之間的圖，每個城市之間都有路徑，因此是連通圖。而下面這張圖中，頂點8和頂點2之間就不存在路徑，因此下圖不是一個連通圖，當然該圖中還有很多頂點之間不存在路徑。

上圖雖然不是一個連通圖，但它有多個連通子圖：0,1,2頂點構(gòu)成一個連通子圖，0,1,2,3,4頂點構(gòu)成的子圖是連通圖，6,7,8,9頂點構(gòu)成的子圖也是連通圖，當然還有很多子圖。我們把一個圖的最大連通子圖稱為它的連通分量。0,1,2,3,4頂點構(gòu)成的子圖就是該圖的最大連通子圖，也就是連通分量。連通分量有如下特點：

（1）是子圖；

（2）子圖是連通的；

（3）子圖含有最大頂點數(shù)。

注意：“最大連通子圖”指的是無法再擴展了，不能包含更多頂點和邊的子圖。0,1,2,3,4頂點構(gòu)成的子圖已經(jīng)無法再擴展了。

顯然，對于連通圖來說，它的最大連通子圖就是其本身，連通分量也是其本身。