1 圖的定義

一個圖(G)定義為一個偶對(V,E)亭饵，記為G=(V,E)休偶。
V是頂點(Vertex)的非空有限集合，記為V(G)辜羊。
E是無序集V&V的一個子集踏兜，記為E(G)，其元素是圖的弧(Arc)八秃。
將頂點集合為空的圖稱為空圖碱妆。
弧：表示兩個頂點v和w之間存在一個關(guān)系喜德，用頂點偶對<v,w>表示山橄。

2 圖的重要術(shù)語

(1)無向圖:
在一個圖中垮媒，如果任意兩個頂點構(gòu)成的偶對(v,w)∈E 是無序的舍悯，即頂點之間的連線是沒有方向的，則稱該圖為無向圖睡雇。

(2)有向圖:
在一個圖中萌衬，如果任意兩個頂點構(gòu)成的偶對(v,w)∈E 是有序的，即頂點之間的連線是有方向的它抱，則稱該圖為有向圖秕豫。一般記作<v,w>

(3)完全無向圖:
在一個無向圖中，如果任意兩頂點都有一條直接邊相連接观蓄，則稱該圖為完全無向圖混移。在一個含有 n 個頂點的完全無向圖中，有n(n-1)/2條邊侮穿。

(4)完全有向圖:
在一個有向圖中歌径，如果任意兩頂點之間都有方向互為相反的兩條弧相連接，則稱該圖為完全有向圖亲茅。在一個含有 n 個頂點的完全有向圖中回铛，有n(n-1)條邊。

(5)稠密圖克锣、稀疏圖:
若一個圖接近完全圖茵肃，稱為稠密圖;稱邊數(shù)很少()的圖為稀疏圖。

(6)頂點的度袭祟、入度验残、出度:
頂點的度(degree)是指依附于某頂點的邊數(shù)，通常記為TD()巾乳。
在無向圖中您没，所有頂點度的和是圖中邊的2倍故俐。
在有向圖中，要區(qū)別頂點的入度(Indegree)與出度(Outdegree)的概念紊婉。
頂點的入度是指以頂點為終點的弧的數(shù)目药版，記為ID ();
頂點出度是指以頂點為始點的弧的數(shù)目，記為 OD()喻犁。
頂點的出度與入度之和稱為的度槽片，記為TD()。即TD()=OD()+ID ()肢础。

(7)邊的權(quán)还栓、網(wǎng)圖:
與邊有關(guān)的數(shù)據(jù)信息稱為權(quán)(weight)。在實際應用中传轰，權(quán)值可以有某種含義剩盒。
邊上帶權(quán)的圖稱為網(wǎng)圖或網(wǎng)絡(network)。如果邊是有方向的帶權(quán)圖慨蛙，則就是一個有向網(wǎng)圖辽聊。

(8)路徑、路徑長度:
對無向圖期贫，若從頂點經(jīng)過若干條邊能到達跟匆，則稱頂點和是連通的，又稱頂點到有路徑通砍。
對有向圖玛臂，從頂點到有有向路徑，指的是從頂點經(jīng)過若干條有向邊能到達封孙。
路徑上邊或有向邊(弧)的數(shù)目稱為路徑長度迹冤。

(9)簡單路徑、回路虎忌、簡單回路:
在一條路徑中泡徙，若沒有重復相同的頂點，該路徑稱為簡單路徑呐籽。
第一個頂點和最后一個頂點相同的路徑稱為回路(環(huán))锋勺。
除第一個頂點與最后一個頂點之外，其他頂點不重復出現(xiàn)的回路稱為簡單回路狡蝶，或者簡單環(huán)庶橱。

(10)子圖和生成子圖:
對于圖 G=(V，E)贪惹，G’=(V’苏章，E’)，若存在 V’是 V 的子集 ，E’是 E的子集枫绅，則稱圖 G’是 G 的一個子圖泉孩；
若V’=V且E’是E的子集，則稱圖G’是G的一個生成子圖并淋。

(11)連通圖寓搬、連通分量:
對無向圖G=(V,E)，若任意 都是連通的县耽，則稱該圖是連通圖句喷，否則稱為非連通圖。
若G是非連通圖兔毙，則極大連通子圖稱為連通分量唾琼。
極大的含義：指的是對子圖再增加圖G中的其它頂點，子圖就不再連通澎剥。
任何連通圖的連通分量只有一個锡溯，即本身，而非連通圖有多個連通分量哑姚。

