第2章
圖論
早上鬧鐘響起，你睜開惺忪的睡眼伸手去拿手機。關掉鬧鈴的時候，你看到了2條通知。有15個人給你昨晚的推特點了贊，美滋滋，仔細一看，又有3人轉發，這可真是棒極了。你的“瞬間網紅”體驗就是圖論的神奇力量（見圖2-1）。
熱愛工作的你沖向地鐵站，趕在車門關上前一瞬間擠了進去。開車了，美好的一天又開始了。
車門開開關關，乘客上上下下。你在換乘站換乘了另一條線路，然後又走了兩站，如圖2-2所示：
就在你坐着扶梯快要出站的時候，電話響了，是你可愛的妹妹。她說她想去參加下個月爺爺的八十大壽，想買火車票。這個時候你想到既然是爺爺的大壽，那親戚朋友肯定少不了。于是你的腦海裡就規劃出了另一個圖形：家譜（見圖2-3）。
後來，你開始留意各處的圖形。社交媒體、交通路線圖和電話本到處都是它們的身影。大到宇宙中的星座，小到自然界的分子構成，圖形無處不在（見圖2-4和圖2-5）。
圖形可以清楚地表示項目、人員、想法或資料等之間的關系。那麼圖形的概念又從何而來呢？為了了解這一點，我們來追根溯源一番，了解一下圖論和它的數學起源。
學習GraphQL實際上并不需要了解任何圖論知識。但是我們認為探究這些概念背後的曆史是很有趣的。
圖論相關詞彙
顧名思義，圖論是對圖形的研究。圖論是用來表示互相連接配接的對象的集合。你可以将圖形看作一個對象，它包含資料點（data point）和連接配接（connection）。在計算機科學中，圖形常用來描述資料網絡。常見的圖形結構見圖2-6。
如圖2-6所示，該圖形由表示資料點的四個圓組成。在圖論術語中，這些圓被稱為節點（node）或頂點（vertice）。這些節點之間的線或連接配接則被稱為邊（edge），圖2-6中有5條邊。注1
這樣我們可以列一個等式：G = (V, E)。
讓我們從最簡單的縮寫開始，G代表圖形，V代表一組頂點或節點。就圖2-6來說，V将等于以下内容：
V = {1, 2, 3, 4} E代表一組邊。通常采用一對節點代表一條邊。
E = { {1, 2},
{1, 3},
{1, 4},
{2, 4},
{3, 4} } 那麼如果我們将這個邊集合重新排序會發生什麼呢？舉例如下：
E = { {4, 3},
{4, 2},
{4, 1},
{3, 1},
{2, 1} } 在這種情況下，圖形沒有發生任何變化，如圖2-7所示。
方程依然表示這個圖形，因為節點之間不存在方向和層次結構。在圖論當中，我們稱之為無向圖（undirected graph）。邊或資料點之間的連接配接就被稱為無序對（unordered pair）。
當你開始周遊或通路這個圖的不同節點時，可以從任意位置開始和結束，并向任意方向移動。資料并不遵循明顯的順序，是以無向圖是一種非線性資料結構。接下來，介紹另一種類型的圖，有向圖（directed graph），如圖2-8所示。
節點數相同，而邊卻有所不同。連接配接它們的不是線，而是箭頭。該圖中的節點之間存在方向或流。為了表示它，我們使用以下形式：
V = {1, 2, 3, 4}
E = ( {1, 2},
{1, 3}
{3, 4} ) 總之，方程就可以表示為：
G = ( {1, 2, 3, 4},
({1, 2}, {1, 3}, {3, 4}) ) 請注意，我們用圓括号将這些資料對包裹起來，而沒有采用花括号。圓括号表示這些邊是有序對。無論什麼時候，隻要邊是有序對，那麼這個圖就是一個有向圖。如果我們對這些有向圖進行重新排列會發生什麼呢？會和無向圖一樣嗎？
G = ( {1, 2, 3, 4},
( {4, 3}, {3, 1}, {1, 2} ) ) 結果顯示，以節點4作為根節點的情況下，圖形與原來相比有了很大的不同，見圖2-9。
這時如果要周遊該圖，那麼就需要從節點4開始，然後按照箭頭的方向依次通路圖形的每個節點。為了更容易了解周遊，需要描繪從一個節點到另一個節點的實體路徑。實際上，實體路徑正是圖論概念産生的原因。
圖論的曆史
對圖論的研究可追溯到1735年的普魯士柯尼斯堡（現俄羅斯加裡甯格勒州首府）。該鎮位于普雷格爾河（Pregel River）上，是一個航運樞紐，有兩個大島通過七座橋連接配接了四塊主要陸地，如圖2-10所示。
柯尼斯堡（Konigsberg）是一座美麗的小鎮，鎮上的人們喜歡在橋上散步歡度周末。一直以來，鎮上的居民糾結于怎樣才能在不經過同一座橋的情況下，依次跨越七座橋。他們走遍小鎮試圖走過每個島嶼，想盡一切辦法不重複經過任一座橋梁，可每次都失敗了。萬般無奈之下，他們拜訪了萊昂哈德 "歐拉（Leonhard Euler）。大名鼎鼎的歐拉是一位多産的瑞士數學家，他一生出版和發表了500多部書籍和論文。
天才很忙，歐拉并不關心那些看起來微不足道的問題。但在多想了一會兒之後，他發現這個問題并不簡單，随即也和鎮上的居民一樣對它産生了興趣并想要真正搞清楚。歐拉沒有寫下所有可能的路徑，而是決定檢視陸地之間的7座橋梁，如圖2-11所示。
接下來他将其簡化，把橋梁和陸地繪制成後來被稱為圖的圖形，如圖2-12所示。
根據圖2-12，A和B是由一條邊相連接配接的相鄰節點。通過這些邊，我們可以計算出每個節點的度數（degree）。節點的度數等于連接配接該節點的邊的數量。如果我們檢視七橋問題中的節點，就會發現每個節點的度數都是奇數。
A有5條邊連接配接相鄰節點（奇數），B、C、D各有3條邊連接配接相鄰節點（奇數）。
因為每個節點的度數都是奇數，歐拉發現不重複經過每座橋是不可能的。一言以蔽之：如果你通過一座橋去一個島，那麼就必須通過另一座橋離開。你說你不想重複經過同一座橋，抱歉，不存在的。
如今，我們把每條邊隻能通路一次的圖稱為歐拉路徑（Eulerian path）。通過證明，無向圖擁有兩個奇數度的節點，或者所有節點都是偶數度。我們來看看兩個奇數度節點的情況（見圖2-13）。
另一個與歐拉相關的概念是環路或歐拉循環（Eulerian cycle）。這種情況是，起始點和結束點相同。每條邊隻經過一次，但起始點又是結束點（見圖2-14）。
柯尼斯堡七橋問題成為圖論的第一個定理。歐拉不僅被尊為圖論的鼻祖，而且創造了常數e和虛數機關i，甚至變量x之于函數f的數學函數文法f(x)也可以追溯到他。
柯尼斯堡七橋問題是因同一座橋不可以通過超過一次這條規則而産生，但卻并未規定必須在何處開始或結束。這就意味着若你試圖解決這個問題，那就跳不出無向圖這個框。倘若化繁為簡，隻從特定點開始又會怎樣呢？
如果你生活在B島上，那麼你每次走過各個橋就都得從B島開始。這種情況就是一個有向圖，通常稱為樹（tree）。
樹就是圖
讓我們來看看另一種類型的圖：樹。樹是把節點分層排列的圖。當你發現圖裡有一個根節點的時候，就說明這是一棵樹。換句話說，根是樹開始的地方，其他節點都作為子節點與根連接配接。
我們來看一個公司的結構圖，這是一個教科書式的樹案例。公司CEO高高在上，其他員工都在CEO之下。CEO就是樹的根節點，所有其他員工就是樹的子節點，如圖2-15所示。
樹有許多用途，比如可以表示一個家庭的家譜。樹還可以映射決策算法（decision-making algorithm），進而幫助程式員高效地通路資料庫中的資訊。或許有一天，你可以直接把圖2-15那個二叉樹倒過來，自己出任CEO，走上人生巅峰。
我們可以根據圖是否有根節點或者起始節點來判定它是否為樹。從根節點開始，樹通過邊連接配接各個子節點。當一個節點連接配接到子節點時，該節點就被稱為父節點（parent）。當一個子節點又有子節點時，該節點就被稱為分支（branch）。如果一個節點沒有子節點，那麼這個節點就叫作葉子（leaf）。
節點涵蓋了資料點。是以，了解資料在樹中的位置就顯得尤為重要，這樣才能快速地通路資料。為了快速查找資料，我們希望計算單個節點的深度。節點的深度僅僅是指節點離樹的根節點有多遠。讓我們考慮一下A→B→C→D這種樹。為了找到節點C的深度，我們來計算C和根節點之間的連接配接數。C和根節點（A）之間正好有兩個連接配接，是以節點C的深度就是2，同理節點D的深度就是3。
樹的層次結構意味着樹通常也包括其他樹。嵌套在樹中的樹稱為子樹。一個HTML頁面通常有多個子樹。樹的根是标記。然後，有兩個子樹，左側子樹根是
，右側子樹的根就是。從這裡開始，都是不同子樹的根。多個嵌套也就産生了多個子樹，如圖2-16所示。
正如樹是一種特定類型的圖一樣，二叉樹（binary tree）也是一種特定類型的樹。二叉樹的意思是每個節點的子節點數都不超過兩個。當談到二叉樹時，通常指的是二叉搜尋樹（binary search trees）注3。二叉搜尋樹是遵循特定排序規則的二叉樹。排序規則和樹結構可幫助我們快速找到所需的資料。圖2-17展示了一個二叉搜尋樹的例子。
它同樣擁有一個根節點，并且遵守每個節點不超過兩個子節點的規則。假設我們想要找到節點15。如果沒有二叉搜尋樹，我們需要周遊每個節點，直至找到節點15。也許我們會幸運地沿着正确的分支走下去，可誰又能保證幸運女神每次都會眷顧我們呢，碰個滿頭包然後回去一個個找才是最真實的情況。
利用二叉搜尋樹，通過對左右節點規則的了解，我們可以很快地定位節點15。如果我們從根節點（9）開始周遊，我們會問“15比9大還是小？”如果小于，我們就找它左邊的節點。如果大于，就找右邊。這樣一來，我們便排除了樹中一半的節點。然後我們找到了節點20，我們再次考慮15和20的大小關系，于是我們再繼續找它的左子節點。這樣，又有一半的節點不用考慮。然後我們找到了節點13，15大于13，是以我們通過尋找右側子節點找到了它。通過不斷地使用左右節點判斷來排除不合适選項，我們可以更快地找到所需的資料。
現實世界中的圖形結構
在工作中使用GraphQL時，你可能每天都會遇到這些圖論概念。否則，你可能隻是将GraphQL項目作為一種将資料高效加載到使用者界面的方法而已。無論如何，所有這些都是在GraphQL的背景執行的。正如我們所看到的，圖形特别适合有處理大量資料需求的應用。
想想Facebook。根據圖論知識，我們知道Facebook中每個人都是一個節點。當一個人和其他人連接配接時，通過一條邊達成了雙向連接配接。Facebook是一個無向圖。當我在Facebook上和我的摯友Sarah聯系時，她也給我回應，這就是雙向連接配接（見圖2-18）。
作為無向圖，Facebook圖中每個節點都是許多互相連接配接的關系網絡—社交關系網的一部分。你和你所有的朋友都聯系在一起。在同一幅圖中，這些朋友都和他們所有的朋友們連接配接在一起。周遊可以從任何節點開始和結束（見圖2-19）。
此外，還有推特（Twitter）。與每個人都是雙向連接配接的Facebook不同，Twitter是一個有向圖，因為每個人的連接配接都是單向的，如圖2-20所示。你關注了一位明星人物，明星不一定會關注你，因為他們的粉絲實在是太多了。
如果一個人檢視他所有的朋友，那麼他就是一棵樹的根節點。他和他的朋友有聯系。他的朋友又在子樹中連接配接到了他們的朋友（見圖2-21）。
Facebook上的其他人也是如此。每當你隔了一個人并請求他們的資料時，請求查找過程就像一棵樹了。查詢者是樹的根節點，并且你希望他之下所有的資料都是子節點。在該請求中，一個人通過邊連接配接到他們所有的朋友：
person
—name
—location
—birthday
—friends
—friend name
—friend location
—friend birthday
結構和GraphQL的查詢字段很像：
{
me {
name
location
birthday
friends {
name
location
birthday
}
} }
我們使用GraphQL的目标是對需要的資料發出查詢來簡化複雜的資料圖形。在下一章中，我們将深入研究GraphQL查詢字段的工作機制，以及如何根據類型系統驗證查詢。