Styjun

How can I get people to remember my character's gender?

SafeCracker #3 - We've Been Blocked

I need a disease

Can there be a single technologically advanced nation, in a continent full of non-technologically advanced nations?

Where can I go to avoid planes overhead?

Should I dumb down my writing in a foreign country?

Is there an idiom that support the idea that "inflation is bad"?

Why does this derived table improve performance?

Are Finitely generated modules over a ring also finitely generated over a subring containing the identity?

List of newcommands used

Shutter speed -vs- effective image stabilisation

How do inspiraling black holes get closer?

How to increase the size of the cursor in Lubuntu 19.04?

What was Bran's plan to kill the Night King?

Does a picture or painting work with Wild Shape?

PWM 1Hz on solid state relay

Why did the Apollo 13 crew extend the LM landing gear?

When two pilots are required for a private aircraft, is it a requirement for the PIC to be ATPL?

How do LIGO and VIRGO know that a gravitational wave has its origin in a neutron star or a black hole?

Will 700 more planes a day fly because of the Heathrow expansion?

What are the differences between credential stuffing and password spraying?

Should I decline this job offer that requires relocating to an area with high cost of living?

Where in Bitcoin Core does it do X?

US born but as a child of foreign diplomat

How to find a path from one vertex to another in a tree using breadth first search?

How do I call one constructor from another in Java?How does a Breadth-First Search work when looking for Shortest Path?Java- Maze Breadth First Search Shortest PathSpanning tree out of graph using Breadth First Search?How to find the shortest path in a maze using breadth first search?Breadth First Search not finding correct pathBreadth-first algorithm on adjacency matrix: premature ending of search, returns queue of size 1?Shortest path using breadth first search in clojureShortest Path - Breadth first searchA* or Bidirectional Breadth First Search?

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;

1

I am trying to implement a BFS that returns a path from a to b in form of a list of vertices. I am implementing this BFS on a tree so I know it will be the shortest path if I can find one. However, so far my research has only led me to find BSF algorithms that search and find nodes, rather than return a path.

The input that I am dealing with is an adjacency matrix of the Minimum Spanning Tree. I must take this and find path from one point to the other.

java breadth-first-search

share|improve this question

edited Mar 23 at 0:25

Jac Frall

asked Mar 22 at 23:48

Jac FrallJac Frall

1917

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  More details? Please? This feels a little like you haven't put too much effort. But the basic idea is just store a list of all nodes visited in the BSF search, and then that is the path.
  
  – mackycheese21
  Mar 22 at 23:52
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @mackycheese21 I understand that it may seem that way. I have spent quite a bit of time and effort on this but the problem is that I can't really try and implement something until I figure out what it is that I am implementing. Regarding what you said, doesn't a BFS visit every node, so this sequence would not be a path from vertex a to b.
  
  – Jac Frall
  Mar 23 at 0:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Sorry! Hmm. Take a look at Dijkstras Algorithm or A*. It depends. Are your connections weighted? BFS is probably not what you want to use.
  
  – mackycheese21
  Mar 23 at 0:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @mackycheese21 In the original graph the edges were weighted but then I found a Minimum spanning tree from that. So now, there is just one unique path from any two vertices and I just need an algorithm for finding it. So the tree can be treated as if it was unweighted.
  
  – Jac Frall
  Mar 23 at 0:58
  

  
  
  
  

add a comment | 

1

I am trying to implement a BFS that returns a path from a to b in form of a list of vertices. I am implementing this BFS on a tree so I know it will be the shortest path if I can find one. However, so far my research has only led me to find BSF algorithms that search and find nodes, rather than return a path.

The input that I am dealing with is an adjacency matrix of the Minimum Spanning Tree. I must take this and find path from one point to the other.

java breadth-first-search

share|improve this question

edited Mar 23 at 0:25

Jac Frall

asked Mar 22 at 23:48

Jac FrallJac Frall