(12)強連通圖祭饭、強連通分量:
對于有向圖來說，若圖中任意一對頂點均有從一個頂點到另一個頂點有路徑蜻懦，也有從到的路徑甜癞，則稱該有向圖是強連通圖。
有向圖的極大強連通子圖稱為強連通分量宛乃。
強連通圖只有一個強連通分量，即本身蒸辆。非強連通圖有多個強連通分量征炼。

(13)生成樹:
一個連通圖(無向圖)的生成樹是一個極小連通子圖，它含有圖中全部n個頂點和只有足以構(gòu)成一棵樹的n-1條邊躬贡，稱為圖的生成樹谆奥。

(14)生成森林:
有向樹是只有一個頂點的入度為0，其余頂點的入度均為1的有向圖拂玻。
有向圖的生成森林是這樣一個子圖酸些，由若干棵有向樹組成，含有圖中全部頂點檐蚜。

3 圖的存儲結(jié)構(gòu)和基本操作

(1)鄰接矩陣法(Adjacency Matrix)
基本思想：對于有n個頂點的圖魄懂，用一維數(shù)組vexs[n]存儲頂點信息，用二維數(shù)組A[n][n]存儲頂點之間關(guān)系的信息闯第。該二維數(shù)組稱為鄰接矩陣市栗。
在鄰接矩陣中，以頂點在vexs數(shù)組中的下標代表頂點，鄰接矩陣中的元素A[i][j]存放的是頂點i到頂點j之間關(guān)系的信息填帽。

1)無向圖的數(shù)組表示
①無向無權(quán)圖的鄰接矩陣
無向無權(quán)圖其鄰接矩陣是n階對稱方陣蛛淋。
若兩條邊相連,A[i][j]=1; 若不相連A[i][j]=0。

無向圖的鄰接矩陣

②無向帶權(quán)圖的鄰接矩陣
若兩條邊相連篡腌，褐荷，W為權(quán)值。
若兩條邊不相連嘹悼，A[i][j]=

帶權(quán)無向圖的鄰接矩陣

③無向圖鄰接矩陣的特性
無向圖的鄰接矩陣一定是一個對稱矩陣诚卸。因此，在具體存放鄰接矩陣時只需存放 上(或下)三角矩陣的元素即可绘迁。
對于頂點合溺，其度數(shù)是第i行的非0元素(或非元素)的個數(shù)。
無向圖的邊數(shù)是上（或下）三角形矩陣的非0元素(或非元素)的個數(shù)缀台。

2)有向圖的數(shù)組表示
①有向無權(quán)圖的鄰接矩陣
若有向無權(quán)圖G=(V,E)有n個頂點棠赛，則其鄰接矩陣是n階方陣：
若從到有弧，A[i][j]=1膛腐；
若從到沒有弧睛约，A[i][j]=0；

有向圖的鄰接矩陣

②有向帶權(quán)圖的鄰接矩陣

有向帶權(quán)圖的鄰接矩陣

③有向圖鄰接矩陣的特性
對于頂點哲身，第i行的非0元素(或非元素)的個數(shù)是其出度OD()辩涝；
第i列的非0元素(或非元素)的個數(shù)是其入度ID();
鄰接矩陣中非0元素(或非元素)的個數(shù)就是圖的弧的個數(shù)。

對于n個頂點e條邊的無向圖勘天，鄰接矩陣表示時有nn個元素怔揩，2e個非0元素。
對于n個頂點e條邊的有向圖脯丝，鄰接矩陣表示時有nn個元素商膊，e個非0元素。

3)圖的鄰接矩陣的操作
定義兩個數(shù)組分別存儲頂點信息(數(shù)據(jù)元素)和邊或弧的信息(數(shù)據(jù)元素之間的關(guān)系) 宠进。

#define INFINITY 65535//定義無窮
#define MAX_VEX 30 //最大頂點數(shù)目

typedef enum {
    DG, AG, WDG, WAG  //{有向圖晕拆，無向圖，帶權(quán)有向圖材蹬，帶權(quán)無向圖}
} GraphKind;

