Dtjytyk

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

An adverb for when you're not exaggerating

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

Amount of permutations on an NxNxN Rubik's Cube

AppleTVs create a chatty alternate WiFi network

Is there a kind of relay that only consumes power when switching?

Is there any word for a place full of confusion?

Is a ledger board required if the side of my house is wood?

Significance of Cersei's obsession with elephants?

Is it a good idea to use CNN to classify 1D signal?

Do any jurisdictions seriously consider reclassifying social media websites as publishers?

Drawing without replacement: why is the order of draw irrelevant?

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

Effects on objects due to a brief relocation of massive amounts of mass

How do I find out the mythology and history of my Fortress?

Morning, Afternoon, Night Kanji

What is the difference between globalisation and imperialism?

Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?

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

Is CEO the "profession" with the most psychopaths?

Do wooden building fires get hotter than 600°C?

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

Using audio cues to encourage good posture

How does the math work when buying airline miles?

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

DG4

asked 3 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 2 hours ago

DG4

asked 3 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 2 hours ago

DG4

asked 3 hours ago

DG4DG4

1135

$endgroup$

share|cite|improve this question

edited 2 hours ago

DG4

asked 3 hours ago

DG4DG4

1135

share|cite|improve this question

edited 2 hours ago

DG4

asked 3 hours ago

DG4DG4

1135

asked 3 hours ago

DG4DG4

1135

asked 3 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 1 hour 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 1 hour 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 1 hour 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 1 hour 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 1 hour 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 1 hour 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 1 hour ago

Bryce KilleBryce Kille

665