1. BFS와 DFS

대표적인 그래프 탐색 알고리즘

너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식

깊이 우선 탐색 (Depth First Search) : 정점과 자식들을 먼저 탐색하는 방식

 

출처 : https://fastcampus.co.kr/courses/210773/clips/

 

2. DFS 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Main3 {
    public static Integer node;
    public static ArrayList<ArrayList<Integer>> adj =  new ArrayList<>();
    public static Boolean visited[] = new Boolean[node];

    public static void addEdge (Integer node1, Integer node2) {
        adj.get(node1).add(node2);
    }

    public static void dfs (Integer node) {
        if (visited[node]) return;

        visited[node] = true;
        System.out.println(node + " ");

        for (int i = 0; i < adj.get(node).size(); i++) {
            int adjNode = adj.get(node).get(i);
            dfs(adjNode);
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        node = sc.nextInt();

        for (int i = 0; i < node + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        Integer node2 = sc.nextInt();

        addEdge(node, node2);
    }
}

 

3. 시간 복잡도

노드수 : V

간선수 : E

시간 복잡도 : O(V + E)

저작자표시 비영리 (새창열림)

'Algorithm > 알고리즘' 카테고리의 다른 글

병합 정렬  (0) 2023.02.05
퀵정렬  (0) 2023.02.05
너비 우선 탐색 (BFS)  (0) 2023.01.23
그래프(Graph)  (0) 2023.01.23
동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer)  (0) 2023.01.20

1. BFS와 DFS

대표적인 그래프 탐색 알고리즘

너비 우선 탐색 (Breadth First Search) : 정점들과 같은 레벨에 있는 노드들 (형제 노드들)을 먼저 탐색하는 방식

깊이 우선 탐색 (Depth First Search) : 정점과 자식들을 먼저 탐색하는 방식

 

출처 :&nbsp;https://fastcampus.co.kr/courses/210773/clips/

 

2. BFS 구현

import lombok.extern.slf4j.Slf4j;

import java.util.*;

@Slf4j
public class Main {
    public static Integer node;
    public static ArrayList<ArrayList<Integer>> adj =  new ArrayList<>();

    public static void addEdge (Integer node1, Integer node2) {
        adj.get(node1).add(node2);
    }

    public static void bfs (Integer newNode) {
        Boolean visited[] = new Boolean[node];
        LinkedList<Integer> queue = new LinkedList<Integer>();

        visited[newNode] = true;
        queue.add(newNode);

        while (!queue.isEmpty()) {
            int now = queue.poll();
            System.out.println(now + " ");
            for (int i = 0; i < adj.get(now).size(); i++) {
                int adjNode = adj.get(now).get(i);
                if (!visited[adjNode]) {
                    visited[adjNode] = true;
                    queue.add(adjNode);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        node = sc.nextInt();

        for (int i = 0; i < node + 1; i++) {
            adj.add(new ArrayList<Integer>());
        }

        Integer node2 = sc.nextInt();

        addEdge(node, node2);
    }
}

 

3. 시간 복잡도

노드수 : V

간선수 : E

시간 복잡도 : O(V + E)

저작자표시 비영리 (새창열림)

'Algorithm > 알고리즘' 카테고리의 다른 글

퀵정렬  (0) 2023.02.05
깊이 우선 탐색 (DFS)  (0) 2023.01.23
그래프(Graph)  (0) 2023.01.23
동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer)  (0) 2023.01.20
재귀 용법 (recursive call)  (0) 2023.01.20

+ Recent posts

티스토리툴바