程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 鄰接表有向圖(二)之 C++詳解

鄰接表有向圖(二)之 C++詳解

編輯:C++入門知識

鄰接表有向圖的介紹 鄰接表有向圖是指通過鄰接表表示的有向圖。       上面的圖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);     } }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved