鄰接表無向圖的介紹 鄰接表無向圖是指通過鄰接表表示的無向圖。 上面的圖G1包含了"A,B,C,D,E,F,G"共7個頂點，而且包含了"(A,C),(A,D),(A,F),(B,C),(C,D),(E,G),(F,G)"共7條邊。 上圖右邊的矩陣是G1在內存中的鄰接表示意圖。每一個頂點都包含一條鏈表，該鏈表記錄了"該頂點的鄰接點的序號"。例如，第2個頂點(頂點C)包含的鏈表所包含的節點的數據分別是"0,1,3"；而這"0,1,3"分別對應"A,B,D"的序號，"A,B,D"都是C的鄰接點。就是通過這種方式記錄圖的信息的。 鄰接表無向圖的代碼說明 1. 基本定義 復制代碼 #define MAX 100 // 鄰接表 class ListUDG { private: // 內部類 // 鄰接表中表對應的鏈表的頂點 class ENode { public: int ivex; // 該邊所指向的頂點的位置 ENode *nextEdge; // 指向下一條弧的指針 }; // 鄰接表中表的頂點 class VNode { public: char data; // 頂點信息 ENode *firstEdge; // 指向第一條依附該頂點的弧 }; private: // 私有成員 int mVexNum; // 圖的頂點的數目 int mEdgNum; // 圖的邊的數目 VNode mVexs[MAX]; public: // 創建鄰接表對應的圖(自己輸入) ListUDG(); // 創建鄰接表對應的圖(用已提供的數據) ListUDG(char vexs[], int vlen, char edges[][2], int elen); ~ListUDG(); // 打印鄰接表圖 void print(); private: // 讀取一個輸入字符 char readChar(); // 返回ch的位置 int getPosition(char ch); // 將node節點鏈接到list的最後 void linkLast(ENode *list, ENode *node); }; 復制代碼 (01) ListUDG是鄰接表對應的結構體。 mVexNum是頂點數，mEdgNum是邊數；mVexs則是保存頂點信息的一維數組。 (02) VNode是鄰接表頂點對應的結構體。 data是頂點所包含的數據，而firstEdge是該頂點所包含鏈表的表頭指針。 (03) ENode是鄰接表頂點所包含的鏈表的節點對應的結構體。 ivex是該節點所對應的頂點在vexs中的索引，而nextEdge是指向下一個節點的。 2. 創建矩陣 這裡介紹提供了兩個創建矩陣的方法。一個是用已知數據，另一個則需要用戶手動輸入數據。 2.1 創建圖(用已提供的矩陣) 復制代碼 /* * 創建鄰接表對應的圖(用已提供的數據) */ ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen) { char c1, c2; int i, p1, p2; ENode *node1, *node2; // 初始化"頂點數"和"邊數" mVexNum = vlen; mEdgNum = elen; // 初始化"鄰接表"的頂點 for(i=0; i<mVexNum; i++) { mVexs[i].data = vexs[i]; mVexs[i].firstEdge = NULL; } // 初始化"鄰接表"的邊 for(i=0; i<mEdgNum; i++) { // 讀取邊的起始頂點和結束頂點 c1 = edges[i][0]; c2 = edges[i][1]; p1 = getPosition(c1); p2 = getPosition(c2); // 初始化node1 node1 = new ENode(); node1->ivex = p2; // 將node1鏈接到"p1所在鏈表的末尾" if(mVexs[p1].firstEdge == NULL) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 node2 = new ENode(); node2->ivex = p1; // 將node2鏈接到"p2所在鏈表的末尾" if(mVexs[p2].firstEdge == NULL) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } } 復制代碼 該函數的作用是創建一個鄰接表無向圖。實際上，該方法創建的無向圖，就是上面圖G1。調用代碼如下： 復制代碼 char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'C'}, {'A', 'D'}, {'A', 'F'}, {'B', 'C'}, {'C', 'D'}, {'E', 'G'}, {'F', 'G'}}; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); ListUDG* pG; pG = new ListUDG(vexs, vlen, edges, elen); 復制代碼 2.2 創建圖(自己輸入) 復制代碼 /* * 創建鄰接表對應的圖(自己輸入) */ ListUDG::ListUDG() { char c1, c2; int v, e; int i, p1, p2; ENode *node1, *node2; // 輸入"頂點數"和"邊數" cout << "input vertex number: "; cin >> mVexNum; cout << "input edge number: "; cin >> mEdgNum; if ( mVexNum < 1 || mEdgNum < 1 || (mEdgNum > (mVexNum * (mVexNum-1)))) { cout << "input error: invalid parameters!" << endl; return ; } // 初始化"鄰接表"的頂點 for(i=0; i<mVexNum; i++) { cout << "vertex(" << i << "): "; mVexs[i].data = readChar(); mVexs[i].firstEdge = NULL; } // 初始化"鄰接表"的邊 for(i=0; i<mEdgNum; i++) { // 讀取邊的起始頂點和結束頂點 cout << "edge(" << i << "): "; c1 = readChar(); c2 = readChar(); p1 = getPosition(c1); p2 = getPosition(c2); // 初始化node1 node1 = new ENode(); node1->ivex = p2; // 將node1鏈接到"p1所在鏈表的末尾" if(mVexs[p1].firstEdge == NULL) mVexs[p1].firstEdge = node1; else linkLast(mVexs[p1].firstEdge, node1); // 初始化node2 node2 = new ENode(); node2->ivex = p1; // 將node2鏈接到"p2所在鏈表的末尾" if(mVexs[p2].firstEdge == NULL) mVexs[p2].firstEdge = node2; else linkLast(mVexs[p2].firstEdge, node2); } } 復制代碼 該函數是讀取用戶的輸入，將輸入的數據轉換成對應的無向圖。
