圖看起來就像下圖這樣：

在計算機(jī)科學(xué)中，一個圖就是一些頂點的集合，這些頂點通過一系列邊結(jié)對（連接）。頂點用圓圈表示，邊就是這些圓圈之間的連線。頂點之間通過邊連接。

注意：頂點有時也稱為節(jié)點或者交點，邊有時也稱為鏈接。

一個圖可以表示一個社交網(wǎng)絡(luò)，每一個人就是一個頂點，互相認(rèn)識的人之間通過邊聯(lián)系。

圖有各種形狀和大小。邊可以有權(quán)重（weight），即每一條邊會被分配一個正數(shù)或者負(fù)數(shù)值。考慮一個代表航線的圖。各個城市就是頂點，航線就是邊。那么邊的權(quán)重可以是飛行時間，或者機(jī)票價格。

有了這樣一張假設(shè)的航線圖。從舊金山到莫斯科最便宜的路線是到紐約轉(zhuǎn)機(jī)。

邊可以是有方向的。在上面提到的例子中，邊是沒有方向的。例如，如果 Ada 認(rèn)識 Charles，那么 Charles 也就認(rèn)識 Ada。相反，有方向的邊意味著是單方面的關(guān)系。一條從頂點 X 到 頂點 Y 的邊是將 X 聯(lián)向 Y，不是將 Y 聯(lián)向 X。

繼續(xù)前面航班的例子，從舊金山到阿拉斯加的朱諾有向邊意味著從舊金山到朱諾有航班，但是從朱諾到舊金山?jīng)]有（我假設(shè)那樣意味著你需要走回去）。

下面的兩種情況也是屬于圖：

左邊的是樹，右邊的是鏈表。他們都可以被當(dāng)成是樹，只不過是一種更簡單的形式。他們都有頂點（節(jié)點）和邊（連接）。

第一種圖包含圈（cycles），即你可以從一個頂點出發(fā)，沿著一條路勁最終會回到最初的頂點。樹是不包含圈的圖。

另一種常見的圖類型是單向圖或者 DAG：

就像樹一樣，這個圖沒有任何圈（無論你從哪一個節(jié)點出發(fā)，你都無法回到最初的節(jié)點），但是這個圖有有向邊（通過一個箭頭表示，這里的箭頭不表示繼承關(guān)系）。

為什么要使用圖？

也許你聳聳肩然后心里想著，有什么大不了的。好吧，事實證明圖是一種有用的數(shù)據(jù)結(jié)構(gòu)。

如果你有一個編程問題可以通過頂點和邊表示出來，那么你就可以將你的問題用圖畫出來，然后使用著名的圖算法（比如廣度優(yōu)先搜索 或者 深度優(yōu)先搜索）來找到解決方案。

例如，假設(shè)你有一系列任務(wù)需要完成，但是有的任務(wù)必須等待其他任務(wù)完成后才可以開始。你可以通過非循環(huán)有向圖來建立模型：

每一個頂點代表一個任務(wù)。兩個任務(wù)之間的邊表示目的任務(wù)必須等到源任務(wù)完成后才可以開始。比如，在任務(wù)B和任務(wù)D都完成之前，任務(wù)C不可以開始。在任務(wù)A完成之前，任務(wù)A和D都不能開始。

現(xiàn)在這個問題就通過圖描述清楚了，你可以使用深度優(yōu)先搜索算法來執(zhí)行執(zhí)行拓?fù)渑判颉＿@樣就可以將所有的任務(wù)排入最優(yōu)的執(zhí)行順序，保證等待任務(wù)完成的時間最小化。（這里可能的順序之一是：A, B, D, E, C, F, G, H, I, J, K）

不管是什么時候遇到困難的編程問題，問一問自己：“如何用圖來表述這個問題？”。圖都是用于表示數(shù)據(jù)之間的關(guān)系。 訣竅在于如何定義“關(guān)系”。

如果你是一個音樂家你可能會喜歡這個圖：

這些頂點來自C大調(diào)的和弦。這些邊--表示和弦之間的關(guān)系--描述了怎樣從一個和弦到另一個和弦。這是一個有向圖，所以箭頭的方向表示了怎樣從一個和弦到下一個和弦。它同時還是一個加權(quán)圖，每一條邊的權(quán)重（這里用線條的寬度來表示）說明了兩個和弦之間的強(qiáng)弱關(guān)系。如你所見，G7-和弦后是一個C和弦和一個很輕的 Am 和弦。

程序員常用的另一個圖就是狀態(tài)機(jī)，這里的邊描述了狀態(tài)之間切換的條件。下面這個狀態(tài)機(jī)描述了一個貓的狀態(tài)：

