Arsthbt

Take 2! Is this homebrew Lady of Pain warlock patron balanced?

Is CEO the "profession" with the most psychopaths?

Is there any word for a place full of confusion?

Do I really need to have a message in a novel to appeal to readers?

Monolithic + MicroServices

Project Euler #1 in C++

How often does castling occur in grandmaster games?

Can the Great Weapon Master feat's damage bonus and accuracy penalty apply to attacks from the Spiritual Weapon spell?

Should I use a zero-interest credit card for a large one-time purchase?

Converted a Scalar function to a TVF function for parallel execution-Still running in Serial mode

How does the secondary effect of the Heat Metal spell interact with a creature resistant/immune to fire damage?

Is it fair for a professor to grade us on the possession of past papers?

How could we fake a moon landing now?

Morning, Afternoon, Night Kanji

Why do we need to use the builder design pattern when we can do the same thing with setters?

Why does it sometimes sound good to play a grace note as a lead in to a note in a melody?

How do living politicians protect their readily obtainable signatures from misuse?

How to compare two different files line by line in unix?

How do I use the new nonlinear finite element in Mathematica 12 for this equation?

Why do early math courses focus on the cross sections of a cone and not on other 3D objects?

Why wasn't DOSKEY integrated with COMMAND.COM?

Can a new player join a group only when a new campaign starts?

Update module to run alter command

Crossing US/Canada Border for less than 24 hours

What is the meaning of 'breadth' in breadth first search?

1

$begingroup$

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this:

Breadth-first search is so named because it expands the frontier
between discovered and undiscovered vertices uniformly across the
breadth of the frontier.

However, I'm not able to understand the meaning of this statement. I'm confused about this word "frontier" and breadth of that frontier.

So, can someone please answer this question in a way which is easy to understand for a beginner like me?

graphs graph-theory shortest-path graph-traversal

share|cite|improve this question

edited 3 hours ago

DG4

asked 4 hours ago

DG4DG4

1135

$endgroup$

add a comment | 

1

$begingroup$

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this:

Breadth-first search is so named because it expands the frontier
between discovered and undiscovered vertices uniformly across the
breadth of the frontier.

However, I'm not able to understand the meaning of this statement. I'm confused about this word "frontier" and breadth of that frontier.

So, can someone please answer this question in a way which is easy to understand for a beginner like me?

graphs graph-theory shortest-path graph-traversal

share|cite|improve this question

edited 3 hours ago

DG4

asked 4 hours ago

DG4DG4

1135

$endgroup$

add a comment | 

$begingroup$

I was learning about breadth first search and a question came in my mind that why BFS is called so. In the book Introduction to Algorithms by CLRS, I read the following reason for this:

Breadth-first search is so named because it expands the frontier
between discovered and undiscovered vertices uniformly across the
breadth of the frontier.

However, I'm not able to understand the meaning of this statement. I'm confused about this word "frontier" and breadth of that frontier.

So, can someone please answer this question in a way which is easy to understand for a beginner like me?

graphs graph-theory shortest-path graph-traversal

share|cite|improve this question

edited 3 hours ago

DG4

asked 4 hours ago

DG4DG4

1135

$endgroup$

share|cite|improve this question

edited 3 hours ago

DG4

asked 4 hours ago

DG4DG4

1135

share|cite|improve this question

edited 3 hours ago

DG4

asked 4 hours ago

DG4DG4

1135

asked 4 hours ago

DG4DG4

1135

asked 4 hours ago

DG4DG4

1135

1 Answer
1

active

oldest

votes

4

$begingroup$

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the deepest part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here

share|cite|improve this answer

answered 2 hours ago

Bryce KilleBryce Kille

665

New contributor

Bryce Kille 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 | 

Your Answer

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "419"
;
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: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
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%2fcs.stackexchange.com%2fquestions%2f107187%2fwhat-is-the-meaning-of-breadth-in-breadth-first-search%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

4

$begingroup$

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the deepest part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here

share|cite|improve this answer

answered 2 hours ago

Bryce KilleBryce Kille

665

New contributor

Bryce Kille 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 | 

4

$begingroup$

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the deepest part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here

share|cite|improve this answer

answered 2 hours ago

Bryce KilleBryce Kille

665

New contributor

Bryce Kille 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$

Consider the data structure used to represent the search. In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

The “frontier” is the set of all nodes in the search data structure. The queue will will iterate through all nodes on the frontier sequentially, thus iterating across the breadth of the frontier. DFS will always pop the most recently discovered state off of the stack, thus always iterating over the deepest part of the frontier.

Consider the image below. Notice how the DFS goes straight to the deepest parts of the tree whereas BFS iterates over the breadth of each level.

Image here

share|cite|improve this answer

answered 2 hours ago

Bryce KilleBryce Kille

665

New contributor

Bryce Kille 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 2 hours ago

Bryce KilleBryce Kille

665

New contributor

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

answered 2 hours ago

Bryce KilleBryce Kille

665

New contributor

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

answered 2 hours ago

Bryce KilleBryce Kille

665