圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V,E）彰阴，其中瘾敢，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合簇抵。
一庆杜、圖的定義
在線性表中，數(shù)據(jù)元素之間是被串起來的正压，僅有線性關(guān)系欣福，每個數(shù)據(jù)元素之間只有一個直接前驅(qū)和一個直接后繼。
在樹形結(jié)構(gòu)中焦履，數(shù)據(jù)元素之間有著明顯的層次關(guān)系拓劝，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素相關(guān)，但只能和上一層中一個元素相關(guān)嘉裤。
圖是一種較線性表和樹更加復(fù)雜的數(shù)據(jù)結(jié)構(gòu)郑临。在圖形結(jié)構(gòu)中，結(jié)點之間的關(guān)系可以是任意的屑宠，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)厢洞。
圖是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V,E）典奉，其中躺翻，G表示一個圖，V是圖G中頂點的集合卫玖，E是圖G中邊的集合公你。
注意：
1.線性表中我們把數(shù)據(jù)元素叫作元素，樹中將數(shù)據(jù)元素叫結(jié)點假瞬，在圖中數(shù)據(jù)元素叫頂點陕靠。
2.線性表中可以沒有數(shù)據(jù)元素驳遵，稱為空表谷炸。樹中可以沒有結(jié)點，叫做空樹剃幌。但在圖結(jié)構(gòu)中琴许，不允許沒有頂點税肪。
3.線性表中，相鄰數(shù)據(jù)元素之間具有線性關(guān)系榜田，樹結(jié)構(gòu)中寸认，相鄰兩層的結(jié)構(gòu)具有層次關(guān)系。而圖中串慰，任意兩個頂點之間都有可能有關(guān)系，頂點之間的邏輯關(guān)系用邊來表示唱蒸，邊集可以是空的邦鲫。
1.1各種圖定義
無向邊：若頂點Vi到Vj之間的邊沒有方向，則稱這條邊為無向邊，用無序偶對（Vi,Vj）來表示庆捺。如果圖中任意兩個頂點之間的邊都是無向邊古今，則稱該圖為無向圖。如圖所示：由于是無方向的滔以，連接頂點A與D的邊捉腥，可以表示成無序?qū)Γˋ,D），也可以寫成（D,A）你画。
有向邊：若從頂點Vi到Vj的邊有方向抵碟，則稱這條邊為有向邊，也稱為弧坏匪。用有序偶對<Vi,Vj>來表示拟逮，Vi稱為弧尾，Vj稱為弧頭适滓。如果圖中任意兩個頂點之間的邊都是有向邊敦迄，則稱該圖為有向圖。如圖所示：連接頂點A到D的有向邊就是弧凭迹，A是弧尾罚屋，D是弧頭，<A,D>表示弧嗅绸，注意不能寫成<D,A>脾猛。
在圖中，若不存在頂點到其自身的邊朽砰，且同一條邊不重復(fù)出現(xiàn)尖滚，則稱這樣的圖為簡單圖。
在無向圖中瞧柔，如果任意兩個頂點之間都存在邊漆弄，則稱該圖為無向完全圖。如圖所示：含有n個頂點的無向完全圖有{n(n-1)}/2條邊造锅。
在有向圖中撼唾，如果任意兩個頂點之間都存在方向互為相反的兩條弧，則稱該圖為有向完全圖哥蔚。如圖所示：含有n個頂點的有向完全圖有n*(n-1)條邊倒谷。
有很少條邊或弧的圖稱為稀疏圖，反之為稠密圖糙箍。
有些圖的邊或弧具有與它相關(guān)的數(shù)字渤愁，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)。這些權(quán)可以表示從一個頂點到另一個頂點的距離或耗費深夯。這種帶權(quán)的圖通常稱為網(wǎng)抖格。如圖所示：
1.2圖的頂點與邊定義
對于無向圖G=（V诺苹，{E}），如果邊（V,V’）屬于E雹拄，則稱頂點v和v'互為鄰接點收奔，即v和v'相鄰接。邊（v,v'）依附于頂點v和v'滓玖，或者說（v,v'）與頂點v和v'相關(guān)聯(lián)坪哄。頂點v的度是和v相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)势篡。如圖所示：頂點A和B互為鄰接點翩肌。
邊數(shù)其實就是各頂點度數(shù)和的一半。
對于有向圖G=（V殊霞，{E}）摧阅，如果弧<v,v'>屬于E，則稱頂點v鄰接到頂點v'绷蹲，頂點v'鄰接自頂點v棒卷。弧<v,v'>和頂點v祝钢，v'相關(guān)聯(lián)比规。以頂點v為頭的弧的數(shù)目稱為v的入度，記為ID(v)拦英；以v為尾的弧的數(shù)目稱為v的出度蜒什，記為OD(v);頂點v的度為TD(v)=ID(v)+OD(v)。如圖所示：頂點A的入度為2疤估，出度為1灾常。
樹中根結(jié)點到任意結(jié)點的路徑是唯一的，但是圖中頂點與頂點之間的路徑確是不唯一的铃拇。路徑的長度是路徑上的邊或者弧的數(shù)目钞瀑。
1.3連通圖
在無向圖G中，如果從頂點v到頂點v'有路徑慷荔，則稱v和v'是連通的雕什。如果對于圖中任意兩個頂點vi、vj屬于V显晶，vi和vj都是連通的贷岸，則稱G是連通圖。如圖所示：
二磷雇、圖的存儲結(jié)構(gòu)
2.1鄰接矩陣
圖的鄰接矩陣存儲方式是用兩個數(shù)組來表示圖偿警。一個一維數(shù)組存儲圖中頂點信息，一個二維數(shù)組（稱為鄰接矩陣）存儲圖中的邊或弧的信息唯笙。
示例如下户敬，下圖是一個無向圖：
頂點數(shù)組為vertex[4]={v0,v1,v2,v3}落剪，邊數(shù)組arc[4][4]為上圖右邊這樣的一個矩陣。無向圖的邊數(shù)組是一個對稱矩陣尿庐。
有向圖示例如下：
有向圖講究出度和入度，v1的出度是行之和呢堰，v1的入度是列之和抄瑟。
有向網(wǎng)圖示例如下：
無窮表示一個計算機允許的、大于所有邊上權(quán)值的值枉疼，也就是一個不可能的極限值皮假。
2.2鄰接表
鄰接矩陣是一個不錯的存儲結(jié)構(gòu)，對于邊數(shù)相對頂點較少的圖骂维，這種結(jié)構(gòu)是存在對存儲空間的極大浪費的褪测。
數(shù)組與鏈表相結(jié)合的存儲方法稱為鄰接表分扎。鄰接表是這樣的：
（1）圖中頂點用一個一維數(shù)組存儲菲饼，當(dāng)然粥谬，頂點也可以用單鏈表來存儲芭届，不過數(shù)組可以較容易的讀取頂點信息逃片，更加方便哥艇。另外哩俭，對于頂點數(shù)組中，每個數(shù)據(jù)元素還需要存儲指向第一個鄰接點的指針拳恋，以便于查找該頂點的邊信息凡资。
（2）圖中每個頂點vi的所有鄰接點構(gòu)成一個線性表，由于鄰接點的個數(shù)不定谬运，所以用單鏈表存儲隙赁，無向圖稱為頂點vi的邊表，有向圖則稱為頂點vi作為弧尾的出邊表梆暖。
無向圖的鄰接表結(jié)構(gòu)如下：
頂點的各個結(jié)點由data和firstedge兩個域表示伞访，data是數(shù)據(jù)域，存儲頂點的信息轰驳，firstedge是指針域厚掷，指向邊表的第一個結(jié)點，即此頂點的第一個鄰接點级解。邊表結(jié)點由adjvex和next兩個域組成冒黑。adjvex是鄰接點域，存儲某頂點的鄰接點在頂點表中的下標(biāo)勤哗，next則存儲指向邊表中下一個結(jié)點的指針抡爹。
有向圖的鄰接表結(jié)構(gòu)如下，但要注意的是有向圖由于有方向芒划，我們是以頂點為弧尾來存儲邊表的冬竟，這樣和容易得到每個頂點的出度欧穴。但有時為了便于確定頂點的入度或以頂點為弧頭的弧，我們可以建立一個有向圖的逆鄰接表泵殴，即對每個頂點vi都建立一個鏈接為vi為弧頭的表涮帘。
2.3十字鏈表（有向圖的鄰接表改進）
對于有向圖來說，鄰接表是有缺陷的袋狞。關(guān)心了出度問題焚辅，想了解入度就必須要遍歷整個圖才能知道，反之苟鸯，逆鄰接表解決了入度確不了解出度的情況。把鄰接表與逆鄰接表結(jié)合起來棚点，就是有向圖的另一種存儲方式：十字鏈表早处。頂點表結(jié)點結(jié)構(gòu)如圖所示：
其中firstin表示入邊表頭指針，指向該頂點的入邊表中第一個結(jié)點瘫析，firstout表示出邊表頭指針砌梆，指向該頂點的出邊表中的第一個結(jié)點。
邊表結(jié)點結(jié)構(gòu)如圖所示：
其中tailvex是指弧起點在頂點表的下標(biāo)贬循，headvex是指弧終點在頂點表中的下標(biāo)咸包，headlink是指入邊表指針域，指向終點相同的下一條邊杖虾，taillink是指邊表指針域烂瘫，指向起點相同的下一條邊。如果是網(wǎng)奇适，還可以再增加一個weight域來存儲權(quán)值坟比。
2.4鄰接多重表（無向圖的鄰接表改進）
如果我們在無向圖的應(yīng)用中，關(guān)注的重點是頂點嚷往，那么鄰接表是不錯的選擇葛账，但如果我們更關(guān)注邊的操作，比如對已經(jīng)訪問過的邊做標(biāo)記皮仁，刪除某一條邊等操作籍琳，那就意味著，需要找到這條邊的兩個邊表結(jié)點進行操作贷祈，這其實比較麻煩趋急。
重新定義的邊表結(jié)點結(jié)構(gòu)如圖所示：
ivex和jvex是與某條邊依附的兩個頂點在頂點表中的下標(biāo)。ilink指向依附頂點ivex的下一條邊付燥，jlink指向依附頂點jvex的下一條邊宣谈。這就是鄰接多重表結(jié)構(gòu)。
2.5邊集數(shù)組
邊集數(shù)組是由兩個一維數(shù)組構(gòu)成键科。一個是存儲頂點的信息闻丑；另一個是存儲邊的信息漩怎，這個邊數(shù)組每個數(shù)據(jù)元素由一條邊的起點下標(biāo)（begin）、終點下標(biāo)（end）和權(quán)（weight）組成嗦嗡，如圖所示：
顯然邊集數(shù)組關(guān)注的是邊的集合勋锤，在邊集數(shù)組中要查找一個頂點的度需要掃描整個邊數(shù)組，效率并不高侥祭。因此它更適合對邊依次進行處理的操作叁执，而不適合對頂點相關(guān)的操作。
三矮冬、圖的遍歷
從圖中某一頂點出發(fā)訪遍圖中其余頂點谈宛，且使每一個頂點僅被訪問一次，這一過程就叫做圖的遍歷胎署。
3.1深度優(yōu)先遍歷（類似樹的前序遍歷）
深度優(yōu)先遍歷吆录，也叫作深度優(yōu)先搜索，簡稱DFS琼牧。
首先從頂點A開始恢筝，做上走過的標(biāo)記后，前面有兩條路巨坊，通向B和F撬槽，我們自己設(shè)定一個規(guī)則，在沒有碰到重復(fù)頂點的情況下趾撵，始終是向右手邊走侄柔，于是走到了B頂點。整個行路過程如上圖所示鼓寺。此時發(fā)現(xiàn)有三條分支勋拟，分別通向頂點C、I妈候、G敢靡，右手通行原則，使得我們走到了C頂點苦银。就這樣啸胧，一直順著右手通道走，一直走到F頂點幔虏。當(dāng)依然選擇右手通道走過去后纺念，發(fā)現(xiàn)走回到頂點A，而此時頂點A做了走過的標(biāo)記想括，因此退回到頂點F陷谱，走向從右數(shù)的第二條通道，到了G頂點，它有三條通道烟逊，發(fā)現(xiàn)B和D都已經(jīng)是走過的渣窜，于是走到了H，當(dāng)面對通向H的兩條通道D和E時宪躯，會發(fā)現(xiàn)都已經(jīng)走過了乔宿。
此時是否已經(jīng)遍歷了所有頂點？沒有访雪∠耆穑可能還有很多分支的頂點我們沒有走到，所以按原路返回臣缀。在頂點H處坝橡，再無通道沒走過，返回到G精置，也無未走過通道驳庭，返回F，沒有通道氯窍，返回到E，有一條通道通往H的通道蹲堂，驗證后也是走過的狼讨，再返回到頂點D，此時H走過了柒竞，G走過了政供，I未走過，趕快記下來朽基。繼續(xù)返回布隔，直到返回頂點A，確認(rèn)已經(jīng)完成遍歷任務(wù)稼虎，找到了所有的9個頂點衅檀。
深度優(yōu)先遍歷其實就是一個遞歸的過程。它從圖中某個頂點v出發(fā)霎俩，訪問此頂點哀军，然后從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到打却。
3.2廣度優(yōu)先遍歷（類似樹的層序遍歷）
廣度優(yōu)先遍歷杉适，又稱為廣度優(yōu)先搜索，簡稱BFS柳击。
對上圖進行變形猿推，變形原則是頂點A放置在最上第一層，讓與它有邊的頂點B捌肴、F為第二層蹬叭，再讓與B和F有邊的頂點C藕咏、I、G具垫、E為第三層侈离，再將這四個頂點有邊的D、H放在第四層筝蚕，如圖所示卦碾。
