Vjylku

How often does castling occur in grandmaster games?

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

What was the first language to use conditional keywords?

Is there hard evidence that the grant peer review system performs significantly better than random?

A term for a woman complaining about things/begging in a cute/childish way

Is grep documentation about ignoring case wrong, since it doesn't ignore case in filenames?

What would you call this weird metallic apparatus that allows you to lift people?

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

Putting class ranking in CV, but against dept guidelines

Why should I vote and accept answers?

Hangman Game with C++

How to react to hostile behavior from a senior developer?

What are the diatonic extended chords of C major?

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

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

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

Do wooden building fires get hotter than 600°C?

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

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

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

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

Selecting user stories during sprint planning

How would a mousetrap for use in space work?

How could we fake a moon landing now?

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