Fdtxjr

Why is implicit conversion not ambiguous for non-primitive types?

Would this string work as string?

New Order #2: Turn My Way

Writing in a Christian voice

What is the period/term used describe Giuseppe Arcimboldo's style of painting?

Friend wants my recommendation but I don't want to give it to him

Has the laser at Magurele, Romania reached a tenth of the Sun's power?

Not hide and seek

Rendered textures different to 3D View

Is this saw blade faulty?

How can I, as DM, avoid the Conga Line of Death occurring when implementing some form of flanking rule?

"Marked down as someone wanting to sell shares." What does that mean?

Capacitor electron flow

What should be the ideal length of sentences in a blog post for ease of reading?

How would a solely written language work mechanically

Offset in split text content

How to preserve electronics (computers, ipads, phones) for hundreds of years?

Strange behavior in TikZ draw command

Why is participating in the European Parliamentary elections used as a threat?

Started in 1987 vs. Starting in 1987

PTIJ: Which Dr. Seuss books should one obtain?

Why is indicated airspeed rather than ground speed used during the takeoff roll?

Exposing a company lying about themselves in a tightly knit industry (videogames) : Is my career at risk on the long run?

How can a new country break out from a developed country without war?

How to apply DFS on a disconnected graph.

Singly Connected GraphsDepth first search on graphAlgorithm for finding the longest path in a undirected weighted tree (positive weights)Graph theory name for minimum depth to leaf node.How to use BFS or DFS to determine the connectivity in a non-connected graph?Find all “critical nodes” in a graphHow to create a dense graph, when each node has a limited number of edges?Coloring problem on directed graphHow to implement an algorithm for specific kinds of search in a graphimplement of DFS algorithm

0

$begingroup$

I was wondering how to go about solving a problem with disconnected graphs and depth-first search. Here is an example of a disconnected graph.

How would I go through it in DFS?

My current reasoning is by going down the left most subtree, as you would with a BST, so assuming that the node 5 is the start, the path would be: [5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18].

graph-theory searching

share|cite|improve this question

asked Mar 13 at 17:51

taway0282taway0282

1

New contributor

taway0282 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax.
  $endgroup$
  – dantopa
  Mar 13 at 18:40
  

  
  
  
  

add a comment | 

0

$begingroup$

I was wondering how to go about solving a problem with disconnected graphs and depth-first search. Here is an example of a disconnected graph.

How would I go through it in DFS?

My current reasoning is by going down the left most subtree, as you would with a BST, so assuming that the node 5 is the start, the path would be: [5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18].

graph-theory searching

share|cite|improve this question

asked Mar 13 at 17:51

taway0282taway0282

1

New contributor

taway0282 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Welcome to Mathematics Stack Exchange! A quick tour will enhance your experience. Here are helpful tips to write a good question and write a good answer. For equations, please use MathJax.
  $endgroup$
  – dantopa
  Mar 13 at 18:40
  

  
  
  
  

add a comment | 

$begingroup$

I was wondering how to go about solving a problem with disconnected graphs and depth-first search. Here is an example of a disconnected graph.

How would I go through it in DFS?

My current reasoning is by going down the left most subtree, as you would with a BST, so assuming that the node 5 is the start, the path would be: [5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18].

graph-theory searching

share|cite|improve this question

asked Mar 13 at 17:51

taway0282taway0282

1

New contributor

taway0282 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this question

asked Mar 13 at 17:51

taway0282taway0282

1

New contributor

taway0282 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

share|cite|improve this question

asked Mar 13 at 17:51

taway0282taway0282

1

New contributor

taway0282 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked Mar 13 at 17:51

taway0282taway0282

1

New contributor

taway0282 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

asked Mar 13 at 17:51

taway0282taway0282

1

3 Answers
3

active

oldest

votes

0

$begingroup$

This link should answer your question. In fact, DFS is often used to determine whether or not a graph is disconnected or not - if we run DFS and do not reach all of the nodes in the graph, the graph must be disconnected. Hope that helps!

share|cite|improve this answer

answered Mar 13 at 19:43

JRyanJRyan

31816

$endgroup$

add a comment | 

0

$begingroup$

DFS can be used to solve the connectivity problem. You continue to run it on different components until the entire graph is "discovered". Under any case, it does not take longer than $V+E$.

if none of the edges are connected, then you will simply run DFS on every vertice until you discover your graph is disconnected.

share|cite|improve this answer

answered Mar 15 at 21:23

loxlox

212

New contributor

lox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

0

$begingroup$

Normally, running DFS (by taking the left-most node first) would stop after visiting node 6. The visiting order that you describe

