graph search two points

readme.md

graph search two points

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);

  
  bool result = g.search(1, 8);
  print(result);
//   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 initMarks(){
    for( Node n in nodes){
      n.marked = false;
    }
  }
  
  bool search(int p1, int p2){
    
    Node start = nodes[p1];
    Node end = nodes[p2];
    
    initMarks();
    
    List<Node> stack = [];
    // stack에 넣고
    stack.add(start);
    // 방문도장 찍고
    start.marked = true;

    // 시작
    while (stack.isNotEmpty) {
      // 스택에서 꺼내고
      Node r = stack.removeLast();
      
      // 시작과 끝이 같으면 찾았다 요놈
      if(r == end){
        return true;
      }
      
      // 자식 있으면 방문도장 찍고 추가
      for (var n in r.adjacent) {
        if (n.marked == false) {
          n.marked = true;
          stack.add(n);
        }
      }
      print(r.data);
    }
    
    
    // 끝까지 return 이 안되면 false
    return false;
  }
}