1917

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  More details? Please? This feels a little like you haven't put too much effort. But the basic idea is just store a list of all nodes visited in the BSF search, and then that is the path.
  
  – mackycheese21
  Mar 22 at 23:52
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @mackycheese21 I understand that it may seem that way. I have spent quite a bit of time and effort on this but the problem is that I can't really try and implement something until I figure out what it is that I am implementing. Regarding what you said, doesn't a BFS visit every node, so this sequence would not be a path from vertex a to b.
  
  – Jac Frall
  Mar 23 at 0:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Sorry! Hmm. Take a look at Dijkstras Algorithm or A*. It depends. Are your connections weighted? BFS is probably not what you want to use.
  
  – mackycheese21
  Mar 23 at 0:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  @mackycheese21 In the original graph the edges were weighted but then I found a Minimum spanning tree from that. So now, there is just one unique path from any two vertices and I just need an algorithm for finding it. So the tree can be treated as if it was unweighted.
  
  – Jac Frall
  Mar 23 at 0:58
  

  
  
  
  

add a comment | 

I am trying to implement a BFS that returns a path from a to b in form of a list of vertices. I am implementing this BFS on a tree so I know it will be the shortest path if I can find one. However, so far my research has only led me to find BSF algorithms that search and find nodes, rather than return a path.

The input that I am dealing with is an adjacency matrix of the Minimum Spanning Tree. I must take this and find path from one point to the other.

java breadth-first-search

share|improve this question

edited Mar 23 at 0:25

Jac Frall

asked Mar 22 at 23:48

Jac FrallJac Frall

1917

share|improve this question

edited Mar 23 at 0:25

Jac Frall

asked Mar 22 at 23:48

Jac FrallJac Frall

1917

share|improve this question

edited Mar 23 at 0:25

Jac Frall

asked Mar 22 at 23:48

Jac FrallJac Frall

1917

asked Mar 22 at 23:48

Jac FrallJac Frall

1917

asked Mar 22 at 23:48

Jac FrallJac Frall

1917

2 Answers
2

active

oldest

votes

1

If you really want to use BFS to solve this, to trace the path from source to destination you need to store the parent of each node visited. Here's a sample BFS without optimizations.

import java.util.*;

public class bfs 

 static class Node 
 Node parent;
 int x;

 Node (int x) 
 this (x, null);
 

 Node (int x, Node parent) 
 this.parent = parent;
 this.x = x;
 

 void trace () 
 if (parent == null) 
 System.out.print (x);
 else 
 parent.trace ();
 System.out.print ("->" + x);
 
 
 

 static void bfs (int start, int goal, int[][] adj) 
 List<Node> list = new ArrayList<> ();

 list.add (new Node (start));

 while (!list.isEmpty ()) 
 Node cur = list.remove (0);

 if (cur.x == goal) 
 cur.trace ();
 break;
 else 
 for (int i = 0; i < adj[cur.x].length; i++) 
 if (adj[cur.x][i] == 1) 
 list.add (new Node (i, cur));
 
 
 
 
 

 public static void main (String[] args) 
 int[][] adjacency_matrix = 
 0, 1, 1, 0, 0,
 1, 0, 0, 1, 0,
 1, 0, 0, 0, 0,
 0, 1, 0, 0, 1,
 0, 0, 0, 1, 0
 ;
 int start = 0;
 int goal = 4;

 bfs (start, goal, adjacency_matrix);
 

share|improve this answer

answered Mar 23 at 0:10

alvinalvordalvinalvord

1067

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Now that I think of it it is not absolutely necessary that I use a node searching algorithm. I simply need to find a path.
  
  – Jac Frall
  Mar 23 at 0:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Is there any way of doing this non recursively
  
  – Jac Frall
  Mar 23 at 0:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Yes it can be done without recursion but you will need to store an array or a list in the Node.
  
  – alvinalvord
  Mar 23 at 1:20
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  I figured it out. Thanks!
  
  – Jac Frall
  Mar 23 at 1:39
  

  
  
  
  

add a comment | 

0

Dijkstra or A* is probably what you want to use. It depends, though. What you seem to be describing is a pathfinding algorithm, not a node search.

share|improve this answer

answered Mar 23 at 0:04

mackycheese21mackycheese21

568416

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  That makes sense. I got so many hits for BFS when googling that I felt I was on the right path
  
  – Jac Frall
  Mar 23 at 0:14
  

  
  
  
  

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
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
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

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%2fstackoverflow.com%2fquestions%2f55309178%2fhow-to-find-a-path-from-one-vertex-to-another-in-a-tree-using-breadth-first-sear%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

