資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學圖的鄰接表表示法中新增和刪除邊
鄰接表有效地儲存圖的關係。圖演算法和操作使用它。新增和刪除邊可以動態地更改頂點之間的連線。圖的修改、連線分析和演化需要此過程。新增和刪除邊分別連線和分離頂點。鄰接表表示法通常透過更改頂點的鄰接表來執行這些操作。使用向量、集合或集合對映可以改變實現方式。新的邊在圖中建立路徑和連線。但是，刪除邊會斷開連線，從而改變圖的結構和動態。這些過程對於圖的鄰接表完整性和演化至關重要。
使用的方法
向量向量
向量集合
集合對映
向量向量方法
向量向量技術實現圖的鄰接表表示。外層向量表示頂點，內層向量表示其鄰居。此方法易於儲存圖結構。透過修改向量來更新鄰接表。這種方法可以輕鬆訪問和修改小型圖。
演算法
向量化一個空圖。
將v新增到u的鄰接表以建立邊。
將u新增到v的鄰接表。
從u的鄰接表中刪除v以刪除邊。
示例
#include <iostream>
#include <vector>
#include <algorithm>
// Function to add an edge between two vertices
void addEdge(std::vector<std::vector<int>>& graph, int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
// Function to remove an edge between two vertices
void removeEdge(std::vector<std::vector<int>>& graph, int u, int v) {
graph[u].erase(std::remove(graph[u].begin(), graph[u].end(), v), graph[u].end());
graph[v].erase(std::remove(graph[v].begin(), graph[v].end(), u), graph[v].end());
}
int main() {
int numVertices = 4;
std::vector<std::vector<int>> graph(numVertices);
// Add edges to the graph
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
// Remove edge between vertices 0 and 2
removeEdge(graph, 0, 2);
// Display the updated graph
for (int i = 0; i < graph.size(); ++i) {
std::cout << "Adjacent vertices of vertex " << i << ": ";
for (int j = 0; j < graph[i].size(); ++j) {
std::cout << graph[i][j] << " ";
}
std::cout << std::endl;
}
return 0;
}
輸出
Adjacent vertices of vertex 0: 1 Adjacent vertices of vertex 1: 0 2 Adjacent vertices of vertex 2: 1 3 Adjacent vertices of vertex 3: 2
向量集合方法
向量集合技術使用無序集合來表示圖的鄰接表。無序集合維護每個向量元素的相鄰頂點。此方法允許快速插入、刪除和查詢邊。它可以防止鄰接表重複。此方法對於有效檢查邊是否存在非常方便。
演算法
使用無序集合建立一個空圖。
連線u和v
將v新增到u的無序集合中。
將u新增到v的無序集合中。
刪除u-v邊
從u中刪除v。
從v中刪除u。
示例
#include <iostream>
#include <vector>
#include <unordered_set>
// Function to add an edge between two vertices
void addEdge(std::vector<std::unordered_set<int>>& graph, int u, int v) {
graph[u].insert(v);
graph[v].insert(u);
}
// Function to remove an edge between two vertices
void removeEdge(std::vector<std::unordered_set<int>>& graph, int u, int v) {
graph[u].erase(v);
graph[v].erase(u);
}
int main() {
int numVertices = 4;
std::vector<std::unordered_set<int>> graph(numVertices);
// Add edges to the graph
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
// Remove edge between vertices 0 and 2
removeEdge(graph, 0, 2);
// Display the updated graph
for (int i = 0; i < graph.size(); ++i) {
std::cout << "Adjacent vertices of vertex " << i << ": ";
for (int adjVertex : graph[i]) {
std::cout << adjVertex << " ";
}
std::cout << std::endl;
}
return 0;
}
輸出
Adjacent vertices of vertex 0: 1 Adjacent vertices of vertex 1: 2 0 Adjacent vertices of vertex 2: 3 1 Adjacent vertices of vertex 3: 2
集合對映方法
在集合對映技術中，對映資料結構表示圖的鄰接表。對映的鍵值對錶示頂點及其相鄰的無序集合。此方法簡化了邊的新增和刪除以及頂點的鄰接表。對映可以處理具有非數字頂點 ID 的圖。某些圖演算法受益於按頂點 ID 排序的鄰接表。
演算法
對映無序集合以建立一個空圖。
連線u和v
將v插入u的無序對映集合中。
將u插入對映的無序v集合中。
刪除u-v邊
從對映的無序u集合中刪除v。
從對映的無序v集合中刪除u。
示例
#include <iostream>
#include <map>
#include <unordered_set>
// Function to add an edge between two vertices
void addEdge(std::map<int, std::unordered_set<int>>& graph, int u, int v) {
graph[u].insert(v);
graph[v].insert(u);
}
// Function to remove an edge between two vertices
void removeEdge(std::map<int, std::unordered_set<int>>& graph, int u, int v) {
graph[u].erase(v);
graph[v].erase(u);
}
int main() {
std::map<int, std::unordered_set<int>> graph;
// Add edges to the graph
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
// Remove edge between vertices 0 and 2
removeEdge(graph, 0, 2);
// Display the updated graph
for (const auto& entry : graph) {
int vertex = entry.first;
std::cout << "Adjacent vertices of vertex " << vertex << ": ";
for (int adjVertex : entry.second) {
std::cout << adjVertex << " ";
}
std::cout << std::endl;
}
return 0;
}
輸出
Adjacent vertices of vertex 0: 1 Adjacent vertices of vertex 1: 2 0 Adjacent vertices of vertex 2: 3 1 Adjacent vertices of vertex 3: 2
結論
總之，在鄰接表形式中新增和刪除邊需要更改、分析和擴充套件圖結構。使用向量向量、集合或集合對映會在簡單性、效率和實用性之間進行權衡。這些方法允許您透過新增或刪除鄰接表來更新圖的結構。許多與圖相關的應用程式都需要圖的擴充套件、邊的刪除和圖的演化，而這種靈活性允許這樣做。效能、易於實現以及邊是否存在檢查或排序決定了基於圖的應用程式的技術選擇。為了有效地新增和刪除邊，請使用正確的方法。
859 次瀏覽
