LeetCode Graph

Giriş

Sorularda önce bir dizi veriliyor ve Graph yapısı kurmamız gerekiyor. Graph yapısının nasıl kurulduğu çözümü ve geriye kalan kodları da etkiliyor.

1. Graph'ın Kendisi

1. Array şeklinde olabilir.

2. Map şeklinde olabilir

3. Tree şeklinde olabilir

1.1 Array Şeklinde Graph

Şöyle yaparız. Burada bir node'a erişim için dönmek gerekiyor.

List<Nodex> nodelist = new ArrayList<>();

1.2 Map Şeklinde Graph

Şöyle yaparız. Burada her bir node'a sayı veriliyor.

Map<Integer, List<Integer>> adjList = new HashMap<>(words.length);

 

2. Graph Kurulması

2.1  List Tipindeki Girdiden Adjacency List Şeklinde Graph Kurma

Buradaki yapı şuna benzer. Her node bir diğerine pointer tutar

public class Node {

  private final List<Node> vertices = new ArrayList<>();

  public void addVertex(Nodex node){
    vertices.add(node);
  }

  public List<Predecessor> getPathToRoot(){
    List<Node> path = new ArrayList<>();
    if(!vertices.isEmpty()){
      path.add(this);
      path.addAll(vertices.get(0).getPathToRoot());
    }
    return path;
  }
  ...
}

Ben elimdeki her girdiyi graph'taki bir node'a eklemek için çalışırım. Şöyle yaparım

//create graph as list 
List<Nodex> nodelist = new ArrayList<>();
//construct graph
for(String word: words){
  Node newNode = new Node(word);
  nodeList.add(newNode);
  for(Node node: nodeList){
    if(node.isX(word)){
      node.addvertex(newNode);
      ...
    }
  }
}

2.2  List Tipindeki Girdiden Adjacency Tree Şeklinde Graph Kurma

Elimizde şöyle bir kod olsun

public class TreeNode {

  private int nodeId;

  private int treeId;

  private List<Integer> parentId;

  private List<TreeNode> children;

  private List<TreeNode> parents;

  public TreeNode() {
    this.parentId = new ArrayList<>();
    this.children = new ArrayList<>();
    this.parents = new ArrayList<>();
  }

  public void addChild(TreeNode child) {
    if (this.children!= null && !this.children.contains(child) && child != null)
      this.children.add(child);
  }

  public void addParent(TreeNode parent) {
    if (this.parents!= null && !this.parents.contains(parent) && parent != null)
      this.parents.add(parent);
  }
}

Şöyle yaparız. Burada liste dolaşılıyor ve nodeId değerine göre bir Map'e dolduruluyor. Daha sonra liste bir kere daha dolaşılıyor ve her düğümün parentId'si alınıyor. parentId'ye sahip düğüm bulunuyor ve düğüm buna ekleniyor.

public TreeNode assembleTree(List<TreeNode> nodes, int rootNodeId) {
  Map<Integer, TreeNode> mapTmp = new LinkedHashMap<>();
  // Save all nodes to a map
  for (TreeNode current : nodes) {
    mapTmp.put(current.getNodeId(), current);
  }

  // Loop and assign parent/child relationships
  for (TreeNode current : nodes) {
    List<Integer> parents = current.getParentId();

    if (!CollectionUtils.isEmpty(parents)) {
      for (Integer pid : parents) {
        TreeNode parent = mapTmp.get(pid);
        if (parent != null) {
          parent.addChild(current);
          current.addParent(parent);
        }
      }
    }
  }
  return mapTmp.get(rootNodeId);
}