The Find if Path Exists in Graph problem involves determining whether there is a path between two given nodes (source and destination) in an undirected graph. The graph is represented by n nodes and a list of edges, where each edge specifies a connection between two nodes.
Given:
n: Number of nodes in the graph.
edges: List of edges where each edge is represented as [u, v], indicating an undirected edge between node u and node v.
source: The starting node for the path.
destination: The target node to reach.
Objective:
You need to implement a solution that can determine if there exists a path from the source node to the destination node in the given graph.
Output:
Return True if there exists a path from source to destination, otherwise return False.
解题：
方法一（depth first search）：
-
重构给出的图结构
题目给出的是一对对二维数组（向量表）edges，用来表示图中所有的边。
重构：从已有的二维数组中构建一个邻接表，这会让之后遍历每一个节点和它的相邻节点变得高效。 -
DFS函数的逻辑：
1.）我们需要一个集合visited来存储每次循环访问过的节点，每次只要是访问过的节点，都把它放到visite集合中。
2.) 构建一个递归函数，从source节点开始，首先判断这个source是不是就是要找的destination，如果是则返回true，否则找到和source相连接的所有邻节点，选择其中一个并判断：这个节点有没有被遍历过（是否在visited中能找到），如果没有，则选中它作为递归的起点，把它作为新的source递归调用这个函数，重复以上的操作。
3.）通过递归可以充分遍历完图中的所有节点，如果最终没有找到预先给定的destination，则表示不存在从source到destination的路径，返回false。
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
unordered_map<int, vector<int>> graph;
for (const auto &edge: edges) {
int u = edge[0];
int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
unordered_set<int> visited;
return dfs(source, destination, graph, visited);
}
bool dfs(int node, int destination, unordered_map<int, vector<int>> &graph, unordered_set<int> &visited) {
if (node == destination) {
return true;
}
visited.insert(node);
for (int neighbor: graph[node]) {
if (visited.find(neighbor) == visited.end()) {
if (dfs(neighbor, destination, graph, visited)) {
return true;
}
}
}
return false;
}
};
方法二（breadth-first search）
- 首先也是和方法一一样重构图结构。
- BFS函数逻辑：
1.）同样需要建立一个集合visited用来存储访问过的节点，以保证遍历的过程中循环的有界性以及避免重复访问同一个节点。
2.）这次用一个while循环替代递归，对于while，需要创造一个结束的边界条件：使用queue容器并判断queue容器是否为空，为空则停止循环。具体操作：把关注的那个节点（没有被访问过的）放入队列queue中，进入循环while判断，把这个节点pop出去，并把这个节点存储到visted集合内。找到和当前节点相邻的同时未被访问过的一个新节点，把它作为新关注的节点并放到队列中，进入下一轮while循环，确定这个节点是否等于destination，如果等于则结束循环，否则找一个与该节点相邻的下一个邻接点重复循环，如果最后queue在进行while判断时为空，那么循环终止，表示遍历完所有节点，没有找到从source到destination的路径。
class Solution {
public:
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
unordered_map<int, vector<int>> graph;
for (const auto &edge: edges) {
int u = edge[0];
int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
queue<int> queue;
unordered_set<int> visited;
queue.push(source);
visited.insert(source);
while (!queue.empty()) {
int node = queue.front();
queue.pop();
if (node == destination) {
return true;
}
for (int neighbor: graph[node]) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
queue.push(neighbor);
}
}
}
return false;
}
};