圖
1. 圖的定義
1.1 各種圖
圖由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成狮含，記為G(V,E)洋满，其中G表示圖，V是G圖中頂點(diǎn)的集合锣咒，E是G圖中邊的集合侵状。
- 無(wú)向邊：用無(wú)需偶對(duì)(Vi,Vj)表示
- 有向邊：也稱為弧，<Vi,Vj>表示毅整，Vi為弧頭（head）趣兄。主要順序不能寫錯(cuò)
- 無(wú)頂點(diǎn)到自身的邊和重邊的圖稱為簡(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ú)向圖的的極大連通子圖稱為連通分量
- 子圖
- 子圖是連通的
- 連通子圖含有極大頂點(diǎn)數(shù)
- 具有極大頂點(diǎn)數(shù)的連通子圖包含依附于這些頂點(diǎn)的所有邊
有向圖雙向連通->強(qiáng)連通
無(wú)向圖中連通且n個(gè)頂點(diǎn)n-1條邊叫生成樹
有向圖：有向樹总棵，若干顆有向樹構(gòu)成生成森林
2. 抽象數(shù)據(jù)類型
3. 存儲(chǔ)結(jié)構(gòu)
3.1 鄰接矩陣
- 一維數(shù)組存儲(chǔ)圖中頂點(diǎn)信息
- 二位數(shù)組（鄰接矩陣）存儲(chǔ)邊/弧的信息
- 求Vi的所有鄰接點(diǎn)只需將矩陣的第i行元素掃描一遍鳍寂，為1的為鄰接點(diǎn)
- 無(wú)向圖的鄰接矩陣為對(duì)稱陣
- 網(wǎng)的權(quán)值表示法
- 用權(quán)值代替1
- 無(wú)連接的為“無(wú)窮”
- 主對(duì)角線為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)化：鄰接表
