許多現實世界的問題可以使用圖演算法來解決。圖對於建模和解決現實問題很有用。例如，找到兩個城市之間的最少航班數量的問題可以使用圖來建模，其中頂點代表城市，邊代表兩個相鄰城市之間的航班​​，如下圖所示。求最小聯程航班數的問題
兩個城市之間的問題簡化為尋找圖中兩個頂點之間的最短路徑。

圖問題的研究稱為圖論。圖論由 Leonhard Euler 於 1736 年創立，當時他引入圖術語來解決著名的柯尼斯堡七橋問題。普魯士柯尼斯堡市（現為俄羅斯加里寧格勒）被普雷格爾河分開。河上有兩個島嶼。城市和島嶼由七座橋樑連接，如下圖（a）所示。問題是，一個人可以步行，每座橋只過一次，然後回到起點嗎？歐拉證明這是不可能的。

為了建立證明，歐拉首先透過消除所有街道來抽象化柯尼斯堡城市地圖，產生如上圖 (a) 所示的草圖。接下來，他將每個陸塊替換為一個點，稱為頂點或節點，並將每座橋替換為一條線，稱為邊，如圖所示上圖(b)。這種具有頂點和邊的結構稱為 圖.

看圖，我們問是否存在一條從任意頂點出發，恰好遍歷所有邊一次，並返回到起始頂點的路徑。歐拉證明，要存在這樣的路徑，每個頂點都必須有偶數條邊。因此，柯尼斯堡七橋問題無解。

圖問題通常使用演算法來解決。圖算法在電腦科學、數學、生物學、工程、經濟學、遺傳學和社會科學等各個領域都有許多應用。

基本圖形術語

圖由頂點和連接頂點的邊組成。本章不假設您具備任何圖論或離散數學的先驗知識。我們使用簡單明了的術語來定義圖表。

什麼是圖表？圖是一種數學結構，表示現實世界中實體之間的關係。例如，上圖代表城市之間的航班​​，下圖(b)代表陸地之間的橋樑。

圖由一組非空頂點（也稱為節點或點）和一組連接頂點的邊組成。為了方便起見，我們將圖形定義為 G = (V, E)，其中 V 表示一組頂點，E 表示一組邊。例如下圖的V和E如下：

V = {"西雅圖", "舊金山", "洛杉磯",
「丹佛」、「堪薩斯城」、「芝加哥」、「波士頓」、「紐約」、
「亞特蘭大」、「邁阿密」、「達拉斯」、「休士頓」}；

E = {{"西雅圖", "舊金山"},{"西雅圖", "芝加哥"},
{“西雅圖”，“丹佛”}，{“舊金山”，“丹佛”}，
...
};

圖可以是有向的，也可以是無向的。在有向圖中，每條邊都有一個方向，這表示您可以透過邊從一個頂點移動到另一個頂點。您可以使用有向圖來建模父/子關係，其中從頂點 A 到 B 的邊表示 A 是 B 的父項。下圖 (a) 顯示了有向圖。

在無向圖中，您可以在頂點之間雙向移動。下圖是無向圖。

邊可以加權也可以不加權。例如，您可以為上圖中圖表中的每條邊分配一個權重，以指示兩個城市之間的飛行時間。

圖中的兩個頂點被稱為相鄰如果它們由同一條邊連接。類似地，如果兩邊連接到同一頂點，則稱它們是相鄰。圖中連接兩個頂點的邊稱為與兩個頂點關聯。頂點的度是與其相關的邊的數量。

兩個頂點如果相鄰，則稱為鄰居。類似地，如果兩邊相鄰，則稱為 鄰居。

A 循環是將頂點連結到自身的邊。如果兩個頂點由兩條或多條邊連接，這些邊稱為平行邊。 簡單圖是沒有任何環或平行邊的圖。在完全圖中，每兩對頂點都是相連的，如下圖(b)所示。

若圖中任兩個頂點之間存在路徑，則該圖是連通的。圖G的子圖是一個圖，其頂點集是G的子集，邊集是G的子集。例如，上圖(c)的圖是上圖(b)的子圖。

假設該圖是連通且無向的。 循環是一條從某個頂點開始並在同一頂點結束的閉合路徑。如果連通圖沒有環，則它是樹。圖G的生成樹是G的連通子圖，且此子圖是包含G中所有頂點的樹。