图的邻接矩阵表示法中添加和删除顶点

在图的邻接矩阵表示法中包含一个顶点意味着将矩阵的大小增加一行一列。未使用的行和列表示新添加的顶点与现有顶点之间的连接。此外，删除一个顶点需要从邻接矩阵中删除其对应的行和列，从而相应地更改矩阵的大小。添加顶点包括添加一行一列，其初始值为 0，而删除顶点包括删除对应的行和列，从而有效地减小矩阵的大小。

使用的方法

  • 邻接矩阵

改进的带权乘积迪杰斯特拉算法

在改进的带权乘积迪杰斯特拉算法中，我们首先将源节点的权重设置为无穷大，并将所有其他节点的权重设置为无穷大。在算法执行过程中，我们不是用权重之和来更新距离，而是用迄今为止遇到的权重之积来更新它们。在每一步中，我们选择权重乘积最小的节点，并以相同的方式更新其相邻节点的权重。此过程持续进行，直到我们到达目标节点。最终，沿此路径的权重乘积将表示最小的可能值，满足权重大于或等于 1 的条件。

算法

添加顶点

  • 通过添加新行和新列来增加矩阵的大小。

  • 将新行和列中的值初始化为 0（或任何其他合适的默认值）。

  • 通过相应地更新新行和列来更新与现有顶点的连接。

删除顶点

  • 确定要删除的顶点的行。

  • 从邻接矩阵中删除该行和列。

  • 移动剩余的行和列以填充删除操作产生的空隙。

  • 如果图是有向图，则相应地更新矩阵中剩余顶点的索引以保持正确的连接。

示例

Open Compiler
#include <iostream>
using namespace std;

class Graph {
private:
    bool** adjMatrix;
    int numVertices;

public:
    // Initialize the matrix to zero
    Graph(int numVertices) {
        this->numVertices = numVertices;
        adjMatrix = new bool* [numVertices];
        for (int i = 0; i < numVertices; i++) {
            adjMatrix[i] = new bool[numVertices];
            for (int j = 0; j < numVertices; j++)
                adjMatrix[i][j] = false;
        }
    }

    // Add an edge
    void addEdge(int src, int dest) {
        adjMatrix[src][dest] = true;
        adjMatrix[dest][src] = true;
    }

    // Remove an edge
    void removeEdge(int src, int dest) {
        adjMatrix[src][dest] = false;
        adjMatrix[dest][src] = false;
    }

    // Print the adjacency matrix
    void printAdjMatrix() {
        for (int i = 0; i < numVertices; i++) {
            cout << i << " : ";
            for (int j = 0; j < numVertices; j++)
                cout << adjMatrix[i][j] << " ";
            cout << "\n";
        }
    }

    ~Graph() {
        for (int i = 0; i < numVertices; i++)
            delete[] adjMatrix[i];
        delete[] adjMatrix;
    }
};

int main() {
    Graph graph(4);

    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 0);
    graph.addEdge(2, 3);

    graph.printAdjMatrix();

    return 0;
}

输出

0 : 0 1 1 0 
1 : 1 0 1 0 
2 : 1 1 0 1 
3 : 0 0 1 0

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

本文研究了图的邻接矩阵表示法中顶点的添加和删除。它解释了通过添加新行和列来扩展矩阵、初始化其值以及更新与现有顶点的连接来添加顶点的方法。同样地，它涵盖了通过删除其对应的行和列、移动其余元素以及在有向图的情况下修改索引来删除顶点。C 程序说明了这些操作并显示了更新后的邻接矩阵。本文提供了对如何使用邻接矩阵表示法来操作图的清晰理解。

更新于: 2023-07-13

548 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告