圖
1. 圖的定義
1.1 各種圖
圖由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，記為G(V,E)，其中G表示圖，V是G圖中頂點(diǎn)的集合，E是G圖中邊的集合。
- 無(wú)向邊：用無(wú)需偶對(duì)(Vi,Vj)表示
- 有向邊：也稱(chēng)為弧，<Vi,Vj>表示，Vi為弧頭（head）。主要順序不能寫(xiě)錯(cuò)
- 無(wú)頂點(diǎn)到自身的邊和重邊的圖稱(chēng)為簡(jiǎn)單圖（無(wú)向圖中任意頂點(diǎn)間都有邊的簡(jiǎn)單圖為完全簡(jiǎn)單圖，n個(gè)頂點(diǎn)有n*(n-1)/2條邊
- 有向完全圖，n個(gè)頂點(diǎn)，n*(n-1)條邊
- 帶權(quán)（weight）的圖成為網(wǎng)（network）
1.2 頂點(diǎn)與邊
無(wú)向圖中被邊相連的頂點(diǎn)互為鄰接點(diǎn)（adjacent），這條邊依附（incident）與這兩個(gè)頂點(diǎn)。
頂點(diǎn)的度數(shù)：略。圖的邊數(shù)為全部頂點(diǎn)度數(shù)和的一半
有向圖分出度和入度。邊數(shù)=出度和=入度和
路徑
路徑的長(zhǎng)度
路徑的首尾相接->回路/環(huán)（cycle）
- 頂點(diǎn)不重復(fù)的路徑->簡(jiǎn)單路徑
- 除首尾頂點(diǎn)外無(wú)重復(fù)頂點(diǎn)的回路->簡(jiǎn)單回路
1.3 連通圖
無(wú)向圖的的極大連通子圖稱(chēng)為連通分量
- 子圖
- 子圖是連通的
- 連通子圖含有極大頂點(diǎn)數(shù)
- 具有極大頂點(diǎn)數(shù)的連通子圖包含依附于這些頂點(diǎn)的所有邊
有向圖雙向連通->強(qiáng)連通
無(wú)向圖中連通且n個(gè)頂點(diǎn)n-1條邊叫生成樹(shù)
有向圖：有向樹(shù)，若干顆有向樹(shù)構(gòu)成生成森林
2. 抽象數(shù)據(jù)類(lèi)型
3. 存儲(chǔ)結(jié)構(gòu)
3.1 鄰接矩陣
- 一維數(shù)組存儲(chǔ)圖中頂點(diǎn)信息
- 二位數(shù)組（鄰接矩陣）存儲(chǔ)邊/弧的信息
- 求Vi的所有鄰接點(diǎn)只需將矩陣的第i行元素掃描一遍，為1的為鄰接點(diǎn)
- 無(wú)向圖的鄰接矩陣為對(duì)稱(chēng)陣
- 網(wǎng)的權(quán)值表示法
- 用權(quán)值代替1
- 無(wú)連接的為“無(wú)窮”
- 主對(duì)角線(xiàn)為0
代碼實(shí)現(xiàn)
typedef char VertexType;
typedef int Endg Type;
#define MAXVEX 100
#define INFINITY 65535
typedf struct
{
VertexType vexs [MAXVEX];
EdgeType arc [MAXVEX] [MAXVEX];
int numVertexes, numEdges;
} MGraph;
鄰接矩陣?yán)速M(fèi)空間，優(yōu)化：鄰接表
