了解邻接矩阵

IQCO • 2024-10-14 18:47 • 编程

在计算机科学中，邻接矩阵是一种用于存储图形数据和它们之间关系的数据结构。它是由一个二元数组组成，其中表示给定节点之间是否存在边。节点可以表示城市、人、车站等等，边则表示它们之间的关系。邻接矩阵是一个方阵，它可以将复杂的图形表示为简单的矩阵，这简化了很多计算。

一、创建邻接矩阵

邻接矩阵是用一个数组表示，其中矩阵的每行和每列代表矩阵中每个节点的编号。矩阵中的值代表两个节点之间是否存在边。

#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），当节点数量极大时，它将占用大量内存并浪费计算时间。

五、结论

邻接矩阵是一种用于存储图形数据和它们之间关系的数据结构。尽管它运作的实际速度较慢且需要更多的内存，但它易于实现，易于理解。在处理小型图形时，邻接矩阵是一个很有用的工具。

原创文章，作者：IQCO，如若转载，请注明出处：https://www.506064.com/n/143326.html