typedef struct {
    GraphKind kind; /* 圖的種類標志 */
    int verxtexNum, arcNum; /* 圖的當前頂點數(shù)和弧數(shù) */
    char vexs[MAX_VEX]; //頂點集合
    int edges[MAX_VEX][MAX_VEX];//鄰接矩陣
} MGraph;/* 圖的結(jié)構(gòu)定義 */

圖的各種操作实幕。
①圖的創(chuàng)建

MGraph *createGraph(MGraph *G) {
    printf("請輸入圖的種類標志:");
    scanf("%d", &G->kind);
    G->verxtexNum = 0; /* 初始化頂點個數(shù) */
    return (G);
}

②圖的頂點定位
實際上是確定一個頂點在 vexs 數(shù)組中的位置(下標) ，其過程完全等同于在順序存儲的線性表中查找一個數(shù)據(jù)元素堤器。

int LocateVex(MGraph *G, char ch) {
    for (int i = 0; i < G->verxtexNum; i++) {
        if (G->vexs[i] == ch) {
            return (i);
        }
    }
    return (-1); /*圖中無此頂點*/
}

③向圖中增加頂點
向圖中增加一個頂點的操作昆庇，類似在順序存儲的線性表的末尾增加一個數(shù)據(jù)元素。

int addVertex(MGraph *G, char ch) {
    int j, k;
    if (G->verxtexNum >= MAX_VEX) {
        printf("Vertex overflow!\n");
        return (-1);
    }
    if (LocateVex(G, ch) != -1) {
        printf("Vertex has existed!\n");
        return (-1);
    }
    k = G->verxtexNum;
    G->vexs[G->verxtexNum++] = ch;
    if (G->kind == DG || G->kind == AG) {//不帶權(quán)
        for (j = 0; j < G->verxtexNum; j++) {//新加一行和一列
            G->edges[j][k] = G->edges[k][j] = 0;
        }
    } else {
        for (j = 0; j < G->verxtexNum; j++) {
            G->edges[j][k] = G->edges[k][j] = INFINITY;
        }
    }
    return (k);
}

④向圖中增加一條弧
根據(jù)給定的弧或邊所依附的頂點吼旧，修改鄰接矩陣中所對應的數(shù)組元素凰锡。

int addArc(MGraph *G, char ch1, char ch2, int weight) {
    int j = LocateVex(G, ch1);
    int k = LocateVex(G, ch2);
    if (k == -1 || j == -1) {
        printf("Vertex do not exist!\n");
        return (-1);
    }
    if (G->kind == DG || G->kind == WDG) {//有向圖
        G->edges[j][k] == weight;
    } else {//無向圖
        G->edges[j][k] == weight;
        G->edges[k][j] == weight;
    }
    return (1);
}

(2)鄰接鏈表法
1)基本思想：類似于樹的孩子鏈表法，就是對于圖 G 中的每個頂點，將所有鄰接于的頂點鏈成一個單鏈表掂为，這個單鏈表就稱為頂點的鄰接鏈表裕膀，再將所有點的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接鏈表勇哗。

無向圖及其鄰接表

對無向圖扰法，其鄰接鏈表是唯一(按順序鏈接)的蛹含；對有向圖，其鄰接鏈表有兩種形式塞颁。

有向圖及其鄰接表

2)從圖的鄰接表存儲方法容易看出浦箱，這種表示具有以下特點:
①表頭向量中每個分量就是一個單鏈表的頭結(jié)點，分量個數(shù)就是圖中的頂點數(shù)目祠锣。
②在邊稀疏的情況下酷窥，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間。
③在無向圖的鄰接表中伴网，頂點的度恰為第 i 個鏈表中的結(jié)點數(shù)蓬推。
④有向圖可以建立一個正鄰接表和逆鄰接表，便于統(tǒng)計每個結(jié)點的出度和入度澡腾。
⑤在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點沸伏，但要判定任意兩個頂點(和)之間是否有邊或弧相連，則需搜索第 i 個或第 j 個鏈表蛋铆，因此馋评，不及鄰接矩陣方便。

對于n個頂點e條邊的無向圖刺啦，鄰接表表示時有n個表頭結(jié)點，2e個表結(jié)點纠脾。
對于n個頂點e條邊的有向圖玛瘸，鄰接表表示時有n個表頭結(jié)點，表結(jié)點數(shù)不確定苟蹈，但正鄰接表加上逆鄰接表表結(jié)點數(shù)為e糊渊。

3)表結(jié)點及其類型定義

#define MAX_VEX 30 /* 最大頂點數(shù) */

typedef enum {
    DG, AG, WDG, WAG
} GraphKind;

typedef struct LinkNode {
    int adjvex;//鄰接點在頭結(jié)點數(shù)組中的位置(下標)
    int weight;//權(quán)值
    struct LinkNode *nextarc;//指向下一個表結(jié)點
} LinkNode;/*表結(jié)點類型定義 */

typedef struct VexNode {
    char data; // 頂點信息
    LinkNode *firstarc; // 指向第一個表結(jié)點
} VexNode;/* 頂點結(jié)點類型定義 */

typedef struct {
    GraphKind kind;/*圖的種類標志 */
    int vexnum;//頂點數(shù)
    VexNode AdjList[MAX_VEX];//鄰接表
} ALGraph;/* 圖的結(jié)構(gòu)定義 */

圖的各種操作
①圖的創(chuàng)建

ALGraph *createGraph(ALGraph *G) {
    printf("請輸入圖的種類標志:");
    scanf("%d", &G->kind);
    G->vexnum = 0; /*初始化頂點個數(shù)*/
    return (G);
}

②頂點定位
圖的頂點定位實際上是確定一個頂點在 AdjList 數(shù)組中的某個元素的 data 域內(nèi)容。

int LocateVex(ALGraph *G, char ch) {
    for (int i = 0; i < G->vexnum; i++) {
        if (G->AdjList[i].data == ch) {
            return (i);
        }
    }
    return (-1);/* 圖中無此頂點*/
}

③向圖中增加頂點
向圖中增加一個頂點的操作慧脱，在 AdjList 數(shù)組的末尾增加一個數(shù)據(jù)元素渺绒。

int AddVertex(ALGraph *G, char ch) {
    int k;
    if (G->vexnum >= MAX_VEX) {
        printf("Vertex Overflow !\n");
        return (-1);
    }
    if (LocateVex(G, ch) != -1) {
        printf("Vertex has existed !\n");
        return (-1);
    }
    G->AdjList[G->vexnum].data = ch;
    G->AdjList[G->vexnum].firstarc = NULL;
    k = ++G->vexnum;
    return k;
}

④向圖中增加一條弧
根據(jù)給定弧或邊所依附的頂點，修改單鏈表，無向圖修改兩個單鏈表;有向圖修改一個單鏈表宗兼。

int addArc(ALGraph *G, char ch1, char ch2, int weight) {
    int k, j;
    LinkNode *p, *q;
    k = LocateVex(G, ch1);
    j = LocateVex(G, ch2);
    if (k == -1 || j == -1) {
        printf("Arc’s Vertex do not exist!\n");
        return (-1);
    }
    p = (LinkNode *) malloc(sizeof(LinkNode));
    p->weight = weight;
    q = (LinkNode *) malloc(sizeof(LinkNode));
    q->weight = weight;
    if (G->kind == AG || G->kind == WAG) {//無向圖躏鱼，用頭插入法插入到兩個單鏈表
        p->nextarc = G->AdjList[k].firstarc;
        G->AdjList[k].firstarc = p;
        q->nextarc = G->AdjList[j].firstarc;
        G->AdjList[j].firstarc = q;
    } else {
        p->nextarc = G->AdjList[k].firstarc;
        G->AdjList[k].firstarc = p;   /*建立正鄰接鏈表用 */

//        q->nextarc = G->AdjList[j].firstarc;
//        G->AdjList[j].firstarc = q;/*建立逆鄰接鏈表用 */
    }
    return (1);
}