[5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

would happen if the two trees where connected through a root. Imagine a new node (let's call it 3) which is the parent of 5 and 17. Now re-run DFS. You would get

[3, 5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

If you use DFS for traversal reasons, say because you want to make some transformation to each node of the graph, since node 3 is a superficial one that you added, you have to handle that node exceptionally. However, usually, nodes of a graph are given as a list or as integers (which are the indexes in $v_i$). Then you can visit (and apply any transformations on) all nodes just by traversing that list or by using the integers successively to refer to all of your nodes.

If you use DFS for path-finding reasons, then it makes no sense to try to connect the two components. The results will be wrong.

share|cite|improve this answer

edited Mar 15 at 22:41

answered Mar 15 at 22:35

frabalafrabala

2,3241122

$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
);



);

taway0282 is a new contributor. Be nice, and check out our Code of Conduct.

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3146925%2fhow-to-apply-dfs-on-a-disconnected-graph%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

This link should answer your question. In fact, DFS is often used to determine whether or not a graph is disconnected or not - if we run DFS and do not reach all of the nodes in the graph, the graph must be disconnected. Hope that helps!

share|cite|improve this answer

answered Mar 13 at 19:43

JRyanJRyan

31816

$endgroup$

add a comment | 

0

$begingroup$

This link should answer your question. In fact, DFS is often used to determine whether or not a graph is disconnected or not - if we run DFS and do not reach all of the nodes in the graph, the graph must be disconnected. Hope that helps!

share|cite|improve this answer

answered Mar 13 at 19:43

JRyanJRyan

31816

$endgroup$

add a comment | 

$begingroup$

This link should answer your question. In fact, DFS is often used to determine whether or not a graph is disconnected or not - if we run DFS and do not reach all of the nodes in the graph, the graph must be disconnected. Hope that helps!

share|cite|improve this answer

answered Mar 13 at 19:43

JRyanJRyan

31816

$endgroup$

share|cite|improve this answer

answered Mar 13 at 19:43

JRyanJRyan

31816

answered Mar 13 at 19:43

JRyanJRyan

31816

answered Mar 13 at 19:43

JRyanJRyan

31816

0

$begingroup$

DFS can be used to solve the connectivity problem. You continue to run it on different components until the entire graph is "discovered". Under any case, it does not take longer than $V+E$.

if none of the edges are connected, then you will simply run DFS on every vertice until you discover your graph is disconnected.

share|cite|improve this answer

answered Mar 15 at 21:23

loxlox

212

New contributor

lox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

0

$begingroup$

DFS can be used to solve the connectivity problem. You continue to run it on different components until the entire graph is "discovered". Under any case, it does not take longer than $V+E$.

if none of the edges are connected, then you will simply run DFS on every vertice until you discover your graph is disconnected.

share|cite|improve this answer

answered Mar 15 at 21:23

loxlox

212

New contributor

lox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

add a comment | 

$begingroup$

DFS can be used to solve the connectivity problem. You continue to run it on different components until the entire graph is "discovered". Under any case, it does not take longer than $V+E$.

if none of the edges are connected, then you will simply run DFS on every vertice until you discover your graph is disconnected.

share|cite|improve this answer

answered Mar 15 at 21:23

loxlox

212

New contributor

lox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

$endgroup$

share|cite|improve this answer

answered Mar 15 at 21:23

loxlox

212

New contributor

lox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered Mar 15 at 21:23

loxlox

212

New contributor

lox is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.

answered Mar 15 at 21:23

loxlox

212

0

$begingroup$

Normally, running DFS (by taking the left-most node first) would stop after visiting node 6. The visiting order that you describe

[5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

would happen if the two trees where connected through a root. Imagine a new node (let's call it 3) which is the parent of 5 and 17. Now re-run DFS. You would get

[3, 5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

If you use DFS for traversal reasons, say because you want to make some transformation to each node of the graph, since node 3 is a superficial one that you added, you have to handle that node exceptionally. However, usually, nodes of a graph are given as a list or as integers (which are the indexes in $v_i$). Then you can visit (and apply any transformations on) all nodes just by traversing that list or by using the integers successively to refer to all of your nodes.

If you use DFS for path-finding reasons, then it makes no sense to try to connect the two components. The results will be wrong.

share|cite|improve this answer

edited Mar 15 at 22:41

answered Mar 15 at 22:35

frabalafrabala

2,3241122

$endgroup$

add a comment | 

0

$begingroup$

Normally, running DFS (by taking the left-most node first) would stop after visiting node 6. The visiting order that you describe

[5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

would happen if the two trees where connected through a root. Imagine a new node (let's call it 3) which is the parent of 5 and 17. Now re-run DFS. You would get

[3, 5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

If you use DFS for traversal reasons, say because you want to make some transformation to each node of the graph, since node 3 is a superficial one that you added, you have to handle that node exceptionally. However, usually, nodes of a graph are given as a list or as integers (which are the indexes in $v_i$). Then you can visit (and apply any transformations on) all nodes just by traversing that list or by using the integers successively to refer to all of your nodes.

If you use DFS for path-finding reasons, then it makes no sense to try to connect the two components. The results will be wrong.

share|cite|improve this answer

edited Mar 15 at 22:41

answered Mar 15 at 22:35

frabalafrabala

2,3241122

$endgroup$

add a comment | 

$begingroup$

Normally, running DFS (by taking the left-most node first) would stop after visiting node 6. The visiting order that you describe

[5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

would happen if the two trees where connected through a root. Imagine a new node (let's call it 3) which is the parent of 5 and 17. Now re-run DFS. You would get

[3, 5, 1, 4, 13, 2, 6, 17, 9, 11, 12, 10, 18]

If you use DFS for traversal reasons, say because you want to make some transformation to each node of the graph, since node 3 is a superficial one that you added, you have to handle that node exceptionally. However, usually, nodes of a graph are given as a list or as integers (which are the indexes in $v_i$). Then you can visit (and apply any transformations on) all nodes just by traversing that list or by using the integers successively to refer to all of your nodes.

If you use DFS for path-finding reasons, then it makes no sense to try to connect the two components. The results will be wrong.

share|cite|improve this answer

edited Mar 15 at 22:41

answered Mar 15 at 22:35

frabalafrabala

2,3241122

$endgroup$

share|cite|improve this answer

edited Mar 15 at 22:41

answered Mar 15 at 22:35

frabalafrabala

2,3241122

answered Mar 15 at 22:35

frabalafrabala

2,3241122

answered Mar 15 at 22:35

frabalafrabala

2,3241122