鄰接表無向圖C++實現詳解

數據結構定義

#define MAX 100

class ListUDG {
private:
    // 邊節點
    class ENode {
    public:
        int ivex;       // 目標頂點索引
        ENode* nextEdge; // 下一條邊
    };
    
    // 頂點節點
    class VNode {
    public:
        char data;       // 頂點信息
        ENode* firstEdge; // 第一條邊
    };
    
    int mVexNum;        // 頂點數
    int mEdgNum;        // 邊數
    VNode mVexs[MAX];   // 頂點數組
    
    // 輔助函數
    char readChar();
    int getPosition(char ch);
    void linkLast(ENode* list, ENode* node);
    
public:
    ListUDG();                          // 手動輸入構建
    ListUDG(char vexs[], int vlen,      // 給定數據構建
            char edges[][2], int elen);
    ~ListUDG();
    void print();                       // 打印鄰接表
};

核心操作實現

1. 給定數據構建（構造函數）

ListUDG::ListUDG(char vexs[], int vlen, char edges[][2], int elen) {
    mVexNum = vlen; mEdgNum = elen;
    
    // 初始化頂點
    for(int i=0; i c2
        ENode* node1 = new ENode();
        node1->ivex = p2;
        if(mVexs[p1].firstEdge == NULL) mVexs[p1].firstEdge = node1;
        else linkLast(mVexs[p1].firstEdge, node1);
        
        // c2 -> c1
        ENode* node2 = new ENode();
        node2->ivex = p1;
        if(mVexs[p2].firstEdge == NULL) mVexs[p2].firstEdge = node2;
        else linkLast(mVexs[p2].firstEdge, node2);
    }
}

2. 尾插法輔助函數

void ListUDG::linkLast(ENode* list, ENode* node) {
    ENode* p = list;
    while(p->nextEdge != NULL) p = p->nextEdge;
    p->nextEdge = node;
}

3. 手動輸入構建

ListUDG::ListUDG() {
    cout << "input vertex number: "; cin >> mVexNum;
    cout << "input edge number: ";   cin >> mEdgNum;
    // 合法性檢查...
    
    for(int i=0; i

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 = new ListUDG(vexs, vlen, edges, elen);
pG->print();
// 輸出每頂點鄰接鏈表
delete pG;

頂點數組 mVexs:
[0] 'A' → 2 → 3 → 5 → NULL  (C,D,F)
[1] 'B' → 2 → NULL          (C)
[2] 'C' → 0 → 1 → 3 → NULL  (A,B,D)
[3] 'D' → 0 → 2 → NULL      (A,C)
[4] 'E' → 6 → NULL          (G)
[5] 'F' → 0 → 6 → NULL      (A,G)
[6] 'G' → 4 → 5 → NULL      (E,F)