(3) 十字鏈表法
十字鏈表(Orthogonal List)是有向圖的另一種鏈式存儲結(jié)構(gòu)，是將有向圖的正鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表殷绍。
在這種結(jié)構(gòu)中染苛，每條弧的弧頭結(jié)點和弧尾結(jié)點都存放在鏈表中，并將弧結(jié)點分別組織到以弧尾結(jié)點為頭(頂點)結(jié)點和以弧頭結(jié)點為頭(頂點)結(jié)點的鏈表中主到。這種結(jié)構(gòu)的結(jié)點邏輯結(jié)構(gòu)如圖所示茶行。

十字鏈表結(jié)點結(jié)構(gòu)

data 域:存儲和頂點相關(guān)的信息;
指針域 firstin:指向以該頂點為弧頭的第一條弧所對應的弧結(jié)點，即逆鄰接鏈表;
指針域 firstout:指向以該頂點為弧尾的第一條弧所對應的弧結(jié)點登钥，即正鄰接鏈表;
尾域 tailvex:指示弧尾頂點在圖中的位置;
頭域 headvex:指示弧頭頂點在圖中的位置;
指針域 hlink:指向弧頭相同的下一條弧;
指針域 tlink:指向弧尾相同的下一條弧;
Info 域:指向該弧的相關(guān)信息畔师，比如權(quán)值;
結(jié)點類型定義：

#define MAX_VEX 30 /* 最大頂點數(shù) */
#define INFINITY 65535/* 最大值∞ */
#define MAX_VEX 30//最大頂點數(shù)
typedef struct ArcNode {
    int tailvex, headvex;//尾結(jié)點和頭結(jié)點在圖中的位置
    int  info;//權(quán)值
    struct ArcNode *hlink, *tlink;
} ArcNode;/* 弧結(jié)點類型定義 */

typedef struct VexNode {
    char data; // 頂點信息
    ArcNode *firstin, *firstout;
} VexNode;/* 頂點結(jié)點類型定義 */

typedef struct {
    int vexnum;
    VexNode xlist[MAX_VEX];
} OLGraph; /* 圖的類型定義 */

下圖所示是一個有向圖及其十字鏈表(略去了表結(jié)點的 info 域)。實質(zhì)就是先把圖的正鄰接鏈表(出度)畫出來牧牢，然后再把firstin,firstout,hlink,tlink連起來看锉。

有向圖及其十字鏈表

(4)鄰接多重表法
鄰接多重表(Adjacency Multilist)是無向圖的另一種鏈式存儲結(jié)構(gòu)。
鄰接多重表的結(jié)構(gòu)和十字鏈表類似结执，每條邊用一個結(jié)點表示度陆。
鄰接多重表中的頂點結(jié)點結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點包括六個域献幔。

鄰接多重表結(jié)點定義

data 域:存儲和頂點相關(guān)的信息;
指針域 firstedge:指向依附于該頂點的第一條邊所對應的表結(jié)點;
標志域 mark:用以標識該條邊是否被訪問過;
ivex 和 jvex 域:分別保存該邊所依附的兩個頂點在圖中的位置;
info 域:保存該邊的相關(guān)信息;
指針域 ilink:指向下一條依附于頂點 ivex 的邊;
指針域 jlink:指向下一條依附于頂點 jvex 的邊;

結(jié)點類型定義:

#define MAX_VEX 30 /* 最大頂點數(shù) */

typedef enum {
    unvisited, visited
} Visitting;

typedef struct EdgeNode {
    Visitting mark; // 訪問標記
    int ivex, jvex; // 該邊依附的兩個結(jié)點在圖中的位置
    int  weight; //權(quán)值
    struct EdgeNode *ilink, *jlink;// 分別指向依附于這兩個頂點的下一條邊
} EdgeNode; /* 弧邊結(jié)點類型定義 */

typedef struct VexNode {
    char data; // 頂點信息
    EdgeNode *firsedge; // 指向依附于該頂點的第一條邊
} VexNode;/* 頂點結(jié)點類型定義 */

typedef struct {
    int vexnum;
    VexNode mullist[MAX_VEX];
} AMGraph;

鄰接多重表與鄰接表的區(qū)別:后者的同一條邊用兩個表結(jié)點表示懂傀，而前者只用一個表結(jié)點表示;除標志域外，鄰接多重表與鄰接表表達的信息是相同的蜡感，因此蹬蚁，操作的實現(xiàn)也基本相似。

無向圖及其鄰接多重表