数据结构
网络
关系数据库管理系统 (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 次浏览
