定義
圖是由若干給定的頂點(diǎn)及連接兩頂點(diǎn)的邊所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系。頂點(diǎn)用于代表事物，連接兩頂點(diǎn)的邊則用于表示兩個(gè)事物間具有這種關(guān)系。
定義來(lái)自維基百科:圖論
結(jié)構(gòu)
圖中只包含兩種類型的元素：頂點(diǎn)（vertex）和邊（edge），所以圖可以由頂點(diǎn)集合和邊集合進(jìn)行表示，即：。根據(jù)邊是否具有方向，可以將圖分為有向圖和無(wú)向圖兩種。
無(wú)向圖
有向圖
上面兩張圖 graph 和 digraph 具有相同的頂點(diǎn)集合 ，但是邊集合
不同，所以屬于不同的兩個(gè)圖。
權(quán)重
上述圖定義中提到，邊的作用是用來(lái)描述兩個(gè)頂點(diǎn)之間的關(guān)系，圖 graph 和 digraph 兩個(gè)示例中的邊僅能表示兩個(gè)頂點(diǎn)之間是連通的，可達(dá)的，并不能代表別的意義?？梢越o邊設(shè)置大小值，即權(quán)重，表示兩個(gè)頂點(diǎn)之間連通的程度。例如當(dāng)圖中頂點(diǎn)表示城市的坐標(biāo)時(shí)，則可以設(shè)置連接兩個(gè)頂點(diǎn)的邊的權(quán)重為距離，或某種交通方式消耗的時(shí)間。
度
從一個(gè)頂點(diǎn)出發(fā)，到相鄰頂點(diǎn)的邊的個(gè)數(shù)稱為該頂點(diǎn)的出度，以該頂點(diǎn)為終點(diǎn)的邊的個(gè)數(shù)稱為該頂點(diǎn)的入度。因?yàn)闊o(wú)向圖的邊不具有方向性，所以無(wú)向圖中頂點(diǎn)的出度與入度相等。
路徑與回路
從頂點(diǎn)集合 中選擇
作為起點(diǎn)，
作為終點(diǎn)，從起點(diǎn)出發(fā)到達(dá)終點(diǎn)的過(guò)程中，經(jīng)過(guò)的邊的集合稱為路徑，路徑中邊的個(gè)數(shù)稱為路徑長(zhǎng)度。若路徑中不重復(fù)經(jīng)過(guò)一個(gè)頂點(diǎn)，則稱為簡(jiǎn)單路徑。若起點(diǎn)和終點(diǎn)是同一個(gè)頂點(diǎn)，則該路徑也稱之為回路。
連通圖、連通分量與生成樹(shù)
對(duì)于無(wú)向圖，若圖中任意兩個(gè)頂點(diǎn)之間存在路徑，則該無(wú)向圖為連通圖；對(duì)于有向圖，若圖中任意兩個(gè)頂點(diǎn)之間存在路徑，則該有向圖為強(qiáng)連通圖。
對(duì)于無(wú)向圖，其極大連通子圖稱為該無(wú)向圖的連通分量；對(duì)于有向圖，其極大強(qiáng)連通子圖稱為該無(wú)向圖的強(qiáng)連通分量。
根據(jù)連通分量定義可知，對(duì)于連通圖，極大連通子圖是其自身，所以圖的連通分量就是其自身。對(duì)于非連通圖，因?yàn)榭梢源嬖诙鄠€(gè)極大連通子圖，所以可以具有多個(gè)連通分量。
連通圖的極小連通子圖也稱之為生成樹(shù)，即包含頂點(diǎn)集合 ，但是邊的個(gè)數(shù)為
。生成樹(shù)可以有多個(gè)，經(jīng)常提到的最小生成樹(shù)，也就是帶權(quán)連通圖中權(quán)值之和最小的生成樹(shù)。
圖相關(guān)的概念較多，再次強(qiáng)調(diào)一點(diǎn)，就像在介紹二叉樹(shù)時(shí)所說(shuō)，概念只是起到輔助說(shuō)明的角色，為了方便理解和傳播事物而誕生的產(chǎn)物，不應(yīng)該過(guò)分糾結(jié)概念而忽略了真正的目的。
github鏈接：圖
