그래프(Graph) 코드 구현 및 이해

우선 쌍방향(무방향) 그래프에 대해 알아보겠다.

1) ArrayList안에 ArrayList할당

그래프는 ArrayList중첩으로 표현이 가능하다.

그림으로는 아래에서 그림을 참고하면되고, 코드는 이런식이다.

ArrayList<ArrayList<Integer>> graph;

graph = new ArrayList<>();

for (int i = 0; i < N; i++) {
		graph.add(new ArrayList<>());
}

 

위과정은 ArrayList안에 ArrayList를 할당해주는 과정이다.

ArrayList안에 ArrayList를 또 집어넣기

위처럼 할당하면,

예를들어 graph.get(0)을 하면 0번째에 있는 ArrayList를 가져온다.

 

 

---

2) 바깥ArrayList Index=발신자 -----> 안쪽ArrayList Index=수신자

무방향그래프인경우 이렇게 서로 화살표가 가게끔,

이중for문으로 서로 쏴줘야된다.

for (int i = 0; i < N; i++) {
                for (int j = i + 1; j < M; j++) {
			graph.get(i).add(j);
                	graph.get(j).add(i);
                    }
                }
}

총 4쌍의 양방향그래프가 연결된다.

위의 연결된 노드들 연결한 간선을 종합해보면

그래프

이렇게 그래프 모양이 나온다.

 

 

단방향 그래프의 경우는 비대칭으로 이어주면 된다.