資訊專欄INFORMATION COLUMN
摘要：若為有向圖的終點(diǎn)，經(jīng)過下一次，會指向，返回否則，只要所有的深度搜索中包含滿足條件的結(jié)果，就返回。
Problem
Given a directed graph, design an algorithm to find out whether there is a route between two nodes.
ExampleGiven graph:
A----->B----->C
|
|
|
v
->D----->E
for s = B and t = E, return true
for s = D and t = C, return false
若s為有向圖的終點(diǎn)，經(jīng)過下一次dfs，會指向null，返回false；否則，只要s所有neighbors的深度搜索中包含滿足條件的結(jié)果，就返回true。
Solutionpublic class Solution {
public boolean hasRoute(ArrayList graph,
DirectedGraphNode s, DirectedGraphNode t) {
Set visited = new HashSet();
return dfs(s, t, visited);
}
public boolean dfs(DirectedGraphNode s, DirectedGraphNode t, Set visited) {
if (s == null) return false;
if (s == t) return true;
visited.add(s);
for (DirectedGraphNode next: s.neighbors) {
if (visited.contains(next)) continue;
if (dfs(next, t, visited)) return true;
}
return false;
}
}
BFS
public class Solution {
public boolean hasRoute(ArrayList graph, DirectedGraphNode s, DirectedGraphNode t) {
if (s == t) return true;
Deque q = new ArrayDeque<>();
q.offer(s);
Set visited = new HashSet<>();
while (!q.isEmpty()) {
DirectedGraphNode node = q.poll();
visited.add(node);
if (node == t) return true;
for (DirectedGraphNode child : node.neighbors) {
if (!visited.contains(child)) q.offer(child);
}
}
return false;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/65668.html
Problem Minimum Absolute Difference in BSTGiven a binary search tree with non-negative values, find the minimum absolute difference between values of any two nodes. Example Input: 1 3 ...
Problem Given an undirected graph, return true if and only if it is bipartite. Recall that a graph is bipartite if we can split its set of nodes into two independent subsets A and B such that every ed...
Problem In this problem, a tree is an undirected graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one...
摘要：建立結(jié)點(diǎn)，指向可能要對進(jìn)行操作。找到值為和的結(jié)點(diǎn)設(shè)為，的前結(jié)點(diǎn)若和其中之一為，則和其中之一也一定為，返回頭結(jié)點(diǎn)即可。正式建立，，以及對應(yīng)的結(jié)點(diǎn)，，然后先分析和是相鄰結(jié)點(diǎn)的兩種情況是的前結(jié)點(diǎn)，或是的前結(jié)點(diǎn)再分析非相鄰結(jié)點(diǎn)的一般情況。 Problem Given a linked list and two values v1 and v2. Swap the two nodes in th...
摘要：當(dāng)隊(duì)列非空時，拿出最后放入的元素。若減后入度為，則這個結(jié)點(diǎn)遍歷完成，放入結(jié)果數(shù)組和隊(duì)列。遞歸函數(shù)去遍歷的，繼續(xù)在中標(biāo)記，使得所有點(diǎn)只遍歷一次。最深的點(diǎn)最先，根結(jié)點(diǎn)最后，加入結(jié)果數(shù)組的頭部處。 Problem Given an directed graph, a topological order of the graph nodes is defined as follow: For ...
閱讀 3008·2021-11-23 09:51
閱讀 3163·2021-11-15 11:39
閱讀 3061·2021-11-09 09:47
閱讀 2591·2019-08-30 13:49
閱讀 2162·2019-08-30 13:09
閱讀 3161·2019-08-29 16:10
閱讀 3578·2019-08-26 17:04
閱讀 1103·2019-08-26 13:57
