Tarjan's algorithm to determine wheter a directed graph has a cycle
$begingroup$
I want to know if a directed graph has a cycle; something like
1->2->3->2 ...
1->2->3->4->3...
1->1->1->1...
So, I'm considering the Tarjan's strongly connected algorithm.
Do you think that with this algorithm I'll be able to know if some directed graph has a cycle?
Thanks!
graph-theory algorithms computer-science
asked Sep 2 '14 at 20:06
TomiTomi
4151517
$endgroup$
add a comment |
$begingroup$
I want to know if a directed graph has a cycle; something like
1->2->3->2 ...
1->2->3->4->3...
1->1->1->1...
So, I'm considering the Tarjan's strongly connected algorithm.
Do you think that with this algorithm I'll be able to know if some directed graph has a cycle?
Thanks!
graph-theory algorithms computer-science
asked Sep 2 '14 at 20:06
TomiTomi
4151517
$endgroup$
1
$begingroup$
If you just want to detect whether or not it has any cycle, use DFS. If you want to find all cycles, then I think Tarjan's is a good choice. See stackoverflow.com/questions/546655/finding-all-cycles-in-graph
$endgroup$
– A.E
Sep 2 '14 at 20:09
$begingroup$
I want to stop my algorithm when I found the first cycle
$endgroup$
– Tomi
Sep 2 '14 at 20:11
$begingroup$
Tarzan's algorithm. :-)
$endgroup$
– Lucian
Sep 2 '14 at 20:12
add a comment |
$begingroup$
I want to know if a directed graph has a cycle; something like
1->2->3->2 ...
1->2->3->4->3...
1->1->1->1...
So, I'm considering the Tarjan's strongly connected algorithm.
Do you think that with this algorithm I'll be able to know if some directed graph has a cycle?
Thanks!
graph-theory algorithms computer-science
asked Sep 2 '14 at 20:06
TomiTomi
4151517
$endgroup$
I want to know if a directed graph has a cycle; something like
1->2->3->2 ...
1->2->3->4->3...
1->1->1->1...
So, I'm considering the Tarjan's strongly connected algorithm.
Do you think that with this algorithm I'll be able to know if some directed graph has a cycle?
Thanks!
graph-theory algorithms computer-science
graph-theory algorithms computer-science
asked Sep 2 '14 at 20:06
TomiTomi
4151517
asked Sep 2 '14 at 20:06
TomiTomi
4151517
asked Sep 2 '14 at 20:06
TomiTomi
4151517
asked Sep 2 '14 at 20:06
TomiTomi
4151517
asked Sep 2 '14 at 20:06
TomiTomi
4151517
4151517
1
$begingroup$
If you just want to detect whether or not it has any cycle, use DFS. If you want to find all cycles, then I think Tarjan's is a good choice. See stackoverflow.com/questions/546655/finding-all-cycles-in-graph
$endgroup$
– A.E
Sep 2 '14 at 20:09
$begingroup$
I want to stop my algorithm when I found the first cycle
$endgroup$
– Tomi
Sep 2 '14 at 20:11
$begingroup$
Tarzan's algorithm. :-)
$endgroup$
– Lucian
Sep 2 '14 at 20:12
add a comment |
1
$begingroup$
If you just want to detect whether or not it has any cycle, use DFS. If you want to find all cycles, then I think Tarjan's is a good choice. See stackoverflow.com/questions/546655/finding-all-cycles-in-graph
$endgroup$
– A.E
Sep 2 '14 at 20:09
$begingroup$
I want to stop my algorithm when I found the first cycle
$endgroup$
– Tomi
Sep 2 '14 at 20:11
$begingroup$
Tarzan's algorithm. :-)
$endgroup$
– Lucian
Sep 2 '14 at 20:12
1
1
$begingroup$
If you just want to detect whether or not it has any cycle, use DFS. If you want to find all cycles, then I think Tarjan's is a good choice. See stackoverflow.com/questions/546655/finding-all-cycles-in-graph
$endgroup$
– A.E
Sep 2 '14 at 20:09
$begingroup$
If you just want to detect whether or not it has any cycle, use DFS. If you want to find all cycles, then I think Tarjan's is a good choice. See stackoverflow.com/questions/546655/finding-all-cycles-in-graph
$endgroup$
– A.E
Sep 2 '14 at 20:09
$begingroup$
I want to stop my algorithm when I found the first cycle
$endgroup$
– Tomi
Sep 2 '14 at 20:11
$begingroup$
I want to stop my algorithm when I found the first cycle
$endgroup$
– Tomi
Sep 2 '14 at 20:11
$begingroup$
Tarzan's algorithm. :-)
$endgroup$
– Lucian
Sep 2 '14 at 20:12
$begingroup$
Tarzan's algorithm. :-)
$endgroup$
– Lucian
Sep 2 '14 at 20:12
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
A slight modification to Tarjan's algorithm will serve you well. Run it as normal, but modify the DFS routine to return True if a node is visited more than once.
Equivalently, return True as soon as you find a strongly connected component with more than one cycle.
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
$endgroup$
$begingroup$
Consider the directed graph with four vertices $a,b,c,d$ and four edges $(a,b), (a,c), (b,d), (c,d)$. The graph has no cycles, but DFS from $a$ visits $d$ twice.
$endgroup$
– Fabio Somenzi
May 19 '17 at 4:30
add a comment |
$begingroup$
Tarjan's algorithm may be used to detect cycles in a directed graph as follows: When the root node of a (maximal) strongly connected component (SCC) is detected, the nodes in the SCC are popped from the stack. At that point, if more than one node is popped, then it is known that the graph contains a cycle. If the SCC contains a single node, one has to check whether that node has a "self-loop" (which gives a cycle) or not (that is, the node makes up a trivial SCC).
Said otherwise, if the directed graph has no cycles, Tarjan's algorithm will only find SCCs consisting of individual nodes without self-loops.
If the cycle needs to be identified and the SCC found has more than one node, one can perform a depth-first search from the SCC root, limited to the nodes that are in that SCC and until the root of the SCC is re-entered.
In fact, in practice, cycle detection in directed graphs is performed by two nested depth-first searches, without concern for the enumeration of SCCs, especially when cycles have to go through some designated nodes.
When the "outer" DFS is about to retreat from a (designated) node $v$, a second DFS is run from $v$ to see if some node $u$ currently on the stack of the outer DFS may be reached from $v$.
If that is the case, we have a cycle reachable from the node from which the first DFS started. Such a cycle goes through both $v$, the node from which the outer DFS is about to retreat, and $u$, the node on the stack of the outer DFS found during the inner DFS. We know we can reach $v$ from $u$ because $u$ is on the stack of the outer DFS. We know we can reach $u$ from $v$ because the inner DFS says so.
The nested DFS algorithm is not asymptotically faster than Tarjan's algorithm, but often performs better.
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
$endgroup$
add a comment |
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',
autoActivateHeartbeat: false,
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f917414%2ftarjans-algorithm-to-determine-wheter-a-directed-graph-has-a-cycle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
A slight modification to Tarjan's algorithm will serve you well. Run it as normal, but modify the DFS routine to return True if a node is visited more than once.
Equivalently, return True as soon as you find a strongly connected component with more than one cycle.
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
$endgroup$
$begingroup$
Consider the directed graph with four vertices $a,b,c,d$ and four edges $(a,b), (a,c), (b,d), (c,d)$. The graph has no cycles, but DFS from $a$ visits $d$ twice.
$endgroup$
– Fabio Somenzi
May 19 '17 at 4:30
add a comment |
$begingroup$
A slight modification to Tarjan's algorithm will serve you well. Run it as normal, but modify the DFS routine to return True if a node is visited more than once.
Equivalently, return True as soon as you find a strongly connected component with more than one cycle.
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
$endgroup$
$begingroup$
Consider the directed graph with four vertices $a,b,c,d$ and four edges $(a,b), (a,c), (b,d), (c,d)$. The graph has no cycles, but DFS from $a$ visits $d$ twice.
$endgroup$
– Fabio Somenzi
May 19 '17 at 4:30
add a comment |
$begingroup$
A slight modification to Tarjan's algorithm will serve you well. Run it as normal, but modify the DFS routine to return True if a node is visited more than once.
Equivalently, return True as soon as you find a strongly connected component with more than one cycle.
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
$endgroup$
A slight modification to Tarjan's algorithm will serve you well. Run it as normal, but modify the DFS routine to return True if a node is visited more than once.
Equivalently, return True as soon as you find a strongly connected component with more than one cycle.
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
answered Sep 2 '14 at 20:24
A.EA.E
1,6901722
1,6901722
$begingroup$
Consider the directed graph with four vertices $a,b,c,d$ and four edges $(a,b), (a,c), (b,d), (c,d)$. The graph has no cycles, but DFS from $a$ visits $d$ twice.
$endgroup$
– Fabio Somenzi
May 19 '17 at 4:30
add a comment |
$begingroup$
Consider the directed graph with four vertices $a,b,c,d$ and four edges $(a,b), (a,c), (b,d), (c,d)$. The graph has no cycles, but DFS from $a$ visits $d$ twice.
$endgroup$
– Fabio Somenzi
May 19 '17 at 4:30
$begingroup$
Consider the directed graph with four vertices $a,b,c,d$ and four edges $(a,b), (a,c), (b,d), (c,d)$. The graph has no cycles, but DFS from $a$ visits $d$ twice.
$endgroup$
– Fabio Somenzi
May 19 '17 at 4:30
$begingroup$
Consider the directed graph with four vertices $a,b,c,d$ and four edges $(a,b), (a,c), (b,d), (c,d)$. The graph has no cycles, but DFS from $a$ visits $d$ twice.
$endgroup$
– Fabio Somenzi
May 19 '17 at 4:30
add a comment |
$begingroup$
Tarjan's algorithm may be used to detect cycles in a directed graph as follows: When the root node of a (maximal) strongly connected component (SCC) is detected, the nodes in the SCC are popped from the stack. At that point, if more than one node is popped, then it is known that the graph contains a cycle. If the SCC contains a single node, one has to check whether that node has a "self-loop" (which gives a cycle) or not (that is, the node makes up a trivial SCC).
Said otherwise, if the directed graph has no cycles, Tarjan's algorithm will only find SCCs consisting of individual nodes without self-loops.
If the cycle needs to be identified and the SCC found has more than one node, one can perform a depth-first search from the SCC root, limited to the nodes that are in that SCC and until the root of the SCC is re-entered.
In fact, in practice, cycle detection in directed graphs is performed by two nested depth-first searches, without concern for the enumeration of SCCs, especially when cycles have to go through some designated nodes.
When the "outer" DFS is about to retreat from a (designated) node $v$, a second DFS is run from $v$ to see if some node $u$ currently on the stack of the outer DFS may be reached from $v$.
If that is the case, we have a cycle reachable from the node from which the first DFS started. Such a cycle goes through both $v$, the node from which the outer DFS is about to retreat, and $u$, the node on the stack of the outer DFS found during the inner DFS. We know we can reach $v$ from $u$ because $u$ is on the stack of the outer DFS. We know we can reach $u$ from $v$ because the inner DFS says so.
The nested DFS algorithm is not asymptotically faster than Tarjan's algorithm, but often performs better.
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
$endgroup$
add a comment |
$begingroup$
Tarjan's algorithm may be used to detect cycles in a directed graph as follows: When the root node of a (maximal) strongly connected component (SCC) is detected, the nodes in the SCC are popped from the stack. At that point, if more than one node is popped, then it is known that the graph contains a cycle. If the SCC contains a single node, one has to check whether that node has a "self-loop" (which gives a cycle) or not (that is, the node makes up a trivial SCC).
Said otherwise, if the directed graph has no cycles, Tarjan's algorithm will only find SCCs consisting of individual nodes without self-loops.
If the cycle needs to be identified and the SCC found has more than one node, one can perform a depth-first search from the SCC root, limited to the nodes that are in that SCC and until the root of the SCC is re-entered.
In fact, in practice, cycle detection in directed graphs is performed by two nested depth-first searches, without concern for the enumeration of SCCs, especially when cycles have to go through some designated nodes.
When the "outer" DFS is about to retreat from a (designated) node $v$, a second DFS is run from $v$ to see if some node $u$ currently on the stack of the outer DFS may be reached from $v$.
If that is the case, we have a cycle reachable from the node from which the first DFS started. Such a cycle goes through both $v$, the node from which the outer DFS is about to retreat, and $u$, the node on the stack of the outer DFS found during the inner DFS. We know we can reach $v$ from $u$ because $u$ is on the stack of the outer DFS. We know we can reach $u$ from $v$ because the inner DFS says so.
The nested DFS algorithm is not asymptotically faster than Tarjan's algorithm, but often performs better.
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
$endgroup$
add a comment |
$begingroup$
Tarjan's algorithm may be used to detect cycles in a directed graph as follows: When the root node of a (maximal) strongly connected component (SCC) is detected, the nodes in the SCC are popped from the stack. At that point, if more than one node is popped, then it is known that the graph contains a cycle. If the SCC contains a single node, one has to check whether that node has a "self-loop" (which gives a cycle) or not (that is, the node makes up a trivial SCC).
Said otherwise, if the directed graph has no cycles, Tarjan's algorithm will only find SCCs consisting of individual nodes without self-loops.
If the cycle needs to be identified and the SCC found has more than one node, one can perform a depth-first search from the SCC root, limited to the nodes that are in that SCC and until the root of the SCC is re-entered.
In fact, in practice, cycle detection in directed graphs is performed by two nested depth-first searches, without concern for the enumeration of SCCs, especially when cycles have to go through some designated nodes.
When the "outer" DFS is about to retreat from a (designated) node $v$, a second DFS is run from $v$ to see if some node $u$ currently on the stack of the outer DFS may be reached from $v$.
If that is the case, we have a cycle reachable from the node from which the first DFS started. Such a cycle goes through both $v$, the node from which the outer DFS is about to retreat, and $u$, the node on the stack of the outer DFS found during the inner DFS. We know we can reach $v$ from $u$ because $u$ is on the stack of the outer DFS. We know we can reach $u$ from $v$ because the inner DFS says so.
The nested DFS algorithm is not asymptotically faster than Tarjan's algorithm, but often performs better.
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
$endgroup$
Tarjan's algorithm may be used to detect cycles in a directed graph as follows: When the root node of a (maximal) strongly connected component (SCC) is detected, the nodes in the SCC are popped from the stack. At that point, if more than one node is popped, then it is known that the graph contains a cycle. If the SCC contains a single node, one has to check whether that node has a "self-loop" (which gives a cycle) or not (that is, the node makes up a trivial SCC).
Said otherwise, if the directed graph has no cycles, Tarjan's algorithm will only find SCCs consisting of individual nodes without self-loops.
If the cycle needs to be identified and the SCC found has more than one node, one can perform a depth-first search from the SCC root, limited to the nodes that are in that SCC and until the root of the SCC is re-entered.
In fact, in practice, cycle detection in directed graphs is performed by two nested depth-first searches, without concern for the enumeration of SCCs, especially when cycles have to go through some designated nodes.
When the "outer" DFS is about to retreat from a (designated) node $v$, a second DFS is run from $v$ to see if some node $u$ currently on the stack of the outer DFS may be reached from $v$.
If that is the case, we have a cycle reachable from the node from which the first DFS started. Such a cycle goes through both $v$, the node from which the outer DFS is about to retreat, and $u$, the node on the stack of the outer DFS found during the inner DFS. We know we can reach $v$ from $u$ because $u$ is on the stack of the outer DFS. We know we can reach $u$ from $v$ because the inner DFS says so.
The nested DFS algorithm is not asymptotically faster than Tarjan's algorithm, but often performs better.
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
answered Oct 15 '18 at 17:55
Fabio SomenziFabio Somenzi
6,44321321
6,44321321
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f917414%2ftarjans-algorithm-to-determine-wheter-a-directed-graph-has-a-cycle%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
1
$begingroup$
If you just want to detect whether or not it has any cycle, use DFS. If you want to find all cycles, then I think Tarjan's is a good choice. See stackoverflow.com/questions/546655/finding-all-cycles-in-graph
$endgroup$
– A.E
Sep 2 '14 at 20:09
$begingroup$
I want to stop my algorithm when I found the first cycle
$endgroup$
– Tomi
Sep 2 '14 at 20:11
$begingroup$
Tarzan's algorithm. :-)
$endgroup$
– Lucian
Sep 2 '14 at 20:12