資料結構與演算法 -- 圖（鄰接矩陣）原理詳解
摘要：
PS：圖在資料結構中有著非常大的分量，它比樹有著更為複雜的形式結構，這裡就不再說圖的基本概念，直接就說圖的儲存結構，鄰接矩陣和鄰接表。圖是有方向的，有方向的叫做弧，無方向的叫做邊。儲存圖中各頂點本身資料，使用一維陣列就足夠了；儲存頂點之間的關係時，要記錄每個頂點和其它所有頂點之間的關係，所以需...
PS：圖在資料結構中有著非常大的分量，它比樹有著更為複雜的形式結構，這裡就不再說圖的基本概念，直接就說圖的儲存結構，鄰接矩陣和鄰接表。圖是有方向的，有方向的叫做弧，無方向的叫做邊。儲存圖中各頂點本身資料，使用一維陣列就足夠了；儲存頂點之間的關係時，要記錄每個頂點和其它所有頂點之間的關係，所以需要使用二維陣列。圖在大多行業中的使用也是很多的，比如說遊戲中兩個人物的定址，自動尋路，就是圖與圖直接經過計算然後移動。後序還會介紹Dijkstra（迪傑斯特拉)演算法計算最短路徑問題。
下面介紹鄰接矩陣原理：
下面可以看到頂點之間有一定的聯絡，如果想要把他們存放在計算機中怎麼存入呢，首先我們想到的是把頂點存在一維陣列中，那麼他們的關係存在在二維陣列中，就好像是如下格式，A->B 權值是10，B->E 權值30。(下方1為有關係，0為沒有關係，未加入權值)
思路
首先把要知道頂點和邊數，然後單獨把頂點存在一維陣列中，根據邊來確定兩個頂點之間的聯絡，比如說第一條邊，是A->B。歸根結底也是通過陣列來儲存。當然這是鄰接矩陣。
步驟
- 定義結構體
- 輸入頂點和邊數
- 通過頂點和邊數初始化資料（內部全是0或者是無窮）
- 打印表
- 遍歷（深度和廣度優先遍歷）
1：結構體定義
typedef char VertexType;
typedef int EdgeType;
#define MAXVEX 100
#define IUNFINITY 65535
typedef struct {
VertexType vexs[MAXVEX];/* 頂點表*/
EdgeType arc[MAXVEX][MAXVEX];/* 鄰接矩陣 */
int vnum, edgenum;/*定點的個數和邊的個數*/
} MGraphy;
2：資料初始化
程式碼中有很多註釋，有沒有用到的，但是一種經驗。
//加入權值
void createGraphyWeight(MGraphy *g) {
printf("輸入總頂點(空格)邊數\n");
scanf("%d %d", &g->vnum, &g->edgenum);
printf("輸入 頂點表示:\n");
//頂點請輸入;
for (int i = 0; i < g->vnum; i++) {
printf("請輸入第%d個頂點", (i + 1));
//fflush(stdin);//不起作用，資料顯示一些linux平臺下一些庫沒有定義這個方法。
//flushall(); //清除多餘的回車符。
//如果不加入getchar的話，在for迴圈中就會先執行一遍scanf，因為上面可能會有一些回車，導致執行一遍scanf。需要清除之前的回車。
getchar();
scanf("%c", &g->vexs[i]);
}
for (int i = 0; i < g->vnum; i++) {// 初始化陣列元素 Infonity
for (int j = 0; j < g->vnum; j++) {
//g->arc[i][j] = IUNFINITY;//對於加權值的預設全部設定為最大值，
g->arc[i][j] = 0;//對於未加權值的預設全部設定為0
}
}
printf("輸入邊有關的兩個頂點，\n");
for (int i = 0; i < g->edgenum; i++) {
char a, b;
int c ;
printf("輸入第 %d 條邊有關的兩個頂點加權值（空格隔開）,沒有權值輸入0\n ", (i + 1));
getchar();
//setbuf(stdin,NULL);
scanf("%c %c %d", &a, &b,&c);
int ii = localGV(g, a);
int jj = localGV(g, b);
if(c == 0){
c=1;
}
//printf("c的值是%d",c);
g->arc[ii][jj] = c;
g->arc[jj][ii] = c;// 無向圖
}
printfL(g);
}
3：打印表
void printfL(MGraphy *g) {
//輸出圖的資訊
printf("表為 :\n");
int i = 0;
//先列印行標題；頂點標題
for (i = 0; i < g->vnum + 1; i++) {
if (i > 0) {
printf("%c\t", g->vexs[i - 1]);
} else {
printf("\\\t");
}
}
printf("\n");
for (i = 0; i < g->vnum; i++) {
printf("%c\t", g->vexs[i]);
for (int j = 0; j < g->vnum; j++) {
printf("%d\t", g->arc[i][j]);
}
printf("\n");
}
}
4：深度優先遍歷
這裡的深度優先遍歷只給出程式碼，原理後序會給出。
//深度優先搜尋
void DFSTraverse(MGraphy *G){//
int v;
//將用做標記的visit陣列初始化為false
for( v = 0; v < G->vnum; ++v){
visited[v] = false;
}
//對於每個標記為false的頂點呼叫深度優先搜尋函式
for( v = 0; v < G->vnum; v++){
//如果該頂點的標記位為false，則呼叫深度優先搜尋函式
if(!visited[v]){
DFS(G, v);
}
}
}
int FirstAdjVex(MGraphy *g,int v)
{
//查詢與陣列下標為v的頂點之間有邊的頂點，返回它在陣列中的下標
for(int i = 0; i<g->vnum; i++){
if( g->arc[v][i]){
return i;
}
}
return -1;
}
int NextAdjVex(MGraphy *G,int v,int w)
{
//從前一個訪問位置w的下一個位置開始，查詢之間有邊的頂點
for(int i = w+1; i<G->vnum; i++){
//最關鍵的一個判斷，除錯了很久，讓其等於'1'或者 !=0 ,否則該字元不知道後面還是否有值相連線。
if(G->arc[v][i] != 0){
return i;
}
}
return -1;
}
void DFS(MGraphy *g,int v){
visited[v]= true;
printf("%c",g->vexs[v]);//輸入data值
//從該頂點的第一個邊開始，一直到最後一個邊，對處於邊另一端的頂點呼叫DFS函式
int w;
for( w= FirstAdjVex(g,v); w>=0; w = NextAdjVex(g,v,w)){
//如果該頂點的標記位false，證明未被訪問，呼叫深度優先搜尋函式
if(!visited[w]){
DFS(g,w);
}
}
}
完