圖真的很棒。Facebook 就從他們的社交圖中賺取了巨額財富。如果計劃學(xué)習(xí)任何數(shù)據(jù)結(jié)構(gòu)，則應(yīng)該選擇圖，以及大量的標(biāo)準(zhǔn)圖算法。

頂點和邊

理論上，圖就是一堆頂點和邊對象而已，但是怎么在代碼中來描述呢？

有兩種主要的方法：鄰接列表和鄰接矩陣。

鄰接列表：在鄰接列表實現(xiàn)中，每一個頂點會存儲一個從它這里開始的邊的列表。比如，如果頂點A 有一條邊到B、C和D，那么A的列表中會有3條邊

鄰接列表只描述了指向外部的邊。A 有一條邊到B，但是B沒有邊到A，所以 A沒有出現(xiàn)在B的鄰接列表中。查找兩個頂點之間的邊或者權(quán)重會比較費時，因為遍歷鄰接列表直到找到為止。

鄰接矩陣：在鄰接矩陣實現(xiàn)中，由行和列都表示頂點，由兩個頂點所決定的矩陣對應(yīng)元素表示這里兩個頂點是否相連、如果相連這個值表示的是相連邊的權(quán)重。例如，如果從頂點A到頂點B有一條權(quán)重為 5.6 的邊，那么矩陣中第A行第B列的位置的元素值應(yīng)該是5.6：

往這個圖中添加頂點的成本非常昂貴，因為新的矩陣結(jié)果必須重新按照新的行/列創(chuàng)建，然后將已有的數(shù)據(jù)復(fù)制到新的矩陣中。

所以使用哪一個呢？大多數(shù)時候，選擇鄰接列表是正確的。下面是兩種實現(xiàn)方法更詳細(xì)的比較。

假設(shè) V 表示圖中頂點的個數(shù)，E 表示邊的個數(shù)。

“檢查相鄰性” 是指對于給定的頂點，嘗試確定它是否是另一個頂點的鄰居。在鄰接列表中檢查相鄰性的時間復(fù)雜度是O(V)，因為最壞的情況是一個頂點與每一個頂點都相連。

在 稀疏圖的情況下，每一個頂點都只會和少數(shù)幾個頂點相連，這種情況下相鄰列表是最佳選擇。如果這個圖比較密集，每一個頂點都和大多數(shù)其他頂點相連，那么相鄰矩陣更合適。

代碼：頂點和邊

先看一下邊的定義：

class Edge<T>(val from: Vertex<T>,
              val to: Vertex<T>,
              val weight: Double? = 0.toDouble()) {
}

邊包含了3個屬性 “from” 和 “to” 頂點，以及權(quán)重值。注意 Edge 對象總是有方向的。如果需要添加一條無向邊，你需要在相反方向添加一個 Edge 對象。weight 屬性是可選的，所以加權(quán)圖和未加權(quán)圖都可以用它們來描述。

Vertex 的定義：

class Vertex<T>(var data: T? = null, var index: Int = 0) {
    //val edgeList : List<EdgeList<T>> = emptyList()
    val edges: ArrayList<Edge<T>> = ArrayList()
    var visited = false
    //var distance = 0
    fun addEdge(edge: Edge<T>){
        edges.add(edge)
    }
    override fun toString(): String {
        return data.toString()
    }
}

由于是泛型定義，所以它可以存放任何類型的數(shù)據(jù)。

圖

注意：圖的實現(xiàn)方式有很多，這里給出來的只是一種可能的實現(xiàn)。你可以根據(jù)不同問題來裁剪這些代碼。例如你的邊可能不需要 weight 屬性，你也可能不需要區(qū)分有向邊和無向邊。

這里有一個簡單的圖：

我們可以用鄰接列表或者鄰接矩陣來實現(xiàn)。實現(xiàn)這些概念的類都是繼承自通用的 API AbstractGraph，所以它們可以相同的方式創(chuàng)建，但是背后各自使用不同的數(shù)據(jù)結(jié)構(gòu)。

我們來創(chuàng)建一個有向加權(quán)圖，來存儲上面的數(shù)據(jù)：

val graph = Graph<Int>()
        val v1 = graph.createVertex(1)
        val v2 = graph.createVertex(2)
        val v3 = graph.createVertex(3)
        val v4 = graph.createVertex(4)
        val v5 = graph.createVertex(5)

        graph.addDirectedEdge(fromVertex = v1, toVertex = v2, weightValue = 1.0)
        graph.addDirectedEdge(fromVertex = v2, toVertex = v3, weightValue = 1.0)
        graph.addDirectedEdge(fromVertex = v3, toVertex = v4, weightValue = 4.5)
        graph.addDirectedEdge(fromVertex = v4, toVertex = v1, weightValue = 2.8)
        graph.addDirectedEdge(fromVertex = v2, toVertex = v5, weightValue = 3.2)

        graph.printAdjacencyList()

