[그래프] 모든 정점의 indegree 계산

방향그래프(Directed Graph) 구현에서 보다시피 모든 정점의 indegree 를 계산하는 방법은 에지가 추가될 때마다 미리 계산되어질수 있다.

예를들어 v -> w 에지가 추가된다면 w 인덱스에  indegree 의 카운트를 하나 증가 (14번 라인) 시키면 된다.

// indegree[v] 는 정점 V의 incoming edge = indegree의 개수를 저장한다.
private int[] indegree;
 
...
 
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++;
    }
 

만약 미리 계산하지 않고 직접 계산한다면 인접리스트에서는 각 정점 v ∈ V 과 연결되 연결리스트들의 w ∈ W 를 조사하여

indegree[w]++ 해주면 각 정점에 들어오는 edge 의 카운트(degree)를 계산할 수 있다.

// 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들(edge)을 연결하기위한 자료구조.
private ArrayList<LinkedList<Integer>> adj;
 
// 방향그래프내 노드의 총 개수
private final int V;
 
.... 
  
public int[] indegrees() {
        int []indegree = new int[V];
        for(LinkedList<Integer> v : adj) {
            for(Integer w : v) {
                indegree[w]++;
            }
        }
        return indegree;
    }