estudy 한국어/English

Breadth-First Search (BFS)

519 단어·3 분·원문(.md)

Graph traversal algorithms typically include DFS and BFS. Today, we'll explore BFS.

BFS #

A representative graph traversal algorithm

A method that first explores nodes at the same level as the current vertex (sibling nodes)

Move as broadly as possible, then move down when there are no more options horizontally

For example, it's an algorithm used to determine if one city can be reached from another, or if specific terminals in an electronic circuit are connected.

Node Traversal Order in BFS #

Because it's a breadth-first search, it explores all nodes at the shallowest depth first, then moves to deeper nodes. That is, in the diagram, it first explores nodes 1 and 2 at depth 1. Once all nodes at depth 1 are explored, it then explores nodes 3, 4, 5, and 6 at depth 2.

Characteristics #

  • It's a good method for finding the shortest path between two nodes, as it explores distant nodes later.
  • It uses a queue to store the order of nodes to be explored and explores them in the order they were stored in the queue. A queue is used because it requires a First-In, First-Out (FIFO) approach.

BFS Implementation Algorithm #

  1. Start from the root node.
  2. Add nodes that are adjacent to the root node, have not been visited, and are not already in the Queue, to the Queue.
  3. Dequeue from the Queue and visit the node that was added to the queue first.
  1. Visit the root node at step 1.
  2. At steps 2, 3, 4, and 5, add adjacent nodes that have not been visited and are not already in the queue, to the queue.
  3. At step 6, move to node 1 (the first node stored in the queue) and check the conditions of its adjacent nodes.

Repeat this process until there are no more nodes in the queue.

Graph Implementation Methods #

  1. Adjacency Matrix
  2. Adjacency List

Let's take an example.

When implementing a graph like the one above, it can be done using an adjacency matrix or an adjacency list, as follows.

An adjacency matrix can be implemented as a 2D array, while an adjacency list can be implemented using an array of linked lists, an array of ArrayLists, or an ArrayList of ArrayLists, among other methods.

Code for BFS Implemented with Adjacency Matrix #

Structure required for adjacency matrix implementation

  1. Adjacency matrix array (int[][] graph)
  2. Visited status array (boolean[] visited)
  3. Queue (Queue queue)
  4. Array to store visited nodes in order (ArrayList arrList)
static void bfs(int node) {
    visited[node] = true;
    arrList.add(node);

    for(int i = 1; i <= nodeNum; i++){
        if(graph[node][i] == 1 && visited[i] == false && queue.contains(i) == false) {
            queue.add(i);
        }
    }
    if(!queue.isEmpty())
        bfs(queue.poll());
}

Code for BFS Implemented with Adjacency List #

Structure required for adjacency list implementation

  1. Adjacency list (ArrayList[] graph)
  2. Visited status array (boolean[] visited)
  3. Queue (Queue queue)
  4. Array to store visited nodes in order (ArrayList arrList)
static void bfs(int node) {
    visited[node] = true;
    arrList.add(node);

    for(int i = 0; i < graph[node].size(); i++){
        int adjNode = graph[node].get(i);
        if(visited[adjNode] == false && queue.contains(adjNode) == false) {
            queue.add(adjNode);
        }
    }

    if(!queue.isEmpty())
        bfs(queue.poll());
}
Algorithm/bfs.md