快捷導航

C++數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)鄰接表與鄰接矩陣的相互轉(zhuǎn)換

更新時間：2023年07月28日 14:23:47 作者：小L～～～

這篇文章主要為大家學習介紹了C++如何實現(xiàn)鄰接表與鄰接矩陣的相互轉(zhuǎn)換，文中的示例代碼簡潔易懂，感興趣的小伙伴可以跟隨小編一起學習一下

鄰接表轉(zhuǎn)鄰接矩陣的算法思想：

首先初始化鄰接矩陣。遍歷鄰接表，在依次遍歷頂點vertices[i]的邊鏈表時，修改鄰接矩陣的第i行的元素值。若鏈表邊結(jié)點的值為 j，則置鄰接矩陣的edge[i][j]=1。遍歷完鄰接表時，整個轉(zhuǎn)換過程結(jié)束。此算法對于無向圖有向圖均適用。

鄰接矩陣轉(zhuǎn)鄰接表的算法思想：

首先初始化鄰接表的各個邊表結(jié)點，將邊表結(jié)點的first指針指向NULL。遍歷鄰接矩陣，遍歷到edge[i][j]==1時，將結(jié)點值為j的頂點插入到vertices[i]的邊鏈表中。遍歷完鄰接矩陣，整個轉(zhuǎn)換過程結(jié)束。

圖的鄰接表存儲結(jié)構(gòu)定義如下

const int MaxVertexNum = 100; // 圖中頂點數(shù)目的最大值
typedef struct ArcNode { //邊表結(jié)點
    int adjvex; // 該弧所指向的頂點的位置
    struct ArcNode *next; //指向下一條弧的指針
    // int weight; //網(wǎng)的邊權(quán)值
    // Infotype info;
}ArcNode;
typedef struct VNode { //頂點表結(jié)點
    ArcNode *first; // 指向第一條依附該頂點的弧的指針
}VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices; //鄰接表
    int vexnum, arcnum; //圖的頂點數(shù)和弧數(shù)
}ALGraph; // ALGraph是以鄰接表存儲的圖類型

圖的鄰接矩陣存儲結(jié)構(gòu)定義如下

