資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究圖的鄰接矩陣表示法中新增和刪除頂點
在圖的鄰接矩陣表示法中包含一個頂點意味著將矩陣的大小增加一行一列。未使用的行和列表示新新增的頂點與現有頂點之間的連線。此外，刪除一個頂點需要從鄰接矩陣中刪除其對應的行和列，從而相應地更改矩陣的大小。新增頂點包括新增一行一列，其初始值為 0，而刪除頂點包括刪除對應的行和列，從而有效地減小矩陣的大小。
使用的方法
鄰接矩陣
改進的帶權乘積迪傑斯特拉演算法
在改進的帶權乘積迪傑斯特拉演算法中，我們首先將源節點的權重設定為無窮大，並將所有其他節點的權重設定為無窮大。在演算法執行過程中，我們不是用權重之和來更新距離，而是用迄今為止遇到的權重之積來更新它們。在每一步中，我們選擇權重乘積最小的節點，並以相同的方式更新其相鄰節點的權重。此過程持續進行，直到我們到達目標節點。最終，沿此路徑的權重乘積將表示最小的可能值，滿足權重大於或等於 1 的條件。
演算法
新增頂點
透過新增新行和新列來增加矩陣的大小。
將新行和列中的值初始化為 0（或任何其他合適的預設值）。
透過相應地更新新行和列來更新與現有頂點的連線。
刪除頂點
確定要刪除的頂點的行。
從鄰接矩陣中刪除該行和列。
移動剩餘的行和列以填充刪除操作產生的空隙。
如果圖是有向圖，則相應地更新矩陣中剩餘頂點的索引以保持正確的連線。
示例
#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
結論
本文研究了圖的鄰接矩陣表示法中頂點的新增和刪除。它解釋了透過新增新行和列來擴充套件矩陣、初始化其值以及更新與現有頂點的連線來新增頂點的方法。同樣地，它涵蓋了透過刪除其對應的行和列、移動其餘元素以及在有向圖的情況下修改索引來刪除頂點。C 程式說明了這些操作並顯示了更新後的鄰接矩陣。本文提供了對如何使用鄰接矩陣表示法來操作圖的清晰理解。
更新於: 2023-07-13
548 次瀏覽
廣告