C++圖論演算法——圖的儲存方式

使用二維數組鄰接矩陣儲存圖

無向圖：

圖G

定義圖G[101][101]，G[i][j]的值表示從結點vi到vj是否有邊或弧，若有，取值為1或權值，若無，則取值為0或∞。以下是圖G用鄰接矩陣表示的列表：

 

結點 A B C D
A 0 1 1 1
B 1 0 0 1
C 1 0 0 1
D 1 1 1 0

有向圖：

圖G（無權值）圖G（有權值）

定義圖G[101][101]，G[i][j]的值表示從結點vi到vj是否有邊或弧，若有，取值為1或權值，若無，則取值為0或∞。以下是圖G用鄰接矩陣表示的列表：

結點 A B C D
A ∞ 1 1 ∞
B ∞ ∞ ∞ ∞
C ∞ ∞ ∞ 1
D ∞ 1 ∞ ∞
結點 A B C D
A ∞ 10 3 ∞
B ∞ ∞ ∞ ∞
C ∞ ∞ ∞ 6
D ∞ 5 ∞ ∞ 
#include <iostream>
#include <cstring>
using namespace std;

double G[101][101];
int main(){
    int u,v,t,n,m;                        // 結點u到結點v的節點值為t
    cin >> n;
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            G[i][j] = 0x7fffffff;        // 初始化為無窮大 
        }
    }
    // 或者使用memset(G,0x7fffffff,sizeof(G))來初始化
    /*
    若是int類型數組，則採用memset(G,0x7f,sizeof(G)))
    0x7fffffff表示無窮大,若是無向圖，那麼要寫成memset(G,0,sizeof(G))
    也可以定義成memset(G,oxaf,sizeof(G)),全都定義成很小的數。 
    */
    cin >> m;
    for (int i = 1;i <= m;i++){
        cin >> u >> v >> t;
        G[u][v] = t;G[v][u] = t;        // 鄰接矩陣的值 
    }
    // 輸出
    for (int i = 1;i <= n;i++){
        for (int j = 1;j <= n;j++){
            cout << G[i][j] << " ";
        }
        cout << endl;
    } 
    return 0;
}

這是定義鄰接矩陣的程式碼，大家可以根據需要查看注釋修改程式碼。

Tags:

VirMach 便宜 VPS