typedef struct{
    int Edge[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，邊表
    int vexnum, arcnum; //圖的當前頂點數(shù)和弧數(shù)
}MGraph;

鄰接矩陣轉(zhuǎn)化為鄰接表算法實現(xiàn)如下

void matrix_convert_table(ALGraph &G1, MGraph G2) { // 鄰接矩陣轉(zhuǎn)化為鄰接表
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        G1.vertices[i].first = NULL; // 初始化指向第一條依附該頂點的弧的指針
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { // 依次遍歷整個鄰接矩陣
        for(int j = 1; j <= G2.vexnum; j++) {
            if(G2.Edge[i][j] == 1) {
                p = (ArcNode *) malloc (sizeof(ArcNode));
                p -> adjvex = j;
                p -> next = G1.vertices[i].first;
                G1.vertices[i].first = p;
            }
        }
    }
}

鄰接表轉(zhuǎn)化為鄰接矩陣算法實現(xiàn)如下

void table_convert_matrix(MGraph &G1, ALGraph G2) { // 鄰接表轉(zhuǎn)化為鄰接矩陣
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        for(int j = 1; j <= G1.vexnum; j++) {
            G1.Edge[i][j] = 0; // 初始化鄰接矩陣
        }
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { //依次遍歷各頂點表結(jié)點為頭的邊鏈表
        p = G2.vertices[i].first; // 取出頂點 i 的第一條出邊
        while(p) { //遍歷邊鏈表
            G1.Edge[i][p->adjvex] = 1; 
            p = p -> next; // 取出下一條出邊
        }
    }
}

我們依然以下面這個圖為例子，便得到了一個輸入樣例：

6 8
1 2
1 4
4 2
2 5
5 4
3 5
3 6
6 6

完整可執(zhí)行代碼如下

#include<bits/stdc++.h>
using namespace std;
//圖的鄰接表存儲結(jié)構(gòu)定義如下
const int MaxVertexNum = 100; // 圖中頂點數(shù)目的最大值
typedef struct ArcNode { //邊表結(jié)點
    int adjvex; // 該弧所指向的頂點的位置
    struct ArcNode *next; //指向下一條弧的指針
    // int weight; //網(wǎng)的邊權(quán)值
    // Infotype info;
}ArcNode;
typedef struct VNode { //頂點表結(jié)點
    ArcNode *first; // 指向第一條依附該頂點的弧的指針
}VNode, AdjList[MaxVertexNum];
typedef struct {
    AdjList vertices; //鄰接表
    int vexnum, arcnum; //圖的頂點數(shù)和弧數(shù)
}ALGraph; // ALGraph是以鄰接表存儲的圖類型
//圖的鄰接矩陣存儲結(jié)構(gòu)定義如下
typedef struct{
    int Edge[MaxVertexNum][MaxVertexNum]; //鄰接矩陣，邊表
    int vexnum, arcnum; //圖的當前頂點數(shù)和弧數(shù)
}MGraph;
void Create_Graph(ALGraph &AG, MGraph &MG) { //創(chuàng)建一個鄰接表和鄰接矩陣
    scanf("%d%d", &AG.vexnum, &AG.arcnum); //輸入圖的頂點數(shù)和邊數(shù)
    MG.arcnum = AG.arcnum;
    MG.vexnum = AG.vexnum;
    for(int i = 1; i <= MG.vexnum; i++) { // 初始化鄰接矩陣
        for(int j = 1; j <= MG.vexnum; j++) {
            MG.Edge[i][j] = 0;
        }
    }
    for(int i = 1; i <= AG.vexnum; i++) {
        AG.vertices[i].first = NULL; //初始化第一條依附該頂點的弧的指針為空
    }
    ArcNode *p;
    for(int i = 0; i < AG.arcnum; i++) {
        int u, v;
        scanf("%d%d", &u, &v); //u, v表示u有一條邊指向v;
        MG.Edge[u][v] = 1;
        p = (ArcNode *) malloc (sizeof(ArcNode)); // p = new ArcNode;
        p -> adjvex = v;
        p -> next = AG.vertices[u].first; //用頭插法將v插到結(jié)點u的邊表結(jié)點中
        AG.vertices[u].first = p; // 插入后將第一條依附該頂點的弧的指針修改為p
    }
}
void matrix_convert_table(ALGraph &G1, MGraph G2) { // 鄰接矩陣轉(zhuǎn)化為鄰接表
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        G1.vertices[i].first = NULL; // 初始化指向第一條依附該頂點的弧的指針
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { // 依次遍歷整個鄰接矩陣
        for(int j = 1; j <= G2.vexnum; j++) {
            if(G2.Edge[i][j] == 1) {
                p = (ArcNode *) malloc (sizeof(ArcNode));
                p -> adjvex = j;
                p -> next = G1.vertices[i].first;
                G1.vertices[i].first = p;
            }
        }
    }
}
void table_convert_matrix(MGraph &G1, ALGraph G2) { // 鄰接表轉(zhuǎn)化為鄰接矩陣
    G1.arcnum = G2.arcnum;
    G1.vexnum = G2.vexnum;
    for(int i = 1; i <= G1.vexnum; i++) {
        for(int j = 1; j <= G1.vexnum; j++) {
            G1.Edge[i][j] = 0; // 初始化鄰接矩陣
        }
    }
    ArcNode *p;
    for(int i = 1; i <= G2.vexnum; i++) { //依次遍歷各頂點表結(jié)點為頭的邊鏈表
        p = G2.vertices[i].first; // 取出頂點 i 的第一條出邊
        while(p) { //遍歷邊鏈表
            G1.Edge[i][p->adjvex] = 1; 
            p = p -> next; // 取出下一條出邊
        }
    }
}
void print_matrix(MGraph G) { // 打印鄰接矩陣
    for(int i = 1; i <= G.vexnum; i++) {
        for(int j = 1; j <= G.vexnum; j++) {
            cout << G.Edge[i][j] << " ";
        }
        puts("");
    }
}
void print_table(ALGraph G) { // 打印鄰接表
    for(int i = 1; i <= G.vexnum; i++) {
        printf("(%d) ", i);
        ArcNode *p = G.vertices[i].first;
        while(p) {
            printf("-> %d ", p -> adjvex);
            p = p -> next;
        }
        puts("");
    }
}
int main() {
    MGraph MG1, MG2;
    ALGraph AG1, AG2;
    Create_Graph(AG1, MG1);
    cout << endl;
    print_matrix(MG1);
    cout << endl;
    print_table(AG1);
    cout << endl;
    matrix_convert_table(AG2, MG1); // 鄰接矩陣轉(zhuǎn)鄰接表
    print_table(AG2); // 打印轉(zhuǎn)化后的鄰接表
    cout << endl;
    table_convert_matrix(MG2, AG1); // 鄰接表轉(zhuǎn)鄰接矩陣
    print_matrix(MG2); // 打印轉(zhuǎn)化后的鄰接矩陣
    return 0;
}
/*
測試樣例二：
9 14
1 2
1 3
2 5
2 4
5 3
5 4
5 6
6 5
3 8
8 9
9 6
4 7
7 6
7 9
*/

以上就是C++數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)鄰接表與鄰接矩陣的相互轉(zhuǎn)換的詳細內(nèi)容，更多關(guān)于C++鄰接表轉(zhuǎn)鄰接矩陣的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: