-
Notifications
You must be signed in to change notification settings - Fork 0
/
hasPathProblem.txt
55 lines (50 loc) · 937 Bytes
/
hasPathProblem.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
has path
Write a function, hasPath, that takes in an object representing the adjacency list of a directed acyclic graph and two nodes (src, dst). The function should return a boolean indicating whether or not there exists a directed path between the source and destination nodes.
test_00:
const graph = {
f: ['g', 'i'],
g: ['h'],
h: [],
i: ['g', 'k'],
j: ['i'],
k: []
};
hasPath(graph, 'f', 'k'); // true
test_01:
const graph = {
f: ['g', 'i'],
g: ['h'],
h: [],
i: ['g', 'k'],
j: ['i'],
k: []
};
hasPath(graph, 'f', 'j'); // false
test_02:
const graph = {
f: ['g', 'i'],
g: ['h'],
h: [],
i: ['g', 'k'],
j: ['i'],
k: []
};
hasPath(graph, 'i', 'h'); // true
test_03:
const graph = {
v: ['x', 'w'],
w: [],
x: [],
y: ['z'],
z: [],
};
hasPath(graph, 'v', 'w'); // true
test_04:
const graph = {
v: ['x', 'w'],
w: [],
x: [],
y: ['z'],
z: [],
};
hasPath(graph, 'v', 'z'); // false