数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学检查无向图中节点 S 和 T 之间是否存在仅 S 和 T 重复的环路
介绍
图是一种强大的数学结构，允许我们对各种实体之间的关系进行建模和可视化。在计算机科学中，图在各种算法和数据结构中都有应用。无向图的一个常见问题是确定两个给定节点之间是否存在环路。在本文中，我们将着手解决这个难题，并使用 C/C++ 提供一个优雅的解决方案。确定无向图中的环路对于各种连接性很重要的应用至关重要。
无向图是确定两个给定节点之间是否存在环路
无权双向（或无向）图由通过边连接的顶点或节点组成。这些边没有分配任何特定的权重或距离，而是仅指示存在连接，没有任何方向偏差。
路径表示一系列互连的顶点，其中每个顶点都通过边直接与其相邻的对应顶点连接。在这里，我们专注于查找连接两个不同顶点（明确称为源节点和目标节点）的路径，并具有最小的总边遍历次数。
考虑一个无向图，其中每条边表示两个节点之间的连接。我们的目标是确定在这个图中是否存在连接节点 S 和节点 T 的环路，当这两个节点都可以在任何路径中重复出现。
在上图中，它有四个顶点和 3 条边，我们需要检查节点 1 和节点 4 之间是否存在环路。DFS 算法从节点 1（源节点）开始，访问其相邻节点 - 节点 2 和节点 3。然后它访问节点 4，该节点之前已被节点 3 访问过。由于节点 4 不是节点 3 的父节点，因此图中存在环路。
方法 1：C++ 程序，用于检查无向图中节点 S 和 T 之间是否存在仅 S 和 T 重复的环路
为了有效地解决这个问题，我们将采用深度优先搜索 (DFS)，这是一种广泛使用的图遍历算法。DFS 背后的基本思想是尽可能沿着每个分支向下探索，然后再回溯。
算法
步骤 1 − 它使用一个 `Graph` 类来封装图的属性。
步骤 2 − 它包括诸如 `addEdge()`（连接两个顶点）、`hasCycle()`（确定两个节点之间是否存在环路）以及用于 DFS 遍历的内部辅助方法（例如 `dfsUtil()`）之类的函数。
步骤 3 − 在驱动程序代码 (`main()` )中，我们提示用户输入图中的顶点数和边数。
步骤 4 − 然后逐一询问边对（节点连接）。
步骤 5 − 最后，询问源顶点和目标顶点。
步骤 6 − 程序将输出这两个节点之间是否存在可能重复的路径。
示例
#include <iostream>
#include <vector>
using namespace std;
// Graph class representing our underlying structure
class Graph {
int numNodes; // Total number of nodes in the graph
vector<vector<int>> adjList; // Adjacency list representation
public:
// Constructor taking input parameter specifying the total number of nodes
Graph(int n) {
numNodes = n;
adjList.resize(n);
}
// Function allowing adding edges between two vertices u and v (0-based indexing)
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
private:
// Utility function used by hasCycle() to perform DFS search recursively starting from vertex s.
// It returns true if the cycle is found during exploration.
bool dfsUtil(int s, bool visited[], bool parent[]) {
visited[s] = true;
for (int v : adjList[s]) {
if (!visited[v]) {
parent[v] = true;
// Recursive call
if (dfsUtil(v, visited, parent))
return true;
}
else if(parent[v])
return true;
}
return false;
}
public:
// Function that checks whether a cycle exists between nodes S and T.
bool hasCycle(int s, int t) {
bool* visited = new bool[numNodes];
bool* parent = new bool[numNodes];
for(int i=0; i<numNodes; ++i){
visited[i]=false;
parent[i]=false;
}
parent[s] = true;
if(dfsUtil(s, visited, parent)){
delete[] visited;
delete[] parent;
return dfsUtil(t,visited,parent);
}
delete[] visited;
return false;
}
};
int main() {
int numVertices = 4;
int numEdges = 4;
Graph graph(numVertices);
vector<pair<int,int>> edges = {{1,2},{2,3},{3,4},{4,1}};
for(auto edge : edges){
int u = edge.first - 1;
int v = edge.second - 1;
graph.addEdge(u,v);
}
int source = 1 - 1;
int target = 4 - 1;
if(graph.hasCycle(source,target))
cout<<"A cycle exists between node "<< source+1 <<" and node " <<target+1<<".";
else
cout<<"No cycle found between node "<< source+1<<" and node " <<target + 1<<".";
return 0;
}
输出
A cycle exists between node 1 and node 4.
结论
当可以通过在不同路径上重复特定节点来形成环路时，这个问题变得更加有趣。通过利用深度优先搜索 (DFS)，我们已经成功开发出健壮的 C++ 代码，该代码包含用于探索图的解决方案，同时有效地检查连接所选节点 S 和 T 的重复项的环路是否存在。
94 次浏览
