티스토리 뷰

BFS는 해(Solution)을 찾아서 트리의 모든 노드를 검사하는 무정보 탐색(Uninformed or Blind Search)입니다. 목표에 대한 고려없이 목표가 발견될 때까지 트리를 전부 탐색하는 방식인 것이죠.

실제로 구현할 때에는 FIFO Queue라는 자료구조를 이용하게 됩니다. 검사되지 않은 노드들은 OPEN상태의 용기에 담기고, 검사를 마친 노드는 CLOSE상태의 용기에 담기게 됩니다. 또, 만약 트리가 아닌 비가중치 그래프에서 최단경로를 탐색할 때에는 이미 방문했었다는 것을 표시할 용기가 따로 필요합니다.


BFS는 너비를 우선적으로 탐색하는 방법으로 


BFS 알고리즘은 주로 거리를 탐색하는데 많이 사용됩니다. 특정 출발지에서 특정 도착점까지의 경로를 찾거나 가장 빠른 경로, 가장 빠른 거리 등을 찾는데 사용된다고 합니다.  


  1. GPS Navigation systems: Navigation systems such as the Google Maps, which can give directions to reach from one place to another use BFS. They take your location to be the source node and your destination as the destination node on the graph. (A city can be represented as a graph by taking landmarks as nodes and the roads as the edges that connect the nodes in the graph.) BFS is applied and the shortest route is generated which is used to give directions or real time navigation.
  2. Computer Networks: Peer to peer (P2P) applications such as the torrent clients need to locate a file that the client (one who wants to download the file) is requesting.This is achieved by applying BFS on the hosts (one who supplies the file) on a network. Your computer is the host and it keeps traversing through the network to find a host for the required file (maybe your favourite movie).
  3. Facebook: It treats each user profile as a node on the graph and two nodes are said to be connected if they are each other's friends. Infact, apply BFS on the facebook graph and you will find that any two people are connected with each other by atmost five nodes in between. To say, that you can reach any random person in the world by traversing 5 nodes in between. (I did not run BFS on facebook graph, it is a well known fact). What do you think is the new facebook "Graph Search"(It is not directly BFS, but a lot of modifications over classic graph search algorithms.)
  4. Web CrawlersIt is quite an interesting application. They can be used to analyze what all sites you can reach by following links randomly on a particular website. (Even if you are mildly interested, look into it. It is fun).


Arpit AgarwalArpit AgarwalI am to knowledge what a drop is to an ocean


잘 설명되어 있는 곳1

잘 설명되어 있는 곳2


자료구조 코드 Animaiton으로 시각화해주는 사이트 GOOD!!!


문제풀이 참고 문제



댓글
댓글쓰기 폼
공지사항
Total
41,134
Today
34
Yesterday
59
링크
TAG
more
«   2018/07   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30 31        
글 보관함