概念
圖的定義
圖（Graph）是由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間的邊的集合組成满力，通常
表示為： G(V,E)作喘。其中厢蒜，G 表示一個(gè)圖霞势，V 是圖 G 中頂點(diǎn)的集合，E 是
圖 G 中邊的集合斑鸦。
需要注意：
圖中數(shù)據(jù)元素叫做頂點(diǎn)（Vertext）愕贡。
在圖中，不允許沒有頂點(diǎn)巷屿。若 V 是圖的頂點(diǎn)的集合固以，那么，V 是非空
有窮集合嘱巾。圖的任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系憨琳，它們的關(guān)系用邊來表示诫钓。邊集可
以是空的。
其他概念
無向邊
若頂點(diǎn) $V_i$ 到 $V_j$ 之間的邊沒有方向栽渴，這條邊就叫做無向邊（Edge）,
用無序偶對 ($V_iV_j$) 來表示尖坤。
無向圖
如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是無向邊稳懒，則稱該圖為無項(xiàng)圖（Undirected graphs）闲擦。
有向邊
若從頂點(diǎn) $V_i$ 到 $V_j$ 的邊有方向，則稱這條邊為有向邊场梆，也稱為弧 (Arc)墅冷。
這條有向邊用有序偶 $<V_i,V_j>來表示，$V_j是弧尾(Tail)或油，$V_j$是弧頭(Head)寞忿。
有向圖
如果圖中任意兩個(gè)頂點(diǎn)之間的邊都是有向邊，這個(gè)圖就是有向圖顶岸。
無向邊用小括號 “（）”表示腔彰，有向邊用尖括號“<>”表示。
簡單圖
在圖中辖佣，若不存在頂點(diǎn)到其自身的邊霹抛，且同一條邊不重復(fù)出現(xiàn)，這樣的圖就是簡單圖卷谈。
無向完全圖
在無向圖中杯拐，如何任意兩點(diǎn)之間都存在邊，這個(gè)圖就是無向完全圖世蔗。
n 個(gè)頂點(diǎn)的無向完全圖有 ${n(n-1)} \over 2$ 條邊端逼。
有向完全圖
在有向圖中，如果任意兩點(diǎn)之間都存在方向互為相反的兩條弧污淋，這個(gè)圖就是有向完全圖顶滩。
n個(gè)頂點(diǎn)的有向完全圖有 $n(n-1) \over 2$ 條邊。
稠密圖和稀疏圖
邊或弧很少的圖是稀疏圖寸爆；邊或弧很多的圖是稠密圖礁鲁。
它們都是相對概念。
權(quán)而昨、網(wǎng)
與圖的邊或弧相關(guān)的數(shù)字叫做權(quán)（Weight）救氯。
權(quán)可以表示一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)。
帶權(quán)的圖叫做網(wǎng)（Network）歌憨。
子圖
假設(shè)有兩個(gè)圖 $G = (V,\lbrace E \rbrace)$着憨，$G' = (V',\lbrace E' \rbrace)$，$V' \subseteq V$务嫡，$E' \subseteq E$甲抖，那么漆改，
G' 是 G 的子圖。
圖的頂點(diǎn)與邊間的關(guān)系（暫時(shí)不做筆記准谚，有空再補(bǔ)充）
概念太多挫剑，記錄太麻煩，暫時(shí)不做筆記柱衔，有空再補(bǔ)充樊破。
連通圖
連通圖
圖7-2-13圖2根據(jù)定義，我認(rèn)為它不是強(qiáng)連通圖唆铐。
生成樹
不理解哲戚。
有向樹
不理解。
圖的抽象數(shù)據(jù)類型
ADT 圖(Graph)
Data
頂點(diǎn)的有窮非空集合和邊的集合
Operation
CreateGraph(*G, V, VR)：按照頂點(diǎn)集 V 和 邊弧集 VR 的定義構(gòu)造圖 G艾岂。
DestroyGraph(*G)：圖G存在則銷毀它顺少。
LocateVex(G, u)：若圖 G 中存在頂點(diǎn) u，則返回它在圖中的位置王浴。
GetVex(G, v)：返回圖 G 中頂點(diǎn) v 的值脆炎。
PutVex(G, v, value)：將圖 G 中頂點(diǎn) v 賦值 value。
FirstAdjVex(G, *v)：返回頂點(diǎn) v 的一個(gè)鄰接頂點(diǎn)氓辣，若頂點(diǎn)在 G 中無鄰接頂點(diǎn)則返回空秒裕。
NextAdjVex(G, v, *w)：返回頂點(diǎn) v 相對于頂點(diǎn) w 的下一個(gè)鄰接頂點(diǎn)，若 w 是 v 的最后
一個(gè)鄰接點(diǎn)則返回“空”筛婉。
InsertVex(*G, v)：在圖 G 中增添新頂點(diǎn) v簇爆。
DeleteVex(*G, v): 刪除圖 G 中頂點(diǎn) v 及其相關(guān)的弧。
InsertArc(*G, v, w)：在圖中增添弧 <v,w>爽撒，若 G 是無向圖入蛆，還要增加對稱弧 <w,v>。
DeleteArc(*G, v, w)：在圖中刪除弧 <v,w>硕勿，若 G 是無向圖哨毁，還需要?jiǎng)h除對稱弧 <w,v>。
DFSTraverse(G)：對圖 G 深度優(yōu)先遍歷源武，在遍歷過程中對每個(gè)頂點(diǎn)調(diào)用扼褪。
HFSTraverse(G):對圖 G 廣度優(yōu)先遍歷，在遍歷過程中對每個(gè)頂點(diǎn)調(diào)用粱栖。
endADT
圖的存儲(chǔ)結(jié)構(gòu)（難理解）
鄰接矩陣
定義
圖的鄰接矩陣（Adjacency Matrix）存儲(chǔ)方式是用兩個(gè)數(shù)組表示圖话浇。一個(gè)一維數(shù)組存儲(chǔ)圖中頂點(diǎn)信息，一個(gè)
二維數(shù)組（稱為鄰接矩陣）存儲(chǔ)圖中的邊或弧信息闹究。
無向圖實(shí)例
有向圖實(shí)例
網(wǎng)圖
鄰接矩陣存儲(chǔ)結(jié)構(gòu)
鄰接矩陣存儲(chǔ)結(jié)構(gòu)代碼：
備注：用65536代替 $\infty$
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100; // 最大頂點(diǎn)數(shù)
#define INFINITY 65535;
typedef struct
{
VertexType vexs[MAXVEX]; // 頂點(diǎn)表
EdgeType arc[MAXVEX][MAXVEX]; // 鄰接矩陣幔崖，可看作邊表
int numVertexes, numEdges; // 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
}MGraph;
創(chuàng)建無向網(wǎng)圖代碼：
void CreateGraph(MGraph *G)
{
int i, j, k, w;
printf("%s", "輸入頂點(diǎn)數(shù)和邊數(shù):\n");
scanf("%d, %d", &G->numVertexes, &G->numEdges); // 輸入頂點(diǎn)數(shù)和邊數(shù)
for(i = 0; i < G->numVertexes; i++){
scanf(&G->vexs[i]);
}
for(i = 0; i < G->numVertexes; i++){
for(j = 0; j < G->numVertexes; j++){
G->arc[i][j] = INFINITY; // 鄰接矩陣初始化
}
}
for(k = 0; k < G->numEdges; k++){ // 讀入numEdges條邊，建立鄰接矩陣
printf("輸入邊(vi,vj)上的下標(biāo)i、下標(biāo)j和權(quán)w:\n");
scanf("%d, %d, %d", &i, &j, &w); // 輸入邊（vi,vj）上的權(quán)w
G->arc[i][j] = w;
G->arc[j][i] = G->arc[i][j]; // 因?yàn)槭菬o向圖赏寇，矩陣對稱
}
}
鄰接表
概念
定義
數(shù)組與鏈表相結(jié)合的方法稱為鄰接表（Adjacency List）吉嫩。
思路
圖中頂點(diǎn)用一個(gè)一維數(shù)組存儲(chǔ)。該數(shù)組存儲(chǔ)兩部分內(nèi)容：頂點(diǎn)信息和指針嗅定。
該指針指向該頂點(diǎn)的第一個(gè)鄰接點(diǎn)自娩。圖中的每個(gè)頂點(diǎn) $v_i$ 的所有鄰接點(diǎn)構(gòu)成一個(gè)線性表，用單鏈表存儲(chǔ)渠退。
這個(gè)線性表可能叫 邊表忙迁，也可能叫 出邊表。
當(dāng)圖為無向圖的時(shí)候智什，這個(gè)線性表叫做頂點(diǎn) $v_i$ 的邊表动漾。
當(dāng)圖為有向圖的時(shí)候，這個(gè)線性表叫做頂點(diǎn) $v_i$ 作為弧尾的出邊表荠锭。
摘抄書本
無向圖的鄰接表結(jié)構(gòu)
$v_0$ 的鄰接點(diǎn)是 $v_1，v_2晨川，v_3$证九，$v_0$的 firstEdge 存儲(chǔ)的指針指向它的第一個(gè)鄰接點(diǎn) $v_1$。
$v_1$ 的 adjvex 存儲(chǔ)的是 該頂點(diǎn)在頂點(diǎn)表中的下標(biāo)共虑，next 存儲(chǔ)的指針指向 $v_0$ 的第二個(gè)鄰接點(diǎn) $v_2$愧怜。
有向圖的鄰接表結(jié)構(gòu)
網(wǎng)圖的鄰接表結(jié)構(gòu)
鄰接表存儲(chǔ)結(jié)構(gòu)（看不懂）
結(jié)點(diǎn)定義代碼
typedef char VertexType;
typedef int EdgeType;
typedef struct EdgeNode // 邊表結(jié)點(diǎn)
{
int adjvex; // 鄰接點(diǎn)域，存儲(chǔ)該頂點(diǎn)對應(yīng)的下標(biāo)
EdgeType weight; // 權(quán)值
struct EdgeNode *next; // 鏈域妈拌，指向下一個(gè)連接點(diǎn)
}EdgeNode;
typedef struct VertexNode // 頂點(diǎn)表結(jié)點(diǎn)
{
VertexType data; // 頂點(diǎn)域拥坛，存儲(chǔ)頂點(diǎn)信息
EdgeNode *firstEdge; // 邊表頭指針
}VertexNode, AdjList[MAXVEX];
typedef struct
{
AdjList adjList;
int numVertexes, numEdges; // 圖中當(dāng)前頂點(diǎn)數(shù)和邊數(shù)
}GraphAdjList;
邊表結(jié)點(diǎn) EdgeNode 為什么如此定義？
無向圖的鄰接表創(chuàng)建代碼
void CreateALGraph(GraphAdjList *G)
{
int i, j, k;
EdgeNode *e;
printf("輸入頂點(diǎn)數(shù)和邊數(shù)：\n");
scanf("%d, %d", &G->numVertexes, &G->numEdges); // 輸入頂點(diǎn)數(shù)和邊數(shù)
for(i = 0; i < G->numVertexes; i++){
scanf(&G->adjList[i].data); // 輸入頂點(diǎn)信息尘分。這種寫法猜惋，有問題嗎？
G->adjList[i].firstEdge = NULL; // 將邊表置為空表培愁。為什么著摔？
}
for(k = 0; k < G->numVertexes; i++){ // 建立邊表
printf("輸入邊(Vi,Vj)上的頂點(diǎn)序號：\n");
scanf("%d, %d", &i, &j); // 輸入邊(Vi,Vj)上的頂點(diǎn)序號
e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 申請內(nèi)存空間，創(chuàng)建邊表結(jié)點(diǎn)
e->adjvex = j; // 鄰接序號為j
e->next = G->adjList[i].firstEdge; // 將e指針指向當(dāng)前頂點(diǎn)指向的結(jié)點(diǎn) 定续？
G->adjList[i].firstEdge = e; // 將當(dāng)前頂點(diǎn)的指針指向e
e = (EdgeNode *)malloc(sizeof(EdgeNode)); // 申請內(nèi)存空間谍咆，創(chuàng)建邊表結(jié)點(diǎn)
e->adjvex = i; // 鄰接序號為i
e->next = G->adjList[j].firstEdge; // 將e指針指向當(dāng)前頂點(diǎn)指向的結(jié)點(diǎn)
G->adjList[j].firstEdge = e; // 將當(dāng)前頂點(diǎn)的指針指向e
}
}
十字鏈表（看不懂）
摘抄
鄰接多重表（看不懂）
摘抄
邊集數(shù)組
摘抄
圖的遍歷
定義
從圖中某一個(gè)頂點(diǎn)出發(fā)遍訪圖的其余所有頂點(diǎn)，且使所有頂點(diǎn)被訪問且只訪問一次私股。
這個(gè)過程摹察，就叫做圖的遍歷（Traversing Graph）。
深度優(yōu)先遍歷(Depth_First_Search)
摘抄
虛線表示已經(jīng)遍歷過的點(diǎn)倡鲸，實(shí)線表示未遍歷過的點(diǎn)供嚎。
代碼
鄰接矩陣代碼
typedef int Boolean; // Boolean是布爾類型，其值是TRUE或FALSE
Boolean visited[MAX]; // 訪問標(biāo)志的數(shù)組
void DFS(MGraph G, int i)
{
int j;
visited[i] = TRUE;
printf("%c", G.vexs[i]);
/*2*/for(j = 0; j < G.numVertexes; j++){
/*1*/if(G.arc[i][j] == 1 && !visited[j] ){
DFS(G, j); // 對未訪問的頂點(diǎn)遞歸調(diào)用
}
}
}
void DFSTraverse(MGraph G)
{
int i;
for(i = 0; i < G.numVertexes; i++){
visited[i] = FALSE; // 初始所有頂點(diǎn)狀態(tài)都是未訪問過狀態(tài)
}
for(i = 0; i < G.numVertexes; i++){
if(!visited[i]){
DFS(G, i);
}
}
}
第1行，G.arc[i][j] == 1 表明 $v_iv_j$ 邊存在查坪，這是根據(jù)鄰接圖矩陣定義得出的
結(jié)果寸宏。
第1行，visited[j] 不能理解這句偿曙。
第2行的循環(huán)里面的遞歸氮凝，什么時(shí)候終止？
鄰接表代碼（不懂）
void DFS(GraphAdjList GL, int i)
{
EdgeNode *p;
visited[i] = TRUE;
printf("%c", GL->adjList[i].data);
p = GL->adjList[i].firstEdge;
while(p){
if(!visited[p->adjvex]){
DFS(GL, p->adjvex);
}
p = p->next;
}
}
void DFSTraverse(GraphAdjList GL)
{
int i;
for(i = 0; i < GL->numVertexes; i++){
visited[i] = FALSE;
}
for(i = 0; i < GL->numVertexes; i++){
if(!visited[i]){
DFS(GL, i);
}
}
}
廣度優(yōu)先遍歷(Breadth_First_Search)
摘抄
不明白如何得到這張圖望忆。
代碼
鄰接矩陣代碼（不懂）
void BFSTraverse(MGraph G)
{
int i, j;
Queue Q;
for(i = 0; i < G.numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q); // 初始化一個(gè)輔助用的隊(duì)列
for(i = 0; i < G.numVertexes; i++){ // 對每一個(gè)頂點(diǎn)做循環(huán)
if(!visited[i]){
visited[i] = TRUE;
printf("%c", G.vexs[i]);
EnQueue(&Q, i); // 將此頂點(diǎn)入隊(duì)列
while(!QueueEmpty(Q)){
DeQueue(&Q, &i); // 將隊(duì)列中元素出隊(duì)列罩阵，賦值給i
for(j = 0; j < G.numVertexes; j++){
if(G.arc[i][j] == 1 && !visited[j]){
visited[j] = TRUE;
printf("%c", G.vexs[j]);
EnQueue(&Q, j);
}
}
}
}
}
}
鄰接表代碼（不懂）
void BFSTraverse(GraphAdjList GL)
{
int i;
EdgeNode *p;
Queue Q;
for(i = 0; i < GL->numVertexes; i++){
visited[i] = FALSE;
}
InitQueue(&Q);
for(i = 0; i < GL->numVertexes; i++){
if(!visited[i]){
visited[i] = TRUE;
printf("%c", GL->adjList[i].data);
EnQueue(&Q, i);
while(!QueueEmpty(Q)){
DeQueue(&Q, &i);
p = GL->adjList[i].firstEdge; // 找到當(dāng)前頂點(diǎn)邊表鏈表頭指針
while(p){
if(!visited[p->adjvex]){
visited[p->adjvex] = TRUE;
printf("%c", GL->adjList[p->adjvex].data);
EnQueue(&Q, p->adjvex);
}
}
p = p->next; // 指針指向下一個(gè)鄰接點(diǎn)
}
}
}
}
最小生成樹
定義（不懂）
把構(gòu)造連通網(wǎng)的最小代價(jià)生成樹稱為最小生成樹（Minimum Cost Spanning Tree）。
普里姆(Prim)算法（不懂）
代碼
void MiniSpanTree_Prim(MGraph G)
{
int min, i, j, k;
int adjvex[MAXVEX]; // 保存相關(guān)頂點(diǎn)下標(biāo)
int lowcost[MAXVEX]; // 保存相關(guān)頂點(diǎn)間邊的權(quán)值
// 初始化第一個(gè)權(quán)值為0启摄，即v0加入生成樹
// lowcost的值為0稿壁，在這里就是此下標(biāo)的頂點(diǎn)已經(jīng)加入生成樹
lowcost[0] = 0;
adjvex[0] = 0; // 初始化第一個(gè)頂點(diǎn)下標(biāo)為0
for(i = 1; i < G.numVertexes; i++){
lowcost[i] = G.arc[0][i]; // 將v0頂點(diǎn)與之有邊的權(quán)值存入數(shù)組
adjvex[i] = 0; // 初始化都為v0的下標(biāo)
}
for(i = 1; i < G.numVertexes; i++){
min = INFINITY; // 初始化最小權(quán)值為 INFINITY
j = 1; k = 0;
while(j < G.numVertexes){
if(lowcost[j] != 0 && lowcost[j] < min){
min = lowcost[j]; // 讓當(dāng)前權(quán)值成為最小值
k = j; // 將當(dāng)前最小值的下標(biāo)存入k
}
j++;
}
printf("(%d, %d)", adjvex[k], k); //打印當(dāng)前頂點(diǎn)邊中權(quán)值最小的邊
lowcost[k] = 0; // 將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0，表示此頂點(diǎn)已經(jīng)完成任務(wù)
for(j = 1; j < G.numVertexes; j++){
if(lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){
lowcost[j] = G.arc[k][j]; // 將較小權(quán)值存入lowcost
adjvex[j] = k; // 將下標(biāo)為k的頂點(diǎn)存入adjvex
}
}
}
}
代碼解釋
克魯斯卡爾（Kruskal）算法
代碼
typedef struct
{
int begin;
int end;
int weight;
}Edge;
void MiniSpanTree_Kruskal(MGraph G)
{
int i, n, m;
Edge edges[MAXEDGE]; // 定義邊集數(shù)組
int parent[MAXVEX]; // 定義一數(shù)組用來判斷邊與邊是否形成環(huán)路
for(i = 0; i < G.numVertexes; i++){
parent[i] = 0; // 初始化數(shù)組值為0
}
for(i = 0; i < G.numVertexes; i++){
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if(n != m){ // 假如n與m不等歉备，說明此邊沒有與現(xiàn)有生成樹形成環(huán)路
// 將此邊的結(jié)尾頂點(diǎn)放入下標(biāo)為起點(diǎn)的parent中
// 表示此頂點(diǎn)已經(jīng)在生成樹集合中
parent[n] = m;
printf("(%d, %d) %d", edges[i].begin, edges[i].end, edges[i].weight);
}
}
}
int Find(int *parent, int f) // 查找連線頂點(diǎn)的尾部下標(biāo)
{
while(parent[f] > 0){
f = parent[f];
}
return f;
}
代碼解釋
最短路徑（看不懂）
暫時(shí)放棄
定義
非網(wǎng)圖的最短路徑傅是，是指兩頂點(diǎn)之間經(jīng)過的邊數(shù)最少的路徑。
網(wǎng)圖的最短路徑蕾羊，是指兩頂點(diǎn)之間經(jīng)過的邊上的權(quán)值之和最小的路徑喧笔。
路徑上的第一個(gè)源點(diǎn)，最后一個(gè)頂點(diǎn)是終點(diǎn)。
