⑴ 圖的基本概念，圖的存儲--鄰接矩陣、鄰接表、十字鏈表、鄰接多重表
一個圖(G)定義為一個偶對(V,E)，記為G=(V,E)。
V是頂點(Vertex)的非空有限集合，記為V(G)。
E是無序集V&V的一個子集，記為E(G)，其元素是圖的弧(Arc)。
將頂點集合為空的圖稱為空圖。
弧：表示兩個頂點v和w之間存在一個關系，用頂點偶對<v,w>表示。
(1)無向圖:
在一個圖中，如果任意兩個頂點構成的偶對(v,w)∈E 是無序的，即頂點之間的連線是沒有方向的，則稱該圖為無向圖。
(2)有向圖:
在一個圖中，如果任意兩個頂點構成的偶對(v,w)∈E 是有序的，即頂點之間的連線是有方向的，則稱該圖為有向圖。一般記作<v,w>
(3)完全無向圖:
在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該圖為完全無向圖。在一個含有 n 個頂點的完全無向圖中，有n(n-1)/2條邊。
(4)完全有向圖:
在一個有向圖中，如果任意兩頂點之間都有方向互為相反的兩條弧相連接，則稱該圖為完全有向圖。在一個含有 n 個頂點的完全有向圖中，有n(n-1)條邊。
(5)稠密圖、稀疏圖:
若一個圖接近完全圖，稱為稠密圖;稱邊數很少( )的圖為稀疏圖。
(6)頂點的度、入度、出度:
頂點的度(degree)是指依附於某頂點 的邊數，通常記為TD( )。
在無向圖中，所有頂點度的和是圖中邊的2倍。
在有向圖中，要區別頂點的入度(Indegree)與出度(Outdegree)的概念。
頂點 的入度是指以頂點為終點的弧的數目，記為ID ( );
頂點 出度是指以頂點 為始點的弧的數目，記為 OD( )。
頂點 的出度與入度之和稱為 的度，記為TD( )。即TD( )=OD( )+ID ( )。
(7)邊的權、網圖:
與邊有關的數據信息稱為權(weight)。在實際應用中，權值可以有某種含義。
邊上帶權的圖稱為網圖或網路(network)。如果邊是有方向的帶權圖，則就是一個有向網圖。
(8)路徑、路徑長度:
對無向圖，若從頂點 經過若干條邊能到達 ，則稱頂點 和 是連通的，又稱頂點 到 有路徑。
對有向圖，從頂點 到 有有向路徑，指的是從頂點 經過若干條有向邊能到達 。
路徑上邊或有向邊(弧)的數目稱為路徑長度。
(9)簡單路徑、迴路、簡單迴路:
在一條路徑中，若沒有重復相同的頂點，該路徑稱為簡單路徑。
第一個頂點和最後一個頂點相同的路徑稱為迴路(環)。
除第一個頂點與最後一個頂點之外，其他頂點不重復出現的迴路稱為簡單迴路，或者簡單環。
(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個頂點和只有足以構成一棵樹的n-1條邊，稱為圖的生成樹。
(14)生成森林:
有向樹是只有一個頂點的入度為0，其餘頂點的入度均為1的有向圖。
有向圖的生成森林是這樣一個子圖，由若干棵有向樹組成，含有圖中全部頂點。
(1)鄰接矩陣法(Adjacency Matrix)
基本思想：對於有n個頂點的圖，用一維數組vexs[n]存儲頂點信息，用二維數組A[n][n]存儲頂點之間關系的信息。該二維數組稱為鄰接矩陣。
在鄰接矩陣中，以頂點在vexs數組中的下標代表頂點，鄰接矩陣中的元素A[i][j]存放的是頂點i到頂點j之間關系的信息。
1)無向圖的數組表示
①無向無權圖的鄰接矩陣
無向無權圖其鄰接矩陣是n階對稱方陣。
若兩條邊相連,A[i][j]=1; 若不相連A[i][j]=0。
②無向帶權圖的鄰接矩陣
若兩條邊相連， ，W為權值。
若兩條邊不相連，A[i][j]=
③無向圖鄰接矩陣的特性
無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放 上(或下)三角矩陣的元素即可。
對於頂點 ，其度數是第i行的非0元素(或非 元素)的個數。
無向圖的邊數是上（或下）三角形矩陣的非0元素(或非 元素)的個數。
2)有向圖的數組表示
①有向無權圖的鄰接矩陣
若有向無權圖G=(V,E)有n個頂點，則其鄰接矩陣是n階方陣：
若從 到 有弧，A[i][j]=1；
若從 到 沒有弧，A[i][j]=0；
②有向帶權圖的鄰接矩陣
③有向圖鄰接矩陣的特性
對於頂點 ，第i行的非0元素(或非 元素)的個數是其出度OD( )；
第i列的非0元素(或非 元素)的個數是其入度ID( );
鄰接矩陣中非0元素(或非 元素)的個數就是圖的弧的個數。
對於n個頂點e條邊的無向圖，鄰接矩陣表示時有n n個元素，2 e個非0元素。
對於n個頂點e條邊的有向圖，鄰接矩陣表示時有n n個元素，e個非0元素。
3)圖的鄰接矩陣的操作
定義兩個數組分別存儲頂點信息(數據元素)和邊或弧的信息(數據元素之間的關系) 。
圖的各種操作。
①圖的創建
②圖的頂點定位
實際上是確定一個頂點在 vexs 數組中的位置(下標) ，其過程完全等同於在順序存儲的線性表中查找一個數據元素。
③向圖中增加頂點
向圖中增加一個頂點的操作，類似在順序存儲的線性表的末尾增加一個數據元素。
④向圖中增加一條弧
根據給定的弧或邊所依附的頂點，修改鄰接矩陣中所對應的數組元素。
(2)鄰接鏈表法
1)基本思想：類似於樹的孩子鏈表法，就是對於圖 G 中的每個頂點 ，將所有鄰接於 的頂點 鏈成一個單鏈表，這個單鏈表就稱為頂點 的鄰接鏈表，再將所有點的鄰接表表頭放到數組中，就構成了圖的鄰接鏈表。
對無向圖，其鄰接鏈表是唯一(按順序鏈接)的；對有向圖，其鄰接鏈表有兩種形式。
2)從圖的鄰接表存儲方法容易看出，這種表示具有以下特點:
①表頭向量中每個分量就是一個單鏈表的頭結點，分量個數就是圖中的頂點數目。
②在邊稀疏的情況下，用鄰接表表示圖比鄰接矩陣節省存儲空間。
③在無向圖的鄰接表中，頂點 的度恰為第 i 個鏈表中的結點數。
④有向圖可以建立一個正鄰接表和逆鄰接表，便於統計每個結點的出度和入度。
⑤在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點( 和 )之間是否有邊或弧相連，則需搜索第 i 個或第 j 個鏈表，因此，不及鄰接矩陣方便。
對於n個頂點e條邊的無向圖，鄰接表表示時有n個表頭結點，2 e個表結點。
對於n個頂點e條邊的有向圖，鄰接表表示時有n個表頭結點，表結點數不確定，但正鄰接表加上逆鄰接表表結點數為e。
3)表結點及其類型定義
圖的各種操作
①圖的創建
②頂點定位
圖的頂點定位實際上是確定一個頂點在 AdjList 數組中的某個元素的 data 域內容。
③向圖中增加頂點
向圖中增加一個頂點的操作，在 AdjList 數組的末尾增加一個數據元素。
④向圖中增加一條弧
根據給定弧或邊所依附的頂點，修改單鏈表，無向圖修改兩個單鏈表;有向圖修改一個單鏈表。
(3) 十字鏈表法
十字鏈表(Orthogonal List)是有向圖的另一種鏈式存儲結構，是將有向圖的正鄰接表和逆鄰接表結合起來得到的一種鏈表。
在這種結構中，每條弧的弧頭結點和弧尾結點都存放在鏈表中，並將弧結點分別組織到以弧尾結點為頭(頂點)結點和以弧頭結點為頭(頂點)結點的鏈表中。這種結構的結點邏輯結構如圖所示。
data 域:存儲和頂點相關的信息;
指針域 firstin:指向以該頂點為弧頭的第一條弧所對應的弧結點，即逆鄰接鏈表;
指針域 firstout:指向以該頂點為弧尾的第一條弧所對應的弧結點，即正鄰接鏈表;
尾域 tailvex:指示弧尾頂點在圖中的位置;
頭域 headvex:指示弧頭頂點在圖中的位置;
指針域 hlink:指向弧頭相同的下一條弧;
指針域 tlink:指向弧尾相同的下一條弧;
Info 域:指向該弧的相關信息，比如權值;
結點類型定義：
下圖所示是一個有向圖及其十字鏈表(略去了表結點的 info 域)。實質就是先把圖的正鄰接鏈表(出度)畫出來，然後再把firstin,firstout,hlink,tlink連起來。
(4)鄰接多重表法
鄰接多重表(Adjacency Multilist)是無向圖的另一種鏈式存儲結構。
鄰接多重表的結構和十字鏈表類似，每條邊用一個結點表示。
鄰接多重表中的頂點結點結構與鄰接表中的完全相同，而表結點包括六個域。
data 域:存儲和頂點相關的信息;
指針域 firstedge:指向依附於該頂點的第一條邊所對應的表結點;
標志域 mark:用以標識該條邊是否被訪問過;
ivex 和 jvex 域:分別保存該邊所依附的兩個頂點在圖中的位置;
info 域:保存該邊的相關信息;
指針域 ilink:指向下一條依附於頂點 ivex 的邊;
指針域 jlink:指向下一條依附於頂點 jvex 的邊;
結點類型定義:
鄰接多重表與鄰接表的區別:後者的同一條邊用兩個表結點表示，而前者只用一個表結點表示;除標志域外，鄰接多重表與鄰接表表達的信息是相同的，因此，操作的實現也基本相似。
⑵ 鄰接矩陣vex是什麼意思
typedef char VertexType[MAX_NAME];
。。。。。
2. typedef struct
3. {
4. VertexType vexs[MAX_VERTEX_NUM]; // 頂點向量
5. AdjMatrix arcs; // 鄰接矩陣
6. int vexnum,arcnum; // 圖的當前頂點數和弧數
7. GraphKind kind; // 圖的種類標志
8. } MGraph;
。。。。。。
9.
10. VertexType *GetVex(MGraph G,int v)
11. {
12. // 初始條件: 圖G存在，v是G中某個頂點的序號。操作結果: 返回v的值
13. if(v>=G.vexnum||v<0)
14. exit(ERROR);
15. return G.vexs[v];
16. }
17. int main()
18. {
19. .
20. printf("%s ",*GetVex(G,v));
21. ..
22. }
編譯執行時，提示「15行：warning: function returns address of local variable」，執行時到這個函數就卡住了，問一下怎麼修改？
⑶ 圖的存儲結構——所存儲的信息有哪些
一、鄰接矩陣存儲方法
鄰接矩陣是表示頂點之間相鄰關系的矩陣。
設G=(V，E)是具有n（n＞0）個頂點的圖，頂點的順序依次為0～n-1，則G的鄰接矩陣A是n階方陣，其定義如下：
（1）如果G是無向圖，則：
A[i][j]=1：若(i,j)∈E(G) 0:其他
（2）如果G是有向圖，則：
A[i][j]=1：若<i,j>∈E(G) 0:其他
（3）如果G是帶權無向圖，則：
A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他
（4）如果G是帶權有向圖，則：
A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j∞：其他
注意：帶權圖和不帶權圖表示的元素類型不同。
帶權圖（不論有向還是無向圖）A[i][j]用double表示，不帶權圖（不論有向還是無向圖）A[i][j]用int表示。
用一維數組G[ ]存儲有4個頂點的無向圖如：G[ ] = { 0, 1, 0, 1, 1, 0, 0, 0, 1, 0 }
則頂點2和頂點0之間是有邊的。
如：
鄰接矩陣的特點如下：
（1）圖的鄰接矩陣表示是唯一的。
（2）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲的思想，在具體存放鄰接矩陣時只需存放上（或下）三角形陣的元素即可。
（3）不帶權的有向圖的鄰接矩陣一般來說是一個稀疏矩陣。因此，當圖的頂點較多時，可以採用三元組表的方法存儲鄰接矩陣。
（4）對於無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的度。
（5）對於有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數正好是第i個頂點的出度（或入度）。
（6）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。
鄰接矩陣的數據類型定義如下：
#define MAXV <最大頂點個數>
typedef struct
{ int no; //頂點編號
InfoType info; //頂點其他信息
} VertexType; //頂點類型
typedef struct //圖的定義
{ int edges[MAXV][MAXV]; //鄰接矩陣
int n，e; //頂點數，弧數
VertexType vexs[MAXV]; //存放頂點信息
} MGraph; //圖的鄰接矩陣表示類型
二、 鄰接表存儲方法
圖的鄰接表存儲方法是一種順序分配與鏈式分配相結合的存儲方法。
在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的節點表示依附於頂點i的邊（對有向圖是以頂點i為尾的邊）。每個單鏈表上附設一個表頭節點。
其中，表節點由三個域組成，adjvex指示與頂點i鄰接的點在圖中的位置，nextarc指示下一條邊或弧的節點，info存儲與邊或弧相關的信息，如權值等。
表頭節點由兩個域組成，data存儲頂點i的名稱或其他信息，firstarc指向鏈表中第一個節點。
typedef struct ANode
{ int adjvex; //該邊的終點編號
struct ANode *nextarc; //指向下一條邊的指針
InfoType info; //該邊的相關信息
} ArcNode; //邊表節點類型
typedef struct Vnode
{ Vertex data; //頂點信息
ArcNode *firstarc; //指向第一條邊
} VNode; //鄰接表頭節點類型
typedef VNode AdjList[MAXV]; //AdjList是鄰接表類型
typedef struct
{ AdjList adjlist; //鄰接表
int n,e; //圖中頂點數n和邊數e
} ALGraph; //完整的圖鄰接表類型
鄰接表的特點如下：
（1）鄰接表表示不唯一。這是因為在每個頂點對應的單鏈表中，各邊節點的鏈接次序可以是任意的，取決於建立鄰接表的演算法以及邊的輸入次序。
（2）對於有n個頂點和e條邊的無向圖，其鄰接表有n個頂點節點和2e個邊節點。顯然，在總的邊數小於n(n-1)/2的情況下，鄰接表比鄰接矩陣要節省空間。
（3）對於無向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目正好是頂點i的度。
（4）對於有向圖，鄰接表的頂點i對應的第i個鏈表的邊節點數目僅僅是頂點i的出度。其入度為鄰接表中所有adjvex域值為i的邊節點數目。
例， 給定一個具有n個節點的無向圖的鄰接矩陣和鄰接表。
（1）設計一個將鄰接矩陣轉換為鄰接表的演算法；
（2）設計一個將鄰接表轉換為鄰接矩陣的演算法；
（3）分析上述兩個演算法的時間復雜度。
解：
（1）在鄰接矩陣上查找值不為0的元素，找到這樣的元素後創建一個表節點並在鄰接表對應的單鏈表中採用前插法插入該節點。
void MatToList(MGraph g，ALGraph *&G)
//將鄰接矩陣g轉換成鄰接表G
{ int i，j，n=g.n; ArcNode *p; //n為頂點數
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;i<n;i++) //給所有頭節點的指針域置初值
G->adjlist[i].firstarc=NULL;
for (i=0;i<n;i++) //檢查鄰接矩陣中每個元素
for (j=n-1;j>=0;j--)
if (g.edges[i][j]!=0)
{ p=(ArcNode *)malloc(sizeof(ArcNode));
//創建節點*p
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;
//將*p鏈到鏈表頭
G->adjlist[i].firstarc=p;
}
G->n=n;G->e=g.e;
}
（2）在鄰接表上查找相鄰節點，找到後修改相應鄰接矩陣元素的值。
void ListToMat(ALGraph *G，MGraph &g)
{ int i，j，n=G->n;ArcNode *p;
for (i=0;i<n;i++)
{ p=G->adjlist[i].firstarc;
while (p!=NULL)
{ g.edges[i][p->adjvex]=1;
p=p->nextarc;
}
}
g.n=n;g.e=G->e;
}
（3）演算法1的時間復雜度均為O(n2)。演算法2的時間復雜度為O(n+e)，其中e為圖的邊數。