그래프와 인접 행렬

인접행렬을 가지고 그래프가 어떤 모양인지 파악한다.

✅ 무방향 그래프

✔️ 무방향 그래프 🟰 양방향 그래프

1번 노드와 2번 노드가 연결되어 있다.

예시
1번 도시와 2번 도시가 도로로 연결되어 있다.
그러니까 1번 도시, 2번 도시를 양방향으로 왔다갔다 할 수 있음.

✔️ input

5 5 //각각 노드 개수, 간선 개수
1 2 //간선 정보
1 3
2 4
3 4
2 5

✔️ 인접 행렬(2차원 배열)에 표현

• 인덱스 번호는 1에서 시작해서 노드 개수만큼 있을 것이다.
• 배열은 0으로 초기화되어 시작한다.
• 입력에 받은 input대로 배열의 행, 열을 1로 바꾼다. graph[a][b]=1;

• 그리고 무방향 그래프는 곧 양방향 그래프이므로 행, 열을 거꾸로 해서 열, 행도 1로 바꾼다. graph[b][a]=1;
  

• 1행이 누구랑 이어져있는지 확인하기 위해서는 1행을 쭉 돌면서 graph[1][i]의 값이 0이 아닌지 확인
• 0이 아니면 1이랑 연결된 노드인 것
• 1행을 쭉 가다보면 2, 3이 0이 아니므로 1번 노드는 2, 3번 노드와 연결된 것을 알 수 있다.

✅ 방향 그래프

방향 그래프는 1번 노드에서 2번으로는 갈 수 있지만, 2번 노드에서 1번으로는 갈 수가 없음.

✔️ input

5 5 //각각 노드 개수, 간선 개수
1 2 //간선 정보
1 3
3 4
4 2
2 5

✔️ 인접 행렬(2차원 배열)에 표현

• 마찬가지로 배열은 0으로 초기화되어 시작
• 입력에 받은 input대로 배열의 행, 열을 1로 바꾼다. graph[a][b]=1;
• 반대 방향은 갈 수 없는 방향이니 배열의 행, 열을 거꾸로 해서 넣는 작업은 없음 ❌
  
• 1행에서 갈 수 있는 노드를 확인하기 위해서는 1행을 쭉 돌면서 graph[1][i]의 값이 0이 아닌지 확인
• 0이 아니면 1에서 갈 수 있는 노드
• 1행을 쭉 가다보면 2가 0이 아니므로 1에서 2로 갈 수 있다.

✅ 가중치 방향 그래프

✔️ 가중치 방향 그래프

예시
1번 도시에서 2번 도시로 화물을 이동할 떄는 비용이 2만큼 든다.
1번 도시에서 2번 도시로 화물을 이동할 떄는 비용이 4만큼 든다.

✔️ input

5 5 //각각 노드 개수, 간선 개수
1 2 2 //간선 정보, 가중치 정보
1 3 4
3 4 5
4 2 2
2 5 5

✔️ 인접 행렬(2차원 배열)에 표현

• 마찬가지로 배열은 0으로 초기화되어 시작
• 입력에 받은 input대로 배열의 행, 열을 가중치 값 c로 바꾼다. graph[a][b]=c;
  
• 1행에서 갈 수 있는 노드를 확인하기 위해서는 1행을 쭉 돌면서 graph[1][i]의 값이 0이 아닌지 확인
• 0이 아니면 1에서 갈 수 있는 노드이고, 값 c가 가중치 값일 것이다.