1

If you really want to use BFS to solve this, to trace the path from source to destination you need to store the parent of each node visited. Here's a sample BFS without optimizations.

import java.util.*;

public class bfs 

 static class Node 
 Node parent;
 int x;

 Node (int x) 
 this (x, null);
 

 Node (int x, Node parent) 
 this.parent = parent;
 this.x = x;
 

 void trace () 
 if (parent == null) 
 System.out.print (x);
 else 
 parent.trace ();
 System.out.print ("->" + x);
 
 
 

 static void bfs (int start, int goal, int[][] adj) 
 List<Node> list = new ArrayList<> ();

 list.add (new Node (start));

 while (!list.isEmpty ()) 
 Node cur = list.remove (0);

 if (cur.x == goal) 
 cur.trace ();
 break;
 else 
 for (int i = 0; i < adj[cur.x].length; i++) 
 if (adj[cur.x][i] == 1) 
 list.add (new Node (i, cur));
 
 
 
 
 

 public static void main (String[] args) 
 int[][] adjacency_matrix = 
 0, 1, 1, 0, 0,
 1, 0, 0, 1, 0,
 1, 0, 0, 0, 0,
 0, 1, 0, 0, 1,
 0, 0, 0, 1, 0
 ;
 int start = 0;
 int goal = 4;

 bfs (start, goal, adjacency_matrix);
 

share|improve this answer

answered Mar 23 at 0:10

alvinalvordalvinalvord

1067

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Now that I think of it it is not absolutely necessary that I use a node searching algorithm. I simply need to find a path.
  
  – Jac Frall
  Mar 23 at 0:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Is there any way of doing this non recursively
  
  – Jac Frall
  Mar 23 at 0:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Yes it can be done without recursion but you will need to store an array or a list in the Node.
  
  – alvinalvord
  Mar 23 at 1:20
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  I figured it out. Thanks!
  
  – Jac Frall
  Mar 23 at 1:39
  

  
  
  
  

add a comment | 

1

If you really want to use BFS to solve this, to trace the path from source to destination you need to store the parent of each node visited. Here's a sample BFS without optimizations.

import java.util.*;

public class bfs 

 static class Node 
 Node parent;
 int x;

 Node (int x) 
 this (x, null);
 

 Node (int x, Node parent) 
 this.parent = parent;
 this.x = x;
 

 void trace () 
 if (parent == null) 
 System.out.print (x);
 else 
 parent.trace ();
 System.out.print ("->" + x);
 
 
 

 static void bfs (int start, int goal, int[][] adj) 
 List<Node> list = new ArrayList<> ();

 list.add (new Node (start));

 while (!list.isEmpty ()) 
 Node cur = list.remove (0);

 if (cur.x == goal) 
 cur.trace ();
 break;
 else 
 for (int i = 0; i < adj[cur.x].length; i++) 
 if (adj[cur.x][i] == 1) 
 list.add (new Node (i, cur));
 
 
 
 
 

 public static void main (String[] args) 
 int[][] adjacency_matrix = 
 0, 1, 1, 0, 0,
 1, 0, 0, 1, 0,
 1, 0, 0, 0, 0,
 0, 1, 0, 0, 1,
 0, 0, 0, 1, 0
 ;
 int start = 0;
 int goal = 4;

 bfs (start, goal, adjacency_matrix);
 

share|improve this answer

answered Mar 23 at 0:10

alvinalvordalvinalvord

1067

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Now that I think of it it is not absolutely necessary that I use a node searching algorithm. I simply need to find a path.
  
  – Jac Frall
  Mar 23 at 0:14
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Is there any way of doing this non recursively
  
  – Jac Frall
  Mar 23 at 0:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Yes it can be done without recursion but you will need to store an array or a list in the Node.
  
  – alvinalvord
  Mar 23 at 1:20
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  I figured it out. Thanks!
  
  – Jac Frall
  Mar 23 at 1:39
  

  
  
  
  

add a comment | 