前面我們已經(jīng)說過，如果要添加一條無向邊，需要添加兩條有向邊。對于無向圖，我們可以使用下面的代碼來替換：

        graph.addUnDirectedEdge(fromVertex = v1, toVertex = v2, weightValue = 1.0)
        graph.addUnDirectedEdge(fromVertex = v2, toVertex = v3, weightValue = 1.0)
        graph.addUnDirectedEdge(fromVertex = v3, toVertex = v4, weightValue = 4.5)
        graph.addUnDirectedEdge(fromVertex = v4, toVertex = v1, weightValue = 2.8)
        graph.addUnDirectedEdge(fromVertex = v2, toVertex = v5, weightValue = 3.2)

如果是未加權(quán)圖，weight 這個參數(shù)我們可以不用傳遞值。

鄰接列表的實現(xiàn)

為了維護(hù)鄰接列表，需要一個類（EdgeList）將邊列表映射到一個頂點。然后圖只需要簡單的維護(hù)這樣一個對象（EdgeList）的列表就可以，并根據(jù)需要修改這個列表。

class EdgeList<T> (var vertex: Vertex<T> ){
    var edges: ArrayList<Edge<T>> = ArrayList()

    fun addEdge(edge: Edge<T>){
        edges.add(edge)
    }
}

Graph 的完整實現(xiàn)：

class Graph<T>(private val vertices: ArrayList<Vertex<T>> = ArrayList(),
               private val adjacencyList: ArrayList<EdgeList<T>> = ArrayList()) {
    fun createVertex(value: T): Vertex<T> {
        val matchingVertices = vertices.filter { it.data == value }

        if (matchingVertices.isNotEmpty()) {
            return matchingVertices.last()
        }

        val vertex = Vertex(value, adjacencyList.size)
        vertices.add(vertex)
        adjacencyList.add(EdgeList(vertex))
        return vertex
    }

    fun addDirectedEdge(fromVertex: Vertex<T>, toVertex: Vertex<T>, weightValue: Double) {
        val edge = Edge(from = fromVertex,
                to = toVertex,
                weight = weightValue)

        fromVertex.addEdge(edge)
        val fromIndex = vertices.indexOf(fromVertex)
        adjacencyList[fromIndex].edges.add(edge)
    }

    fun addUnDirectedEdge(fromVertex: Vertex<T>, toVertex: Vertex<T>, weightValue: Double = 0.0) {
        addDirectedEdge(fromVertex, toVertex, weightValue)
        addDirectedEdge(toVertex, fromVertex, weightValue)

    }
    
    fun printAdjacencyList() {
        (0 until vertices.size)
                .filterNot { adjacencyList[it].edges.isEmpty() }
                .forEach { println("""${vertices[it].data} ->[${adjacencyList[it].edges.joinToString()}] """) }
    }
}

來測試一下上面的那個航線圖：

        val planeGraph = Graph<String>()
        val hk = planeGraph.createVertex("Hong Kong")
        val ny = planeGraph.createVertex("New York")
        val mosc = planeGraph.createVertex("Moscow")
        val ld = planeGraph.createVertex("London")
        val pairs = planeGraph.createVertex("Pairs")
        val am = planeGraph.createVertex("Amsterdam")
        val sf = planeGraph.createVertex("San Francisco")
        val ja = planeGraph.createVertex("Juneau Alaska")
        val tm = planeGraph.createVertex("Timbuktu")

        planeGraph.addUnDirectedEdge(hk, sf, 500.0)
        planeGraph.addUnDirectedEdge(hk,mosc,900.0)
        planeGraph.addDirectedEdge(sf, ja, 300.0)
        planeGraph.addUnDirectedEdge(sf, ny, 150.0)
        planeGraph.addDirectedEdge(mosc,ny, 750.0)
        planeGraph.addDirectedEdge(ld, mosc, 200.0)
        planeGraph.addUnDirectedEdge(ld, pairs, 70.0)
        planeGraph.addDirectedEdge(sf,pairs, 800.0)
        planeGraph.addUnDirectedEdge(pairs, tm, 250.0)
        planeGraph.addDirectedEdge(am, pairs, 50.0)

        planeGraph.printAdjacencyList()

運行結(jié)果如下：

Hong Kong ->[(San Francisco: 500.0), (Moscow: 900.0)] 
Moscow ->[(New York: 750.0)] 
London ->[(Moscow: 200.0), (Pairs: 70.0)] 
Pairs ->[(Timbuktu: 250.0)] 
Amsterdam ->[(Pairs: 50.0)] 
San Francisco ->[(Juneau Alaska: 300.0), (New York: 150.0), (Pairs: 800.0)] 

Swift 英文原版戳這里