[그래프] 무방향 그래프 표현 방식

무방향 그래프 (Undirected Graph)

1. Adjacency matrix (boolean array)

두 노드가 연결이 되어있으면 1, 연결이 되어있지않으면 0으로 표시하는 방법

	1	2	3	4	5
1	0	0	0	1	0
2	0	0	0	1	1
3	0	0	0	0	1
4	1	1	0	0	1
5	0	1	1	1	0

이걸 코딩으로 응용한다고 생각하면 2D boolean 배열을 생각해볼 수 있다.

다만, 이때 node 값을 조심해야한다. 그냥 0번 index를 버릴수도 있고 모든 index에 1을 빼는 방법도 있다.

개인적으로 iteration을 돌 때 오히려 헷갈리기 때문에 index에서 1을 빼는것을 더 선호하나 마지막 output에 신경을 써야한다.

boolean[][] graph = {{false, false, false, true, false},
                     {false, false, false, true, true},
                     {false, false, false, false, true},
                     {true, true, false, false, true},
                     {false, true, true, true, false}};

2. ArrayList 배열

1D 배열에서 각 node에 해당하는 index마다 ArrayList를 넣고, 안에 연결되어있는 node들을 넣는 법.

여기서도 node 값을 조심해야한다.

List<Integer> graph = new ArrayList<>[5];

3. Bitwise operation 응용 (int array)

위의 1번 adjacency matrix를 그대로 int로 바꿔서 배열로 저장하는 법.

00010 = 2,

00011 = 3;

00001 = 1,

11001 = 25,

01110 = 14 이니까..

int[] graph = {2, 3, 1, 25, 14};