了解鄰接矩陣

在計算機科學中，鄰接矩陣是一種用於存儲圖形數據和它們之間關係的數據結構。它是由一個二元數組組成，其中表示給定節點之間是否存在邊。節點可以表示城市、人、車站等等，邊則表示它們之間的關係。鄰接矩陣是一個方陣，它可以將複雜的圖形表示為簡單的矩陣，這簡化了很多計算。

一、創建鄰接矩陣

鄰接矩陣是用一個數組表示，其中矩陣的每行和每列代表矩陣中每個節點的編號。矩陣中的值代表兩個節點之間是否存在邊。

#include <iostream>
using namespace std;

int main(){
    int vertices;
    cout<>vertices;

    //分配矩陣內存
    int **matrix = new int *[vertices];
    for(int i=0;i<vertices;i++){
        matrix[i] = new int[vertices];
    }

    //初始化矩陣所有元素為0，表示沒有連接
    for(int i=0;i<vertices;i++){
        for(int j=0;j<vertices;j++){
            matrix[i][j]=0;
        }
    }
    return 0;
}

二、從文件中載入鄰接矩陣

鄰接矩陣也可以從文件中讀取，該文件存儲了節點和邊的信息。在以下示例中，我們將從一個文本文件中讀取鄰接矩陣，文件名為input.txt。

#include <iostream>
#include <fstream>
using namespace std;

int main(){
    int vertices;
    ifstream inputfile("input.txt");
    inputfile >> vertices;

    // allocate memory for matrix
    int **matrix = new int *[vertices];
    for (int i = 0; i < vertices; i++){
        matrix[i] = new int[vertices];
    }
    
    // read matrix from file
    for (int i = 0; i < vertices; i++){
        for (int j = 0; j < vertices; j++){
            inputfile >> matrix[i][j];
        }
    }

    inputfile.close();
    return 0;
}

三、使用鄰接矩陣實現圖形演算法

鄰接矩陣是使用圖形演算法的基礎。在以下示例中，我們使用鄰接矩陣來實現最短路徑演算法。它將找到兩個節點之間的最短路徑，如果該路徑存在的話。

#include <iostream>
#include <limits.h>
using namespace std;

#define V 5

int minDistance(int dist[], bool sptSet[]){
    int min = INT_MAX, min_index;
    for (int v = 0; v < V; v++){
        if (sptSet[v] == false && dist[v] <= min){
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

int dijkstra(int graph[V][V], int src, int dest){
    int dist[V];
    bool sptSet[V];
    for (int i = 0; i < V; i++){
        dist[i] = INT_MAX;
        sptSet[i] = false;
    }

    dist[src] = 0;
    for (int count = 0; count < V - 1; count++){
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        for (int v = 0; v < V; v++){
            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]){
                dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    return dist[dest];
}

int main(){
    // declare adjacency matrix
    int graph[V][V] = {{0, 2, 0, 6, 0},
                       {2, 0, 3, 8, 5},
                       {0, 3, 0, 0, 7},
                       {6, 8, 0, 0, 9},
                       {0, 5, 7, 9, 0}};

    int src = 0, dest = 4;
    cout<<"從節點"<<src<<"到節點"<<dest<<"的最短路徑是"<<dijkstra(graph, src, dest)<<endl;
    return 0;
}

四、鄰接矩陣的優點和缺點

鄰接矩陣的優點是易於理解和實現，尤其適用於小型圖形。它也可以輕鬆地確定兩個節點之間的距離或路徑。然而，鄰接矩陣也有一些缺點。其空間和時間複雜度均為O（V ^ 2），當節點數量極大時，它將佔用大量內存並浪費計算時間。

五、結論

鄰接矩陣是一種用於存儲圖形數據和它們之間關係的數據結構。儘管它運作的實際速度較慢且需要更多的內存，但它易於實現，易於理解。在處理小型圖形時，鄰接矩陣是一個很有用的工具。