Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lære Shortest Path in Graph | Practice
Breadth First Search
course content

Kursinnhold

Breadth First Search

Breadth First Search

1. What is BFS
How to SearchGraph Class Implementation
2. Practice
Breadth First TraverseCheck if is One ComponentShortest Path in GraphRestoring Shortest PathFind All Connected ComponentsIs a Tree
3. Improve Your Code
CongratulationsComponents MethodsBFT and BFS
4. Solving the Problems using BFS
Coloring PixelsShortest Clear Path

book
Shortest Path in Graph

BFS searching shortest path

Well done! Now, let's implement a method that helps us to find the length of shortest path between two vertices, i. e. minimum number of edges to reach end vertice from start.

You should store the length of the way from start to curr node, and you can do it by modifying visited array: visited[i] equals:

  • -1, if i not visited yet

  • 0, if i is visited as first node

  • 1, if i is a neighbor of node, that has mark 0

  • k, if i is a neighbor of node with mark k-1 etc.

This way, you'll store the distance between start and current node, like at the example:

So, the answer is a visited[end].

Oppgave

Swipe to start coding

bfs(start, end) returns a number of edges between start and end nodes. If there is no path, return -1.

Actually this method does traverse as BFT method, but until the end vertex is found. Copy & Paste your BFT algorithm, and add some changes.

Switch to desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 2. Kapittel 3
toggle bottom row

book
Shortest Path in Graph

BFS searching shortest path

Well done! Now, let's implement a method that helps us to find the length of shortest path between two vertices, i. e. minimum number of edges to reach end vertice from start.

You should store the length of the way from start to curr node, and you can do it by modifying visited array: visited[i] equals:

  • -1, if i not visited yet

  • 0, if i is visited as first node

  • 1, if i is a neighbor of node, that has mark 0

  • k, if i is a neighbor of node with mark k-1 etc.

This way, you'll store the distance between start and current node, like at the example:

So, the answer is a visited[end].

Oppgave

Swipe to start coding

bfs(start, end) returns a number of edges between start and end nodes. If there is no path, return -1.

Actually this method does traverse as BFT method, but until the end vertex is found. Copy & Paste your BFT algorithm, and add some changes.

Switch to desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Alt var klart?

Hvordan kan vi forbedre det?

Takk for tilbakemeldingene dine!

Seksjon 2. Kapittel 3
Switch to desktopBytt til skrivebordet for virkelighetspraksisFortsett der du er med et av alternativene nedenfor
Vi beklager at noe gikk galt. Hva skjedde?
some-alt