[Algorithm] DAG(Directed Acyclic Graph)

DAG 란?

• Directed Acyclic Graph 방향을 가지지만 순환이 없는 방향 그래프이다.
• 왼쪽에서 오른쪽 방향으로 이동한다.

 

 

 

 

용어

그래프에서 사용하는 용어들이있다.

• Indgree: 타겟노드에 들어오는 엣지의수
• Outdgree: 타겟노드에서 나가는 엣지의수
• Incomming: 들어오는 엣지
• Outcomming: 나가는 엣지

 

 

 

 

비 순환이란?

• A 노드에서 출발했다면 A 노드로 다시 돌아오는 일이 없어야 한다.

 

 

 

 

위상정렬

• DAG 에서 노드들의 순서화 
• 단 모든 Edge(Vi,Vj)에 대해서 i < j 가 되어야 한다.
• 정렬 할때는 우선순위가 먼저 되어야 하는 것을 가장 앞으로 가져온다.
• 위상정렬에는 여러가지 정렬이 존재 한다.

 

 

정렬방법

• 1. Indegree 가 0 인노드를 선택한다 A 또는 B (선행작업이 없는 노드를 말한다.)
• 2. 선택된 노드를 제거한다.
• 1~2 를 반복한다. 

 

 

 

 

 

구현

 

DagGraph

package algorithm.dag;

import java.util.ArrayList;
import java.util.Deque;
import java.util.Stack;


public class DagGraph {
    private boolean []visit;

    public void dfsts(int v, ArrayList<ArrayList<Integer>> graph,  Deque<Integer> queue)
    {

        visit[v] = true;

        for(int i = 0; i < graph.get(v).size(); i++)
        {
            if (visit[graph.get(v).get(i)] == false) {
                dfsts(graph.get(v).get(i), graph, queue);
            }
        }

        queue.addFirst(v);
    }

    public void topologicalSort2(ArrayList<ArrayList<Integer>> graph, Deque<Integer> deque )
    {

        for (int i = 1; i < graph.size(); i++)
        {
            visit[i] = false;
        }

        ArrayList<Integer> mList;
        for(int i = 1; i < graph.size(); i++) {
            if (visit[i] == false) {
                dfsts(i, graph, deque);
            }
        }
    }

    public void printGraph(ArrayList<ArrayList<Integer>> graph) {
        for (int i = 1; i < graph.size(); i++) {
            System.out.print(i);
            for (int j = 0; j <graph.get(i).size(); j++) {
                System.out.print(" -> " + graph.get(i).get(j));
            }
            System.out.println("");
        }
    }

    public void addVertex(ArrayList<ArrayList<Integer>> graph, int v1, int v2)
    {
        graph.get(v1).add(v2);
    }

    public void init(ArrayList<ArrayList<Integer>> graph, int size) {
        visit = new boolean[size + 1];
        for (int i = 0; i < size + 1; i++) {
            graph.add(new ArrayList<Integer>());
        }
    }
}

 

 

 

 

DagTest

import algorithm.dag.DagGraph;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class DagGraphTest {
    public static void main(String[] args) {

        DagGraph daggraph = new DagGraph();
        int graphSize = 7;

        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        daggraph.init(graph, graphSize);

        daggraph.addVertex(graph, 1,4);
        daggraph.addVertex(graph,1,3);
        daggraph.addVertex(graph,2,3);
        daggraph.addVertex(graph,3,5);
        daggraph.addVertex(graph,4,5);
        daggraph.addVertex(graph,4,6);
        daggraph.addVertex(graph,5,6);
        daggraph.addVertex(graph,5,7);




        // daggraph.printGraph(graph);

        Deque<Integer> queue = new ArrayDeque<>();
        daggraph.topologicalSort2(graph, queue);

        while(!queue.isEmpty()) {
            System.out.print(queue.pollFirst());
            if(queue.size() != 0) {
                System.out.print("->");
            }
        }
    }
}

 

 

 

 

전체코드

 

구현코드 : https://github.com/rnrl1215/algorithm-study/blob/main/src/main/java/algorithm/dag/DagGraph.java

테스트코드: https://github.com/rnrl1215/algorithm-study/blob/main/src/test/java/GraphTest.java