Graph Traversal











up vote
0
down vote

favorite












There are three types of nodes in my graph, red, blue, and black. For each red node I want to find a path to one black node (in whatever time). On the way, I cannot pass through another red node. How can I find all red nodes where there is a path to a black node that satisfies the above condition?










share|cite|improve this question




























    up vote
    0
    down vote

    favorite












    There are three types of nodes in my graph, red, blue, and black. For each red node I want to find a path to one black node (in whatever time). On the way, I cannot pass through another red node. How can I find all red nodes where there is a path to a black node that satisfies the above condition?










    share|cite|improve this question


























      up vote
      0
      down vote

      favorite









      up vote
      0
      down vote

      favorite











      There are three types of nodes in my graph, red, blue, and black. For each red node I want to find a path to one black node (in whatever time). On the way, I cannot pass through another red node. How can I find all red nodes where there is a path to a black node that satisfies the above condition?










      share|cite|improve this question















      There are three types of nodes in my graph, red, blue, and black. For each red node I want to find a path to one black node (in whatever time). On the way, I cannot pass through another red node. How can I find all red nodes where there is a path to a black node that satisfies the above condition?







      graph-theory






      share|cite|improve this question















      share|cite|improve this question













      share|cite|improve this question




      share|cite|improve this question








      edited Nov 16 at 4:07

























      asked Nov 16 at 0:53







      user616300





























          1 Answer
          1






          active

          oldest

          votes

















          up vote
          0
          down vote













          Now this depends on how your data structures are represented in some ways, but I would use the following algorithm. (To find all the paths at once)



          Each node should be augmented with a variable which will store an edge to follow backwards to get to a black node.



          Start with the set of black nodes. Make a queue containing all edges connected to them (store the edges as directed edges with the end being the black node).



          Then for each edge in the queue check the start node of the edge. If the start node has been processed already, discard the edge. Otherwise check the color of the start node of the edge. If it is red, store the edge in the red node and add it to the set of processed vertices. If the node is blue store the edge in the node, add the blue node to the set of processed vertices and then add all other edges adjacent to the blue node (except for those connecting to processed vertices) to the queue (with their end node being set to our blue node). The start node of edges in the queue can never be black since we already processed all the black nodes, so if it were we would have discarded the edge at the start of the loop.



          If you want to know if every red node has a path to a black node then also maintain a set of unprocessed nodes. If there remain nodes in this set after the queue of edges to check is empty, these nodes cannot reach a black node without traveling through a red node. Iterate through this set to see if there are any red nodes in the set.



          At the end, we'll end up with a set of processed vertices, and the nodes in this set each store an edge that points you along a path (that doesn't go through red nodes) that ends at a black node.



          If we use hash sets, this should be $O(E)$ I think since each edge is processed at most once. Well $O(V)+O(E)$ for sparse graphs, but for connected graphs $V$ is $O(E)$.



          Edit:



          Proof of correctness. By which I mean a proof of the following fact. A red vertex is in the set of processed vertices at the end of the algorithm if and only if there exists a path from the red vertex to a black vertex passing through only blue vertices.



          Proof: We prove instead the equivalent statement: The set of processed vertices at the end of the algorithm is precisely the set of vertices with a path to a black vertex that doesn't pass through a red vertex.



          First we show inductively that the set of processed vertices is a subset of the set of vertices with such a path. The initial set of processed vertices is the set of black vertices. Trivially these all have a path to a black vertex not passing through a red vertex, so the condition is true to start with. Then at each stage of the loop we consider an edge $(s,e)$ with $e$ already in the set of processed vertices (assume $s$ is unprocessed, since otherwise we discard the edge without changing the set of processed vertices). Hence there is a path from $e$ to a black vertex not passing through a red vertex. Moreover, we never add directed edges with a red target vertex to the queue since we only add edges whose targets are black or blue. Thus $e$ is not red. Hence adding the edge $sto e$ to the path from $e$ to a black vertex that doesn't pass through a red vertex gives a path from $s$ to a black vertex not passing through a red vertex. Thus adding $s$ to the set of processed vertices preserves the property that all vertices in the set of processed vertices have a path to a black vertex not passing through a red vertex.



          Conversely if a vertex $v$ has a path to a black vertex not passing through red vertices, define $d(v)$ to be the length of the shortest such path. We'll prove by induction on $d(v)$ that $v$ is processed at some point in the algorithm. If $d(v)=0$ $v$ is black, and it is processed at the beginning of the algorithm. Otherwise $d(v) > 0$, so let $w$ be the next vertex along the minimal length path from $v$ to a black vertex. Clearly $d(w)=d(v)-1$, so by our induction hypothesis $w$ is processed at some point in the algorithm. Since $w$ is not red when it was processed all of its (previously unprocessed) adjacent edges are added to the queue of edges to be processed. Thus the edge $vto w$ is added to the queue when $w$ is processed, and therefore $v$ will be processed at some point (either when we come to the edge $vto w$ or perhaps before that, but either way $v$ must be processed). Thus the induction holds. This completes the other half of the proof of our assertion. $blacksquare$



          It is also true that by following the edges stored at a vertex you will get a path to a black vertex not passing through a red vertex, but the proof of correctness is similar to the proof above, so I won't repeat myself.






          share|cite|improve this answer























          • @James Yep! Though if you want to iterate through each path for each red vertex, the run time is necessarily $O(VE)$. This algorithm essentially builds a tree that allows you to easily find a path for each vertex in $O(E)$ time.
            – jgon
            Nov 16 at 1:33










          • @James I added a proof of correctness
            – jgon
            Nov 16 at 3:21











          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "69"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          noCode: true, onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });














           

          draft saved


          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000567%2fgraph-traversal%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown
























          1 Answer
          1






          active

          oldest

          votes








          1 Answer
          1






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes








          up vote
          0
          down vote













          Now this depends on how your data structures are represented in some ways, but I would use the following algorithm. (To find all the paths at once)



          Each node should be augmented with a variable which will store an edge to follow backwards to get to a black node.



          Start with the set of black nodes. Make a queue containing all edges connected to them (store the edges as directed edges with the end being the black node).



          Then for each edge in the queue check the start node of the edge. If the start node has been processed already, discard the edge. Otherwise check the color of the start node of the edge. If it is red, store the edge in the red node and add it to the set of processed vertices. If the node is blue store the edge in the node, add the blue node to the set of processed vertices and then add all other edges adjacent to the blue node (except for those connecting to processed vertices) to the queue (with their end node being set to our blue node). The start node of edges in the queue can never be black since we already processed all the black nodes, so if it were we would have discarded the edge at the start of the loop.



          If you want to know if every red node has a path to a black node then also maintain a set of unprocessed nodes. If there remain nodes in this set after the queue of edges to check is empty, these nodes cannot reach a black node without traveling through a red node. Iterate through this set to see if there are any red nodes in the set.



          At the end, we'll end up with a set of processed vertices, and the nodes in this set each store an edge that points you along a path (that doesn't go through red nodes) that ends at a black node.



          If we use hash sets, this should be $O(E)$ I think since each edge is processed at most once. Well $O(V)+O(E)$ for sparse graphs, but for connected graphs $V$ is $O(E)$.



          Edit:



          Proof of correctness. By which I mean a proof of the following fact. A red vertex is in the set of processed vertices at the end of the algorithm if and only if there exists a path from the red vertex to a black vertex passing through only blue vertices.



          Proof: We prove instead the equivalent statement: The set of processed vertices at the end of the algorithm is precisely the set of vertices with a path to a black vertex that doesn't pass through a red vertex.



          First we show inductively that the set of processed vertices is a subset of the set of vertices with such a path. The initial set of processed vertices is the set of black vertices. Trivially these all have a path to a black vertex not passing through a red vertex, so the condition is true to start with. Then at each stage of the loop we consider an edge $(s,e)$ with $e$ already in the set of processed vertices (assume $s$ is unprocessed, since otherwise we discard the edge without changing the set of processed vertices). Hence there is a path from $e$ to a black vertex not passing through a red vertex. Moreover, we never add directed edges with a red target vertex to the queue since we only add edges whose targets are black or blue. Thus $e$ is not red. Hence adding the edge $sto e$ to the path from $e$ to a black vertex that doesn't pass through a red vertex gives a path from $s$ to a black vertex not passing through a red vertex. Thus adding $s$ to the set of processed vertices preserves the property that all vertices in the set of processed vertices have a path to a black vertex not passing through a red vertex.



          Conversely if a vertex $v$ has a path to a black vertex not passing through red vertices, define $d(v)$ to be the length of the shortest such path. We'll prove by induction on $d(v)$ that $v$ is processed at some point in the algorithm. If $d(v)=0$ $v$ is black, and it is processed at the beginning of the algorithm. Otherwise $d(v) > 0$, so let $w$ be the next vertex along the minimal length path from $v$ to a black vertex. Clearly $d(w)=d(v)-1$, so by our induction hypothesis $w$ is processed at some point in the algorithm. Since $w$ is not red when it was processed all of its (previously unprocessed) adjacent edges are added to the queue of edges to be processed. Thus the edge $vto w$ is added to the queue when $w$ is processed, and therefore $v$ will be processed at some point (either when we come to the edge $vto w$ or perhaps before that, but either way $v$ must be processed). Thus the induction holds. This completes the other half of the proof of our assertion. $blacksquare$



          It is also true that by following the edges stored at a vertex you will get a path to a black vertex not passing through a red vertex, but the proof of correctness is similar to the proof above, so I won't repeat myself.






          share|cite|improve this answer























          • @James Yep! Though if you want to iterate through each path for each red vertex, the run time is necessarily $O(VE)$. This algorithm essentially builds a tree that allows you to easily find a path for each vertex in $O(E)$ time.
            – jgon
            Nov 16 at 1:33










          • @James I added a proof of correctness
            – jgon
            Nov 16 at 3:21















          up vote
          0
          down vote













          Now this depends on how your data structures are represented in some ways, but I would use the following algorithm. (To find all the paths at once)



          Each node should be augmented with a variable which will store an edge to follow backwards to get to a black node.



          Start with the set of black nodes. Make a queue containing all edges connected to them (store the edges as directed edges with the end being the black node).



          Then for each edge in the queue check the start node of the edge. If the start node has been processed already, discard the edge. Otherwise check the color of the start node of the edge. If it is red, store the edge in the red node and add it to the set of processed vertices. If the node is blue store the edge in the node, add the blue node to the set of processed vertices and then add all other edges adjacent to the blue node (except for those connecting to processed vertices) to the queue (with their end node being set to our blue node). The start node of edges in the queue can never be black since we already processed all the black nodes, so if it were we would have discarded the edge at the start of the loop.



          If you want to know if every red node has a path to a black node then also maintain a set of unprocessed nodes. If there remain nodes in this set after the queue of edges to check is empty, these nodes cannot reach a black node without traveling through a red node. Iterate through this set to see if there are any red nodes in the set.



          At the end, we'll end up with a set of processed vertices, and the nodes in this set each store an edge that points you along a path (that doesn't go through red nodes) that ends at a black node.



          If we use hash sets, this should be $O(E)$ I think since each edge is processed at most once. Well $O(V)+O(E)$ for sparse graphs, but for connected graphs $V$ is $O(E)$.



          Edit:



          Proof of correctness. By which I mean a proof of the following fact. A red vertex is in the set of processed vertices at the end of the algorithm if and only if there exists a path from the red vertex to a black vertex passing through only blue vertices.



          Proof: We prove instead the equivalent statement: The set of processed vertices at the end of the algorithm is precisely the set of vertices with a path to a black vertex that doesn't pass through a red vertex.



          First we show inductively that the set of processed vertices is a subset of the set of vertices with such a path. The initial set of processed vertices is the set of black vertices. Trivially these all have a path to a black vertex not passing through a red vertex, so the condition is true to start with. Then at each stage of the loop we consider an edge $(s,e)$ with $e$ already in the set of processed vertices (assume $s$ is unprocessed, since otherwise we discard the edge without changing the set of processed vertices). Hence there is a path from $e$ to a black vertex not passing through a red vertex. Moreover, we never add directed edges with a red target vertex to the queue since we only add edges whose targets are black or blue. Thus $e$ is not red. Hence adding the edge $sto e$ to the path from $e$ to a black vertex that doesn't pass through a red vertex gives a path from $s$ to a black vertex not passing through a red vertex. Thus adding $s$ to the set of processed vertices preserves the property that all vertices in the set of processed vertices have a path to a black vertex not passing through a red vertex.



          Conversely if a vertex $v$ has a path to a black vertex not passing through red vertices, define $d(v)$ to be the length of the shortest such path. We'll prove by induction on $d(v)$ that $v$ is processed at some point in the algorithm. If $d(v)=0$ $v$ is black, and it is processed at the beginning of the algorithm. Otherwise $d(v) > 0$, so let $w$ be the next vertex along the minimal length path from $v$ to a black vertex. Clearly $d(w)=d(v)-1$, so by our induction hypothesis $w$ is processed at some point in the algorithm. Since $w$ is not red when it was processed all of its (previously unprocessed) adjacent edges are added to the queue of edges to be processed. Thus the edge $vto w$ is added to the queue when $w$ is processed, and therefore $v$ will be processed at some point (either when we come to the edge $vto w$ or perhaps before that, but either way $v$ must be processed). Thus the induction holds. This completes the other half of the proof of our assertion. $blacksquare$



          It is also true that by following the edges stored at a vertex you will get a path to a black vertex not passing through a red vertex, but the proof of correctness is similar to the proof above, so I won't repeat myself.






          share|cite|improve this answer























          • @James Yep! Though if you want to iterate through each path for each red vertex, the run time is necessarily $O(VE)$. This algorithm essentially builds a tree that allows you to easily find a path for each vertex in $O(E)$ time.
            – jgon
            Nov 16 at 1:33










          • @James I added a proof of correctness
            – jgon
            Nov 16 at 3:21













          up vote
          0
          down vote










          up vote
          0
          down vote









          Now this depends on how your data structures are represented in some ways, but I would use the following algorithm. (To find all the paths at once)



          Each node should be augmented with a variable which will store an edge to follow backwards to get to a black node.



          Start with the set of black nodes. Make a queue containing all edges connected to them (store the edges as directed edges with the end being the black node).



          Then for each edge in the queue check the start node of the edge. If the start node has been processed already, discard the edge. Otherwise check the color of the start node of the edge. If it is red, store the edge in the red node and add it to the set of processed vertices. If the node is blue store the edge in the node, add the blue node to the set of processed vertices and then add all other edges adjacent to the blue node (except for those connecting to processed vertices) to the queue (with their end node being set to our blue node). The start node of edges in the queue can never be black since we already processed all the black nodes, so if it were we would have discarded the edge at the start of the loop.



          If you want to know if every red node has a path to a black node then also maintain a set of unprocessed nodes. If there remain nodes in this set after the queue of edges to check is empty, these nodes cannot reach a black node without traveling through a red node. Iterate through this set to see if there are any red nodes in the set.



          At the end, we'll end up with a set of processed vertices, and the nodes in this set each store an edge that points you along a path (that doesn't go through red nodes) that ends at a black node.



          If we use hash sets, this should be $O(E)$ I think since each edge is processed at most once. Well $O(V)+O(E)$ for sparse graphs, but for connected graphs $V$ is $O(E)$.



          Edit:



          Proof of correctness. By which I mean a proof of the following fact. A red vertex is in the set of processed vertices at the end of the algorithm if and only if there exists a path from the red vertex to a black vertex passing through only blue vertices.



          Proof: We prove instead the equivalent statement: The set of processed vertices at the end of the algorithm is precisely the set of vertices with a path to a black vertex that doesn't pass through a red vertex.



          First we show inductively that the set of processed vertices is a subset of the set of vertices with such a path. The initial set of processed vertices is the set of black vertices. Trivially these all have a path to a black vertex not passing through a red vertex, so the condition is true to start with. Then at each stage of the loop we consider an edge $(s,e)$ with $e$ already in the set of processed vertices (assume $s$ is unprocessed, since otherwise we discard the edge without changing the set of processed vertices). Hence there is a path from $e$ to a black vertex not passing through a red vertex. Moreover, we never add directed edges with a red target vertex to the queue since we only add edges whose targets are black or blue. Thus $e$ is not red. Hence adding the edge $sto e$ to the path from $e$ to a black vertex that doesn't pass through a red vertex gives a path from $s$ to a black vertex not passing through a red vertex. Thus adding $s$ to the set of processed vertices preserves the property that all vertices in the set of processed vertices have a path to a black vertex not passing through a red vertex.



          Conversely if a vertex $v$ has a path to a black vertex not passing through red vertices, define $d(v)$ to be the length of the shortest such path. We'll prove by induction on $d(v)$ that $v$ is processed at some point in the algorithm. If $d(v)=0$ $v$ is black, and it is processed at the beginning of the algorithm. Otherwise $d(v) > 0$, so let $w$ be the next vertex along the minimal length path from $v$ to a black vertex. Clearly $d(w)=d(v)-1$, so by our induction hypothesis $w$ is processed at some point in the algorithm. Since $w$ is not red when it was processed all of its (previously unprocessed) adjacent edges are added to the queue of edges to be processed. Thus the edge $vto w$ is added to the queue when $w$ is processed, and therefore $v$ will be processed at some point (either when we come to the edge $vto w$ or perhaps before that, but either way $v$ must be processed). Thus the induction holds. This completes the other half of the proof of our assertion. $blacksquare$



          It is also true that by following the edges stored at a vertex you will get a path to a black vertex not passing through a red vertex, but the proof of correctness is similar to the proof above, so I won't repeat myself.






          share|cite|improve this answer














          Now this depends on how your data structures are represented in some ways, but I would use the following algorithm. (To find all the paths at once)



          Each node should be augmented with a variable which will store an edge to follow backwards to get to a black node.



          Start with the set of black nodes. Make a queue containing all edges connected to them (store the edges as directed edges with the end being the black node).



          Then for each edge in the queue check the start node of the edge. If the start node has been processed already, discard the edge. Otherwise check the color of the start node of the edge. If it is red, store the edge in the red node and add it to the set of processed vertices. If the node is blue store the edge in the node, add the blue node to the set of processed vertices and then add all other edges adjacent to the blue node (except for those connecting to processed vertices) to the queue (with their end node being set to our blue node). The start node of edges in the queue can never be black since we already processed all the black nodes, so if it were we would have discarded the edge at the start of the loop.



          If you want to know if every red node has a path to a black node then also maintain a set of unprocessed nodes. If there remain nodes in this set after the queue of edges to check is empty, these nodes cannot reach a black node without traveling through a red node. Iterate through this set to see if there are any red nodes in the set.



          At the end, we'll end up with a set of processed vertices, and the nodes in this set each store an edge that points you along a path (that doesn't go through red nodes) that ends at a black node.



          If we use hash sets, this should be $O(E)$ I think since each edge is processed at most once. Well $O(V)+O(E)$ for sparse graphs, but for connected graphs $V$ is $O(E)$.



          Edit:



          Proof of correctness. By which I mean a proof of the following fact. A red vertex is in the set of processed vertices at the end of the algorithm if and only if there exists a path from the red vertex to a black vertex passing through only blue vertices.



          Proof: We prove instead the equivalent statement: The set of processed vertices at the end of the algorithm is precisely the set of vertices with a path to a black vertex that doesn't pass through a red vertex.



          First we show inductively that the set of processed vertices is a subset of the set of vertices with such a path. The initial set of processed vertices is the set of black vertices. Trivially these all have a path to a black vertex not passing through a red vertex, so the condition is true to start with. Then at each stage of the loop we consider an edge $(s,e)$ with $e$ already in the set of processed vertices (assume $s$ is unprocessed, since otherwise we discard the edge without changing the set of processed vertices). Hence there is a path from $e$ to a black vertex not passing through a red vertex. Moreover, we never add directed edges with a red target vertex to the queue since we only add edges whose targets are black or blue. Thus $e$ is not red. Hence adding the edge $sto e$ to the path from $e$ to a black vertex that doesn't pass through a red vertex gives a path from $s$ to a black vertex not passing through a red vertex. Thus adding $s$ to the set of processed vertices preserves the property that all vertices in the set of processed vertices have a path to a black vertex not passing through a red vertex.



          Conversely if a vertex $v$ has a path to a black vertex not passing through red vertices, define $d(v)$ to be the length of the shortest such path. We'll prove by induction on $d(v)$ that $v$ is processed at some point in the algorithm. If $d(v)=0$ $v$ is black, and it is processed at the beginning of the algorithm. Otherwise $d(v) > 0$, so let $w$ be the next vertex along the minimal length path from $v$ to a black vertex. Clearly $d(w)=d(v)-1$, so by our induction hypothesis $w$ is processed at some point in the algorithm. Since $w$ is not red when it was processed all of its (previously unprocessed) adjacent edges are added to the queue of edges to be processed. Thus the edge $vto w$ is added to the queue when $w$ is processed, and therefore $v$ will be processed at some point (either when we come to the edge $vto w$ or perhaps before that, but either way $v$ must be processed). Thus the induction holds. This completes the other half of the proof of our assertion. $blacksquare$



          It is also true that by following the edges stored at a vertex you will get a path to a black vertex not passing through a red vertex, but the proof of correctness is similar to the proof above, so I won't repeat myself.







          share|cite|improve this answer














          share|cite|improve this answer



          share|cite|improve this answer








          edited Nov 16 at 3:25

























          answered Nov 16 at 1:17









          jgon

          9,82611638




          9,82611638












          • @James Yep! Though if you want to iterate through each path for each red vertex, the run time is necessarily $O(VE)$. This algorithm essentially builds a tree that allows you to easily find a path for each vertex in $O(E)$ time.
            – jgon
            Nov 16 at 1:33










          • @James I added a proof of correctness
            – jgon
            Nov 16 at 3:21


















          • @James Yep! Though if you want to iterate through each path for each red vertex, the run time is necessarily $O(VE)$. This algorithm essentially builds a tree that allows you to easily find a path for each vertex in $O(E)$ time.
            – jgon
            Nov 16 at 1:33










          • @James I added a proof of correctness
            – jgon
            Nov 16 at 3:21
















          @James Yep! Though if you want to iterate through each path for each red vertex, the run time is necessarily $O(VE)$. This algorithm essentially builds a tree that allows you to easily find a path for each vertex in $O(E)$ time.
          – jgon
          Nov 16 at 1:33




          @James Yep! Though if you want to iterate through each path for each red vertex, the run time is necessarily $O(VE)$. This algorithm essentially builds a tree that allows you to easily find a path for each vertex in $O(E)$ time.
          – jgon
          Nov 16 at 1:33












          @James I added a proof of correctness
          – jgon
          Nov 16 at 3:21




          @James I added a proof of correctness
          – jgon
          Nov 16 at 3:21


















           

          draft saved


          draft discarded



















































           


          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3000567%2fgraph-traversal%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          Probability when a professor distributes a quiz and homework assignment to a class of n students.

          Aardman Animations

          Are they similar matrix