- 線性表是一對(duì)一，樹是一對(duì)多汹想，圖是多對(duì)多的關(guān)系外邓。
- 圖中的數(shù)據(jù)元素我們稱為頂點(diǎn)（相對(duì)于樹中的結(jié)點(diǎn)），頂點(diǎn)集合不能為空古掏，邊集合可以為空损话。
- 無(wú)向圖——只要圖中有一條邊是無(wú)向邊（A,B）。
- 有向圖——任意兩頂點(diǎn)之間的邊都是有向邊（徊弁佟）<A,B>丧枪。
- 無(wú)向完全圖——n個(gè)頂點(diǎn)中任意兩頂點(diǎn)之間都存在邊的無(wú)向圖。邊的總數(shù)是n*(n-1)/2庞萍。
- 有向完全圖——n個(gè)頂點(diǎn)中任意兩頂點(diǎn)之間都存在方向相反的有向邊的有向圖拧烦。邊的總數(shù)是n*(n-1)。
- 權(quán)——與圖的邊相關(guān)的數(shù)字钝计。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)恋博。
- 網(wǎng)——帶權(quán)的圖。如網(wǎng)絡(luò)圖中私恬，各條邊就是鏈路债沮，鏈路都是有帶權(quán)（距離或帶寬）的。
- 子圖——G=(V,{E})本鸣，G'=(V',{E'})疫衩，其中V'是V的子集，E'是E的子集荣德，則稱G'是G的子圖(subgraph)闷煤。
- 頂點(diǎn)v的度degree——是和頂點(diǎn)v相連接的邊的數(shù)目。對(duì)于有向圖的頂點(diǎn)的度還分為出度和入度命爬。
- 鄰接點(diǎn)——同一條邊的兩個(gè)點(diǎn)互為鄰接點(diǎn)曹傀。
- 路徑——指從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)所經(jīng)過(guò)的頂點(diǎn)的序列。樹的路徑唯一饲宛，但圖的路徑不唯一皆愉，所以有很多求最短路徑的算法。在網(wǎng)絡(luò)圖中艇抠，路徑又叫路由幕庐。
- 路徑的長(zhǎng)度——路徑上的邊或弧的數(shù)目。
- 回路或環(huán)——第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑家淤。
- 簡(jiǎn)單路徑——路徑序列中沒(méi)有重復(fù)出現(xiàn)的頂點(diǎn)异剥。
- 簡(jiǎn)單回路——除了第一個(gè)和最后一個(gè)頂點(diǎn)相同外，其余的頂點(diǎn)都不相同絮重。
- 連通圖（connected graph）——無(wú)向圖中任意兩個(gè)頂點(diǎn)都有路徑（即都是連通的）冤寿。
- 非連通圖——存在兩個(gè)頂點(diǎn)之間沒(méi)有路徑歹苦，即不連通。有n個(gè)頂點(diǎn)督怜，但只有小于n-1條邊殴瘦，一定是非連通圖。
- 連通分量——無(wú)向圖中的極大連通子圖号杠。連通圖本身即是蚪腋，而非連通圖中最大的連通子圖即是。
- 強(qiáng)連通圖——有向圖中姨蟋，任意兩個(gè)頂點(diǎn)都存在雙向連通的路徑屉凯。有向圖的非強(qiáng)連通圖，對(duì)應(yīng)有強(qiáng)連通分量眼溶。
- 生成樹——一個(gè)連通圖的極小連通子圖悠砚，它含有圖中全部的n個(gè)頂點(diǎn)，但只有足以構(gòu)成一棵樹的n-1條邊（即去掉了環(huán)路）偷仿。不過(guò)n個(gè)頂點(diǎn)有n-1條邊并不一定是生成樹哩簿，比如一個(gè)非連通圖中有一部分是個(gè)環(huán)路。因此生成樹的前提一定是連通圖酝静。
- 有向樹——一個(gè)有向圖恰有一個(gè)頂點(diǎn)的入度為0（根結(jié)點(diǎn)），其余頂點(diǎn)的入度均為1羡玛。
- 生成森林——一個(gè)有向圖的所有頂點(diǎn)别智，被分成若干顆不相交的有向樹，這些有向樹就組成了有向森林稼稿。
圖的存儲(chǔ)結(jié)構(gòu)
- 因?yàn)轫旤c(diǎn)間多對(duì)多的關(guān)系薄榛，所以不能用簡(jiǎn)單的順序結(jié)構(gòu)數(shù)組來(lái)表示。
- 因?yàn)楦鱾€(gè)頂點(diǎn)的度不一致让歼，所以不能用數(shù)據(jù)域+若干指針域的多重鏈表形式來(lái)表示敞恋，否則將造成很大的浪費(fèi)。
- 圖的存儲(chǔ)結(jié)構(gòu)有5種特別的谋右。
1硬猫、鄰接矩陣——重點(diǎn)關(guān)注頂點(diǎn)
2、鄰接表——對(duì)鄰接矩陣空間浪費(fèi)的改進(jìn)改执，重點(diǎn)關(guān)注頂點(diǎn)
3啸蜜、十字鏈表——對(duì)有向圖的鄰接表進(jìn)行改進(jìn)，重點(diǎn)關(guān)注頂點(diǎn)
- 將展示出度的鄰接表和展示入度的逆鄰接表整合在一起辈挂。
4衬横、鄰接多重表——對(duì)無(wú)向圖的鄰接表進(jìn)行改進(jìn)，重點(diǎn)關(guān)注邊
- 更關(guān)注邊的操作终蒂，仿照十字鏈表蜂林。
- 鄰接多重表與鄰接表的差別：同一條邊遥诉，在鄰接表中要用兩個(gè)結(jié)點(diǎn)表示，因此不便于刪除一條邊噪叙。然而在鄰接多重表中矮锈，每個(gè)節(jié)點(diǎn)表示一條邊，要?jiǎng)h除邊很簡(jiǎn)單构眯。
5愕难、邊集數(shù)組——重點(diǎn)關(guān)注邊，特別是與邊的權(quán)值有關(guān)的最小生成樹問(wèn)題
圖的遍歷方式
1惫霸、深度優(yōu)先搜索遍歷DFS——類似于樹的先序遍歷猫缭，使用遞歸
2、廣度優(yōu)先搜索遍歷BFS——類似于樹的層序遍歷壹店，使用隊(duì)列
總結(jié)分析兩種遍歷方式
尋找最小生成樹——最小代價(jià)生成樹
以最小的成本完成任務(wù)猜丹？
在一個(gè)帶權(quán)值的圖中，即網(wǎng)中硅卢，n個(gè)頂點(diǎn)找到n-1條邊將他們連起來(lái)成為連通圖射窒，并且各邊的權(quán)值總和最小，即為成本（代價(jià)）最小将塑。類似的問(wèn)題就是最小生成樹問(wèn)題脉顿。
