一、 圖的定義和術(shù)語
1、 圖按照無方向和有方向分為“無向圖”和“有向圖”
無向圖是由頂點和邊構(gòu)成，有向圖是由頂點和?。ㄓ邢蜻叄?gòu)成。一條從x到y(tǒng)的弧， “弧頭”（初始點）為y，“弧尾”（終端點）為x，如上圖有向圖，A到D的弧，A為弧尾，D為弧頭。
2、 如果任意兩個頂點之間都存在邊叫“完全圖”，上方第一個圖就是完全圖，有向的邊叫“有向完全圖”
3、 帶權(quán)的圖稱為“網(wǎng)”，權(quán)可以表示一個頂點到另一個頂點的距離或耗費
4、 頂點的“度”是和頂點相關(guān)聯(lián)的邊的數(shù)目。有向圖圖中又有“入度”--方向指向頂點的邊；“出度”--方向背向頂點的邊。在有向圖中頂點的度就是入度與出度之和。
上圖：無向圖頂點3的度為3
上圖：有向圖，頂點A的入度=2，出度=3，頂點A的度=2+3=4
5、 “路徑長度”為路徑上邊或弧的數(shù)目，上圖從B到D的路徑長度為3
6、 第一個頂點和最后一個頂點相同的路徑為“回路”或“環(huán)”，序列中頂點不重復(fù)出現(xiàn)的路徑稱為“簡單路徑”，除第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路，稱為“簡單回路”或“簡單環(huán)”
7、 兩個頂點之間有路徑，則稱兩個頂點是“連通”的，任意兩個頂點都是連通的稱為“連通圖”
左圖A與E沒有連通，不是連通圖
8、 “連通分量”為無向圖中的極大連通子圖。（子圖必須是連通的且含有極大頂點數(shù)）。上圖左有兩個連通分量
9、在有向圖中，如果任意兩個頂點之間都存在路徑，則稱這個有向圖為“強連通圖”（下圖）。有向圖中的極大強連通子圖稱作有向圖的 “強連通分量”
下圖1不是強連通圖，但是有兩個強連通分量（下圖2、3）
10、 一個連通圖的“生成樹”是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的n – 1條邊，下圖右是下圖左中最大連通分量的一棵生成樹。如果在一棵生成樹上添加一條邊，必定構(gòu)成一個環(huán)，因為這條邊使得其中兩個頂點之間有了第二條路徑。一棵有n個頂點的生成樹有且僅有n – 1條邊。如果一個圖有n個頂點，n – 1條邊，是非連通圖。如果多于n – 1條邊，則一定有環(huán)。但有n – 1條邊的圖不一定是生成樹，生成樹一定有n – 1條邊。
二、 圖的存儲結(jié)構(gòu)
圖的結(jié)構(gòu)比較復(fù)雜，任意兩個頂點間都可能存在聯(lián)系，因此用多重鏈表表示圖是很自然的事，由一個數(shù)據(jù)域和多個指針域組成的結(jié)點表示一個頂點，數(shù)據(jù)域存儲該頂點的信息，指針域存儲指向其相鄰結(jié)點的指針，但是圖中各個結(jié)點度數(shù)不同，最大度數(shù)和最小度數(shù)可能相差很多，因此若按最大度數(shù)的頂點設(shè)計結(jié)點結(jié)構(gòu)，會存在浪費，若按每個頂點自己的度數(shù)設(shè)計不同的結(jié)點結(jié)構(gòu)，會給操作帶來不便。實際應(yīng)用中通常采用鄰接表，鄰接多重表和十字鏈表來進行數(shù)據(jù)的存儲。
1、 鄰接矩陣
圖的鄰接矩陣存儲方式是用兩個數(shù)組來表示圖。有n個頂點的圖，用一個長度為n的一維數(shù)組來存儲圖中頂點信息，用一個n x n的二維數(shù)組（鄰接矩陣）存儲圖中的邊或弧的信息。
圖的結(jié)構(gòu)定義：
typedef struct {
char vexs[n]; //存儲頂點信息
int arc[n][n]; //鄰接矩陣，可看作邊
int numVertexes, numEdges; //圖中當(dāng)前的頂點數(shù)和邊數(shù)
} Graph;
舉例：
A、無向圖
從上面可以看出，無向圖的邊數(shù)組是一個對稱矩陣。
從這個矩陣中，可知：
(1) 可判斷任意兩頂點是否有邊
(2) 某個頂點的度，就是這個頂點vi在鄰接矩陣中第i行（或第i列）的元素之和
(3) 頂點vi的所有鄰接點就是其所在的第i行（或第i列），值為1的元素
B、有向圖
頂點vi的出度為第i行元素的和，入度為第i列元素的和。
C、網(wǎng)圖（邊帶權(quán)值）
2、 鄰接表
對于頂點多而邊數(shù)少的圖來說，使用鄰接矩陣會使存儲空間產(chǎn)生極大的浪費，因此使用數(shù)組與鏈表相結(jié)合的存儲方式來解決這個問題，這種存儲方式稱為鄰接表。
鄰接表的處理方法：
(1) 圖中的頂點用一個一維數(shù)組存儲
(2) 圖中每個頂點vi的所有鄰接點構(gòu)成一個線性表，由于鄰接點的個數(shù)不定，所以用單鏈表存儲。每個鏈表上設(shè)一個表頭結(jié)點，表頭結(jié)點含有兩個域： 數(shù)據(jù)域（vexdata）--存儲頂點的信息，指針域（firstearc）--指向鏈表中第一個結(jié)點。表結(jié)點由三個域組成：鄰接點域（adjvex）--指示與頂點vi鄰接的點在圖中的位置，也就是存儲這個頂點的鄰接點在表中的下標(biāo)，鏈域（nextarc）--指向下一條邊或弧的結(jié)點的指針，數(shù)據(jù)域（info）--存儲和邊或弧相關(guān)的信息，如權(quán)值。
圖的結(jié)構(gòu)定義：
typedef struct EdgeNode { //表結(jié)點結(jié)構(gòu)
int adjvex; //鄰接點域，存儲該頂點對應(yīng)的下標(biāo)
int weigth; //用于存儲權(quán)值，對于非網(wǎng)圖可以不需要
struct EdgeNode *next; //鏈域，指向下一個鄰接點
} EdgeNode;
typedef struct VertexNode { //頭結(jié)點結(jié)構(gòu)
char data; //數(shù)據(jù)域，存儲頭結(jié)點信息
EdgeNode *firstedge; //指向與該頭結(jié)點相連的第一個結(jié)點的指針
} VertexNode, AdjList[n];
typedef struct {
AdjList adjList;
int numVertexes, numEdges; //圖中當(dāng)前頂點數(shù)和邊數(shù)
} GraphList;
舉例：
A、 無向圖（沒有權(quán)值，所以表結(jié)點的結(jié)構(gòu)可以不定義info這個域）
B、 網(wǎng)圖（帶權(quán)值，需要使用info這個域來存儲權(quán)值）
在無向圖的鄰接表中，頂點vi的度為第i個鏈表中的結(jié)點數(shù)，而在有向圖中，第i個鏈表中的結(jié)點數(shù)只是頂點vi的出度，求入度，須遍歷整個鄰接表，找到在所有鏈表中其連接點域的值為i的結(jié)點個數(shù)，這個個數(shù)才是頂點vi的入度。
為了便于確定頂點的入度，可以建立一個有向圖的逆鄰接表，即對每個頂點vi建立一個鏈接以vi為頭的弧的表。
在鄰接表上容易找到任意頂點的第一個鄰接點和下一個鄰接點，但要判斷任意兩個頂點間是否有邊或弧相鄰，則要搜索第i個或第j個鏈表，因此不及鄰接矩陣方便。
3、 十字鏈表
十字鏈表可以看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表，十字鏈表的結(jié)點定義如下
弧結(jié)點有四個域：尾域(tailvex)--弧尾所在的結(jié)點在表中的下標(biāo)，頭域(headvex)--弧頭所在的結(jié)點在表中的下標(biāo)，hlink--指向弧頭相同的下一條弧，tlink--指向弧尾相同的下一條弧。如果是網(wǎng)，還可以增加一個weight域來存儲權(quán)值。
頂點結(jié)點（頭結(jié)點）由三個域組成：data域--存儲和頂點相關(guān)的信息，如名稱等， firstin--指向以該頂點為弧頭的第一個弧結(jié)點，也就是入邊的第一個結(jié)點，firstout--指向以該頂點為弧尾的第一個弧結(jié)點，也就是出邊的第一個結(jié)點。
舉例：
如上圖所示的圖，實線箭頭指針的圖示完全與鄰接表相同。以頂點v0舉例，firstout指向的是出邊中的第一個結(jié)點v3。所以v0的hearvex 表示v3在整個表中的下標(biāo)為 3，之后的弧結(jié)點中所有域的值，說明的就是v0到v3這條弧。headlink指向以v0作為弧頭的另一條弧，示例中沒有，所以為空，tailvex指向以v3作為弧尾的另一條弧，示例中沒有，所以為空。
對應(yīng)頂點v0，它有兩個頂點為v1和v2的入邊。因此的firstin指向以頂點v0為弧頭的第一個弧結(jié)點，也就是尋找弧結(jié)點中handvex這個域的值為0的弧結(jié)點，如上圖圓圈1。v0還有一個入邊，因此這個弧結(jié)點的handlink指向下一個handvex為0的弧結(jié)點，如上圖圓圈2。對于頂點v1，它有一個頂點v2的入邊，所以它的firstin指向以頂點v2為弧頭的第一個弧結(jié)點，也就是尋找弧結(jié)點中handvex這個域的值為1的弧結(jié)點，如上圖圓圈3。
十字鏈表因為把鄰接表和逆鄰接表組合在一起，所有很容易找到以vi為弧尾的弧，也能很容易找到以vi為弧頭的弧，因此很容易求得任意頂點的入度和出度。
