Consider a special kind of graph where the nodes can be partitioned into $n$ layers. There are edges only between successive layers and no edges between the nodes of any given layer. So for example, the nodes in layer-1 are connected only to the nodes in layer-2, the nodes in layer-2 are connected only to the ones in layer-3 and so on. I call such a graph a "neural graph" since neural networks happen to look like this. Also note that such graphs are bi-partite since all nodes can be colored with two colors in a way that no edge has the same color on both ends.
I'm given a set of nodes, each belonging to different layers in the graph. I need to find any path (represented as an array of nodes) that starts at layer 1ドル$, ends at layer $n$ and necessarily goes through all these nodes in the set. If no such path exists, the algorithm should return an empty array. Any ideas for doing this efficiently?
The graph can be represented in any representation, but adjacency list is preferred.
-
$\begingroup$ Is the graph full between any two layers? That is, im asking if for every $v$ in layer 1 there is an edge to any other $u$ in layer 2. $\endgroup$nir shahar– nir shahar2021年06月28日 00:26:06 +00:00Commented Jun 28, 2021 at 0:26
-
$\begingroup$ No, that is not guaranteed. If it helps, what is guaranteed is that there are no "dead end nodes" meaning every node is compatible with at-least some nodes in the next layer (apart from layer $n$ of course). But the question is well-framed even without this requirement. $\endgroup$Rohit Pandey– Rohit Pandey2021年06月28日 00:29:07 +00:00Commented Jun 28, 2021 at 0:29
-
$\begingroup$ Also, there is no node not connected to any nodes in the previous layer (apart from the nodes in layer 1ドル$). $\endgroup$Rohit Pandey– Rohit Pandey2021年06月28日 00:38:38 +00:00Commented Jun 28, 2021 at 0:38
-
$\begingroup$ What do you mean by "goes through all these nodes in the set"? This is the first time you mention any set, so I don't know what set you are referring to. $\endgroup$D.W.– D.W. ♦2021年06月28日 03:13:59 +00:00Commented Jun 28, 2021 at 3:13
-
$\begingroup$ "I'm given a set of nodes, each belonging to different layers in the graph". $\endgroup$Rohit Pandey– Rohit Pandey2021年06月28日 03:15:38 +00:00Commented Jun 28, 2021 at 3:15
1 Answer 1
Use BFS from some arbitrary node $v$ in that set. Then, denote by $u_1,\dots,u_k$ the nodes that you want to go through, and take the path $u_1\rightsquigarrow v\rightsquigarrow u_2 \rightsquigarrow v \rightsquigarrow\dots\rightsquigarrow u_k$.
If you want to start at the first layer and end at the last layer then just append a path from any node on the first layer to $v$ and then to $u_1$, and also append a path from $u_k$ to $v$ to some node on the last layer.
-
$\begingroup$ Why BFS instead of DFS? $\endgroup$Rohit Pandey– Rohit Pandey2021年06月28日 16:41:44 +00:00Commented Jun 28, 2021 at 16:41
-
$\begingroup$ Doesn't really matter. BFS is just easier to think about when talking about paths (and shortest paths) $\endgroup$nir shahar– nir shahar2021年06月28日 17:04:43 +00:00Commented Jun 28, 2021 at 17:04
-
$\begingroup$ Any reason to think one of them will be faster than the other? $\endgroup$Rohit Pandey– Rohit Pandey2021年06月28日 17:50:37 +00:00Commented Jun 28, 2021 at 17:50
-
$\begingroup$ Nope, but BFS is most likely to give a slightly shorter path, not that it matters for this question... $\endgroup$nir shahar– nir shahar2021年06月28日 17:51:56 +00:00Commented Jun 28, 2021 at 17:51
-
$\begingroup$ All paths start at layer 1ドル$ and end at layer $n,ドル so they all have the same length ($n$). $\endgroup$Rohit Pandey– Rohit Pandey2021年06月28日 17:59:16 +00:00Commented Jun 28, 2021 at 17:59