bfs/dfs

readme.md

bfs/dfs

Created with <3 with dartpad.dev.

main.dart

// This is a basic Flutter widget test.
//
// To perform an interaction with a widget in your test, use the WidgetTester
// utility in the flutter_test package. For example, you can send tap and scroll
// gestures. You can also use WidgetTester to find child widgets in the widget
// tree, read text, and verify that the values of widget properties are correct.

import 'dart:collection';

/**
 *      0
 *     /
 *    1 -- 3    7
 *    |  / |\  /
 *    | /  |  5
 *    2 -- 4   \
 *              6 - 8
 * 
 * 
 * dfs(0)
 * 0 1 3 5 7 6 8 4 2
 * bfs(0)
 * 0 1 2 3 4 5 6 7 8
 * dfsR(0)
 * 0 1 2 3 4 5 6 8 7
 * 
 */

void main() {
  Graph g = Graph(9);

  g.addEdge(0, 1);
  g.addEdge(1, 2);
  g.addEdge(1, 3);
  g.addEdge(2, 3);
  g.addEdge(2, 4);
  g.addEdge(3, 4);
  g.addEdge(3, 5);
  g.addEdge(5, 6);
  g.addEdge(5, 7);
  g.addEdge(6, 8);

  g.dfs(index: 0);
//   g.bfs(index: 0);
//   g.dfsR(g.nodes[0]);
}

class Node {
  int? data;
  late List<Node> adjacent;
  bool marked = false;

  Node(int? data) {
    adjacent = [];
    marked = false;
    this.data = data;
  }
}

class Graph {
  List<Node> nodes = [];
  // 노드들 생성
  Graph(int size) {
    nodes = List<Node>.generate(size, ((index) => Node(index)));
  }

  // 노드사이 연결고리 추가
  void addEdge(int i1, int i2) {
    Node n1 = nodes[i1];
    Node n2 = nodes[i2];
    if (n1.adjacent.contains(n2) == false) {
      n1.adjacent.add(n2);
    }
    if (n2.adjacent.contains(n1) == false) {
      n2.adjacent.add(n1);
    }
  }

  void dfs({int index = 0}) {
    // root 정하고
    Node root = nodes[index];
    List<Node> stack = [];

    // stack에 넣고
    stack.add(root);
    // 방문도장 찍고
    root.marked = true;

    // 시작
    while (stack.isNotEmpty) {
      // 스택에서 꺼내고
      Node r = stack.removeLast();
      // 자식 있으면 방문도장 찍고 추가
      for (var n in r.adjacent) {
        if (n.marked == false) {
          n.marked = true;
          stack.add(n);
        }
      }

      // 나는 출력
      print('${r.data} ');
    }
  }

  void bfs({int index = 0}) {
    Node root = nodes[index];
    Queue<Node> queue = Queue<Node>();
    queue.add(root);
    root.marked = true;
    // 시작
    while (queue.isNotEmpty) {
      // 스택에서 꺼내고
      Node r = queue.removeFirst();
      // 자식 있으면 방문도장 찍고 추가
      for (var n in r.adjacent) {
        if (n.marked == false) {
          n.marked = true;
          queue.add(n);
        }
      }

      // 나는 출력
      print('${r.data} ');
    }
  }

  void dfsR(Node r) {
    if (r == null) return;
    r.marked = true;
    print('${r.data} ');
    for (var n in r.adjacent) {
      if (n.marked == false) {
        dfsR(n);
      }
    }
  }
}