鄰接表有向圖的介紹 鄰接表有向圖是指通過鄰接表表示的有向圖。 上面的圖G2包含了"A,B,C,D,E,F,G"共7個頂點，而且包含了"<A,B>,<B,C>,<B,E>,<B,F>,<C,E>,<D,C>,<E,B>,<E,D>,<F,G>"共9條邊。 上圖右邊的矩陣是G2在內存中的鄰接表示意圖。每一個頂點都包含一條鏈表，該鏈表記錄了"該頂點所對應的出邊的另一個頂點的序號"。例如，第1個頂點(頂點B)包含的鏈表所包含的節點的數據分別是"2,4,5"；而這"2,4,5"分別對應"C,E,F"的序號，"C,E,F"都屬於B的出邊的另一個頂點。 鄰接表有向圖的代碼說明 1. 基本定義 復制代碼 #define MAX 100 // 鄰接表 class ListDG { private: // 內部類 // 鄰接表中表對應的鏈表的頂點 class ENode { public: int ivex; // 該邊所指向的頂點的位置 ENode *nextEdge; // 指向下一條弧的指針 }; // 鄰接表中表的頂點 class VNode { public: char data; // 頂點信息 ENode *firstEdge; // 指向第一條依附該頂點的弧 }; private: // 私有成員 int mVexNum; // 圖的頂點的數目 int mEdgNum; // 圖的邊的數目 VNode mVexs[MAX]; public: // 創建鄰接表對應的圖(自己輸入) ListDG(); // 創建鄰接表對應的圖(用已提供的數據) ListDG(char vexs[], int vlen, char edges[][2], int elen); ~ListDG(); // 打印鄰接表圖 void print(); private: // 讀取一個輸入字符 char readChar(); // 返回ch的位置 int getPosition(char ch); // 將node節點鏈接到list的最後 void linkLast(ENode *list, ENode *node); }; 復制代碼 (01) ListDG是鄰接表對應的結構體。 mVexNum是頂點數，mEdgNum是邊數；mVexs則是保存頂點信息的一維數組。 (02) VNode是鄰接表頂點對應的結構體。 data是頂點所包含的數據，而firstEdge是該頂點所包含鏈表的表頭指針。 (03) ENode是鄰接表頂點所包含的鏈表的節點對應的結構體。 ivex是該節點所對應的頂點在vexs中的索引，而nextEdge是指向下一個節點的。 2. 創建矩陣 這裡介紹提供了兩個創建矩陣的方法。一個是用已知數據，另一個則需要用戶手動輸入數據。 2.1 創建圖(用已提供的矩陣) 復制代碼 /* * 創建鄰接表對應的圖(用已提供的數據) */ ListDG::ListDG(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); } } 復制代碼 該函數的作用是創建一個鄰接表有向圖。實際上，該方法創建的有向圖，就是上面的圖G2。該函數的調用方法如下： 復制代碼 char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'}; char edges[][2] = { {'A', 'B'}, {'B', 'C'}, {'B', 'E'}, {'B', 'F'}, {'C', 'E'}, {'D', 'C'}, {'E', 'B'}, {'E', 'D'}, {'F', 'G'}}; int vlen = sizeof(vexs)/sizeof(vexs[0]); int elen = sizeof(edges)/sizeof(edges[0]); ListDG* pG; pG = new ListDG(vexs, vlen, edges, elen); 復制代碼 2.2 創建圖(自己輸入) 復制代碼 /* * 創建鄰接表對應的圖(自己輸入) */ ListDG::ListDG() { 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); } }
