방향그래프(Directed Graph) 구현

방향그래프(Directed Graph) 구현도 무방향 그래프(Unidrect Graph) 구현 에서 한 것과 동일하게 인접리스트와 인접행렬을 이용하여 구현할 수 있다. 

차이점은 그림1 (비방향 그래프 vs 방향그래프) 처럼 방향그래프는 정점마다 연결된 에지에 화살표로 들어오고(incoming) 나가는(outgoing) 방향이 있기 때문에  구현하는데 약간 변형을 해야 한다. 

그림 1 ) 비방향 그래프 vs 방향그래프

인접행렬과 인접리스트를 이용하여 구현하는 상세 설명은 무방향 그래프(Unidrect Graph) 구현 을 참고하고 여기서는 무방향 그래프 구현과 차이가 나는 부분만 코드내 주석으로 설명하도록 하겠다.

인접리스트 이용하여 구현

import java.util.ArrayList;
import java.util.LinkedList;
 
public class Digraph {
 
    private static final String NEWLINE = System.getProperty("line.separator");
 
    // 방향그래프내 노드의 총 개수
    private final int V;
 
    // 방향그래프내 간선의 총 개수
    private int E;
 
    // 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들(edge)을 연결하기위한 자료구조.
    private ArrayList<LinkedList<Integer>> adj;
 
 
    // indegree[v] 는 정점 V의 incoming edge = indegree의 개수를 저장한다.
    private int[] indegree;
 
 
    // 방향그래프내 있을 정점의 개수로 클래스 초기화.
    public Digraph(int V) {
        if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
        this.V = V ; // 정점의 개수
        this.E = 0 ; // 아직 에지의 개수는 하나도 없음.
        indegree = new int[V];
 
        adj = new ArrayList<>(V);
        for (int v = 0; v < V; v++) {
            adj.add(new LinkedList<>());
        }
    }
 
    // 방향그래프내 노드의 총 개수를 리
    public int V() {
        return V;
    }
 
    // 방향그래프내 에지의 총 개수를 리턴
    public int E() {
        return E;
    }
 
    // // vertext 는 초기에 지정된 사이즈보다 크거나 0보다 작으면 안된다.
    private void validateVertex(int v) {
        if (v < 0 || v >= V)
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
    }
 
 
    // directed edge v→ w 를 그래프에 추가한다.
    public void addEdge(int v, int w) {
        validateVertex(v);
        validateVertex(w);
 
        // 무방향 그래프이니 역뱡향도 추가하였는데 방향그래프에서는 명확히 v -> w로 가는 에지만 추가한다.
        adj.get(v).add(w);
 
        // 그리고 v -> w 이므로 w 의 indegree를 +1 해준다.
        indegree[w]++;
 
        // 그래프내 에지의 총 개수도 +1 해준다.
        E++;
    }
 
    // 정점의 인접리스트를 리턴한다.
    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj.get(v);
    }
 
 
    // 정점으로 부터 나가는 에지의 개수(outdegree)를 리턴한다.
    public int outdegree(int v) {
        validateVertex(v);
        return adj.get(v).size();
    }
 
    // 정점으로 부터 들어오는 에지의 개수(indegree)를 리턴한다.
    public int indegree(int v) {
        validateVertex(v);
        return indegree[v];
    }
 
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " vertices, " + E + " edges " + NEWLINE);
        for (int v = 0; v < V; v++) {
            s.append(String.format("%d: ", v));
            for (int w : adj.get(v)) {
                s.append(String.format("%d ", w));
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }
 
 
}
 

 

인접행렬을 이용하여 구현

 
import java.util.Iterator;
import java.util.NoSuchElementException;
 
public class AdjMatrixDigraph {
 
    // 정점(vertex)의 총 개수.
    private int V;
 
    // 에지(edge)의 총 개수
    private int E;
 
    // 가중치가 없는 그래프라 boolean 으로 함.
    private boolean[][] adj;
    
    
    // 방향그래프내 있을 정점의 개수로 인접행렬을 초기화 한다.
    public AdjMatrixDigraph(int V) {
        if (V < 0) throw new IllegalArgumentException("Too few vertices");
        this.V = V;
        this.E = 0;
        // V * V 사이즈의 행렬(matrix)를 생성한다.
        this.adj = new boolean[V][V];
    }
 
 
    // 그래프내 정점의 총개 개수를 리턴.
    public int V() {
        return V;
    }
 
    // 그래프내 에지의 총 개수를 리턴.
    public int E() {
        return E;
    }
 
    // directed edge v→ w 를 그래프에 추가한다.
    public void addEdge(int v, int w) {
        if (!adj[v][w]) {
            // 그래프내 에지의 총 개수도 +1 해준다.
            E++;
        }
 
        // 무방향 그래프이니 역뱡향도 추가하였는데 방향그래프에서는 명확히 v -> w로 가는 에지만 추가한다.
        adj[v][w] = true;
    }
 
 
    // 정점 V와 인접한 리스트를 리턴한다.
    public Iterable<Integer> adj(int v) {
 
        return new AdjMatrixDigraph.AdjIterator(v);
    }
 
 
    private class AdjIterator implements Iterator<Integer>, Iterable<Integer> {
        private int v;
        private int w = 0;
 
        AdjIterator(int v) {
            this.v = v;
        }
 
        public Iterator<Integer> iterator() {
            return this;
        }
 
        public boolean hasNext() {
            while (w < V) {
                if (adj[v][w]) return true;
                w++;
            }
            return false;
        }
 
        public Integer next() {
            if (hasNext()) return w++;
            else           throw new NoSuchElementException();
        }
 
        public void remove() {
            throw new UnsupportedOperationException();
        }
    }
 
 
    // string representation of Graph - takes quadratic time
    public String toString() {
        String NEWLINE = System.getProperty("line.separator");
        StringBuilder s = new StringBuilder();
        s.append(V + " " + E + NEWLINE);
        for (int v = 0; v < V; v++) {
            s.append(v + ": ");
            for (int w : adj(v)) {
                s.append(w + " ");
            }
            s.append(NEWLINE);
        }
        return s.toString();
    }
}