If you really want to use BFS to solve this, to trace the path from source to destination you need to store the parent of each node visited. Here's a sample BFS without optimizations.

import java.util.*;

public class bfs 

 static class Node 
 Node parent;
 int x;

 Node (int x) 
 this (x, null);
 

 Node (int x, Node parent) 
 this.parent = parent;
 this.x = x;
 

 void trace () 
 if (parent == null) 
 System.out.print (x);
 else 
 parent.trace ();
 System.out.print ("->" + x);
 
 
 

 static void bfs (int start, int goal, int[][] adj) 
 List<Node> list = new ArrayList<> ();

 list.add (new Node (start));

 while (!list.isEmpty ()) 
 Node cur = list.remove (0);

 if (cur.x == goal) 
 cur.trace ();
 break;
 else 
 for (int i = 0; i < adj[cur.x].length; i++) 
 if (adj[cur.x][i] == 1) 
 list.add (new Node (i, cur));
 
 
 
 
 

 public static void main (String[] args) 
 int[][] adjacency_matrix = 
 0, 1, 1, 0, 0,
 1, 0, 0, 1, 0,
 1, 0, 0, 0, 0,
 0, 1, 0, 0, 1,
 0, 0, 0, 1, 0
 ;
 int start = 0;
 int goal = 4;

 bfs (start, goal, adjacency_matrix);
 

share|improve this answer

answered Mar 23 at 0:10

alvinalvordalvinalvord

1067

import java.util.*;

public class bfs 

 static class Node 
 Node parent;
 int x;

 Node (int x) 
 this (x, null);
 

 Node (int x, Node parent) 
 this.parent = parent;
 this.x = x;
 

 void trace () 
 if (parent == null) 
 System.out.print (x);
 else 
 parent.trace ();
 System.out.print ("->" + x);
 
 
 

 static void bfs (int start, int goal, int[][] adj) 
 List<Node> list = new ArrayList<> ();

 list.add (new Node (start));

 while (!list.isEmpty ()) 
 Node cur = list.remove (0);

 if (cur.x == goal) 
 cur.trace ();
 break;
 else 
 for (int i = 0; i < adj[cur.x].length; i++) 
 if (adj[cur.x][i] == 1) 
 list.add (new Node (i, cur));
 
 
 
 
 

 public static void main (String[] args) 
 int[][] adjacency_matrix = 
 0, 1, 1, 0, 0,
 1, 0, 0, 1, 0,
 1, 0, 0, 0, 0,
 0, 1, 0, 0, 1,
 0, 0, 0, 1, 0
 ;
 int start = 0;
 int goal = 4;

 bfs (start, goal, adjacency_matrix);
 

share|improve this answer

answered Mar 23 at 0:10

alvinalvordalvinalvord

1067

answered Mar 23 at 0:10

alvinalvordalvinalvord

1067

answered Mar 23 at 0:10

alvinalvordalvinalvord

1067

0

Dijkstra or A* is probably what you want to use. It depends, though. What you seem to be describing is a pathfinding algorithm, not a node search.

share|improve this answer

answered Mar 23 at 0:04

mackycheese21mackycheese21

568416

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  That makes sense. I got so many hits for BFS when googling that I felt I was on the right path
  
  – Jac Frall
  Mar 23 at 0:14
  

  
  
  
  

add a comment | 

0

Dijkstra or A* is probably what you want to use. It depends, though. What you seem to be describing is a pathfinding algorithm, not a node search.

share|improve this answer

answered Mar 23 at 0:04

mackycheese21mackycheese21

568416

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  That makes sense. I got so many hits for BFS when googling that I felt I was on the right path
  
  – Jac Frall
  Mar 23 at 0:14
  

  
  
  
  

add a comment | 

Dijkstra or A* is probably what you want to use. It depends, though. What you seem to be describing is a pathfinding algorithm, not a node search.

share|improve this answer

answered Mar 23 at 0:04

mackycheese21mackycheese21

568416

share|improve this answer

answered Mar 23 at 0:04

mackycheese21mackycheese21

568416

answered Mar 23 at 0:04

mackycheese21mackycheese21

568416

answered Mar 23 at 0:04

mackycheese21mackycheese21

568416