Breadth First Search (BFS) is a graph-based algorithm that is used to traverse and search through a graph data structure. It is a simple yet effective algorithm that can be used in various applications such as social networking, web crawling, and more. In this article, we will discuss the BFS algorithm and its implementation in Golang.
BFS Algorithm
BFS is a graph traversal algorithm that starts at the root node and explores all the neighboring nodes at the current depth before moving on to the next level of nodes. It explores the graph in a breadth-first manner, hence the name Breadth First Search. BFS can be implemented using a queue data structure to keep track of the nodes to be visited.
Pseudocode
BFS(graph, start_node):
queue = []
visited = []
queue.enqueue(start_node)
while queue is not empty:
node = queue.dequeue()
if node not in visited:
visited.append(node)
for neighbor in graph[node]:
queue.enqueue(neighbor)
Golang Implementation
Let's implement the BFS algorithm in Golang. We will represent the graph as an adjacency list.
ggppackage main
import (
"container/list"
"fmt"
"net/http"
"golang.org/x/net/html"
)
func BFS(url string) {
queue := list.New()
visited := make(map[string]bool)
queue.PushBack(url)
visited[url] = true
for queue.Len() > 0 {
node := queue.Front()
queue.Remove(node)
url := node.Value.(string)
fmt.Println("Visiting", url)
resp, err := http.Get(url)
if err != nil {
continue
}
defer resp.Body.Close()
z := html.NewTokenizer(resp.Body)
for {
tt := z.Next()
switch {
case tt == html.ErrorToken:
// End of the document, we're done
return
case tt == html.StartTagToken:
t := z.Token()
if t.Data == "a" {
for _, a := range t.Attr {
if a.Key == "href" {
absolute := fixUrl(a.Val, url)
if absolute != "" && !visited[absolute] {
fmt.Println(" Found link:", absolute)
visited[absolute] = true
queue.PushBack(absolute)
}
}
}
}
}
}
}
}
func fixUrl(href, base string) string {
url, err := url.Parse(href)
if err != nil {
return ""
}
baseUrl, err := url.Parse(base)
if err != nil {
return ""
}
return baseUrl.ResolveReference(url).String()
}
func main() {
BFS("<https://medium.com>")
}
Realistic Use Case
One realistic use case of BFS is web crawling. Web crawling is the process of automatically browsing the web and collecting data. BFS can be used to crawl web pages in a breadth-first manner, starting from a given URL and following all the links on the page. This can be useful in building search engines, web indexing, and more.
In the implementation above, we have used BFS to crawl web pages starting from a given URL. The BFS algorithm is used to visit all the linked pages in a breadth-first manner and collect data from them. We have used the net/http and golang.org/x/net/html packages to send HTTP requests and parse HTML respectively.
In conclusion, BFS is a simple yet effective algorithm that can be used in various applications. We have discussed the BFS algorithm and its implementation in Golang, along with a realistic use case of web crawling.
In the case of the example above, the generated output looks like this:
Visiting <https://medium.com>
Found link: <https://medium.com/>
Found link: <https://medium.com/about?autoplay=1>
Found link: <https://medium.com/membership>
Found link: <https://about.medium.com/creators/>
Found link: <https://medium.com/m/signin?operation=login&redirect=https%3A%2F%2Fmedium.com%2F&source=--------------------------lo_home_nav----------->
Found link: <https://medium.com/m/signin?operation=register&redirect=https%3A%2F%2Fmedium.com%2F&source=--------------------------lo_home_nav----------->
Found link: <https://medium.com/@mindofjp?source=home---------0---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://mindofjp.medium.com/what-really-happens-to-a-human-body-at-titanic-depths-3f46ab545e0e?source=home---------0---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/@barackobama?source=home---------1---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://barackobama.medium.com/our-statements-on-the-u-s-supreme-courts-decision-to-overturn-affirmative-action-2e161f52b5d1?source=home---------1---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/eudaimonia-co?source=home---------2---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/@umairh?source=home---------2---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://eand.co/the-triumph-of-the-age-of-the-idiot-85c3ede7fa32?source=home---------2---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/@DawsonEJoyce?source=home---------3---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/@DawsonEJoyce/before-i-say-goodbye-looking-back-at-the-films-of-hayao-miyazaki-d813fd4cf8e7?source=home---------3---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/macoclock?source=home---------4---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/@theusefultech?source=home---------4---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/macoclock/9-new-must-have-macos-productivity-apps-for-daily-usage-fec955b1510c?source=home---------4---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/@Schwarzenegger?source=home---------5---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/@Schwarzenegger/terminate-negativity-fea2c77780a4?source=home---------5---------------------fcd7d4ff_9018_4fe9_ad34_14b2fddbe798-------7>
Found link: <https://medium.com/tag/programming?source=home---------0-----------programming-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/data-science?source=home---------1-----------data_science-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/technology?source=home---------2-----------technology-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/self-improvement?source=home---------3-----------self_improvement-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/writing?source=home---------4-----------writing-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/relationships?source=home---------5-----------relationships-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/machine-learning?source=home---------6-----------machine_learning-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/productivity?source=home---------7-----------productivity-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/tag/politics?source=home---------8-----------politics-------30---5be81a59_fae7_4850_986e_fe2b251623fc-------18>
Found link: <https://medium.com/explore-topics?source=home------------------------------------->
Found link: <https://medium.com/zora?source=home---------0------------------0---------->
Found link: <https://medium.com/@savalanolan?source=home---------0------------------0---------->
Found link: <https://zora.medium.com/so-what-if-they-did-thoughts-on-affirmative-action-b714834da28b?source=home---------0------------------0---------->
Found link: <https://medium.com/five-hundred-words?source=home---------1------------------0---------->
Found link: <https://medium.com/@mgs?source=home---------1------------------0---------->
Found link: <https://500ish.com/meta-threads-a-needle-ea3729f377be?source=home---------1------------------0---------->
Found link: <https://medium.com/@dougshapiro?source=home---------2------------------0---------->
Found link: <https://dougshapiro.medium.com/how-will-the-disruption-of-hollywood-play-out-42f724c921e1?source=home---------2------------------0---------->
Found link: <https://medium.com/ideaplatz?source=home---------3------------------0---------->
Found link: <https://medium.com/@cherylplatz?source=home---------3------------------0---------->
Found link: <https://medium.com/ideaplatz/fail-limit-exceeded-c656047c8082?source=home---------3------------------0---------->
Found link: <https://medium.com/human-parts?source=home---------4------------------0---------->
Found link: <https://medium.com/@allynesmith?source=home---------4------------------0---------->
Found link: <https://humanparts.medium.com/apparently-i-broke-up-with-myself-f92dd6d8a952?source=home---------4------------------0---------->
Found link: <https://medium.com/@clivethompson?source=home---------5------------------0---------->
Found link: <https://clivethompson.medium.com/the-case-for-reforesting-our-cities-f78c7332c3ff?source=home---------5------------------0---------->
Found link: <https://medium.com/@katrinapaulson?source=home---------6------------------0---------->
Found link: <https://katrinapaulson.medium.com/become-friends-with-your-future-self-e6d43222f8a7?source=home---------6------------------0---------->
Found link: <https://medium.com/@barackobama?source=home---------7------------------0---------->
Found link: <https://barackobama.medium.com/our-statements-on-the-u-s-supreme-courts-decision-to-overturn-affirmative-action-2e161f52b5d1?source=home---------7------------------0---------->
Found link: <https://medium.com/@saumil?source=home---------8------------------0---------->
Found link: <https://medium.com/@saumil/from-alien-to-american-from-jail-cell-to-general-manager-65e469e8c53?source=home---------8------------------0---------->
Found link: <https://medium.com/blog?source=home---------9------------------0---------->
Found link: <https://medium.com/@MediumStaff?source=home---------9------------------0---------->
Found link: <https://blog.medium.com/what-were-reading-the-mid-year-reset-ff271e53e29?source=home---------9------------------0---------->
Found link: <https://help.medium.com/hc/en-us?source=home------------------------------------->
Found link: <https://medium.statuspage.io/?source=home------------------------------------->
Found link: <https://about.medium.com/creators/?source=home------------------------------------->
Found link: <https://blog.medium.com/?source=home------------------------------------->
Found link: <https://medium.com/jobs-at-medium/work-at-medium-959d1a85284e?source=home------------------------------------->
Found link: <https://policy.medium.com/medium-privacy-policy-f03bf92035c9?source=home------------------------------------->
Found link: <https://policy.medium.com/medium-terms-of-service-9db0094a1e0f?source=home------------------------------------->
Found link: <https://medium.com/about?autoplay=1&source=home------------------------------------->
Found link: <https://speechify.com/medium?source=home------------------------------------->
Found link: <https://medium.com/business?source=home------------------------------------->
Found link: <https://medium.com/?source=home------------------------------------->
Found link: <https://itunes.apple.com/app/medium-everyones-stories/id828256236?pt=698524&mt=8&ct=home&source=home------------------------------------->
Found link: <https://play.google.com/store/apps/details?id=com.medium.reader&source=home------------------------------------->
References
- “Algorithms” by Sedgewick, Robert, Wayne, Kevin