책너두 (코딩 인터뷰 완전분석) 15일차 (~161p, 829p)

메모

그래프

• 트리는 그래프의 한 종류임.
  • 모든 그래프가 트리는 아님.
  • 트리는 사이클이 없는 하나의 연결 그래프임.
• 그래프는 노드와 그 노드를 연결하는 간선을 하나로 모아놓은 것임.

• 그래프에는 방향성이 있을 수도 있고 없을 수도 있음.

• 그래프에는 여러 개의 고립된 부분 그래프(isolated subgraphs)로 구성될 수 있음.

  • 모든 정점 쌍간에 경로가 존재하는 그래프는 ‘연결 그래프’라고 부름.

• 그래프에는 사이클이 존재할 수도 있고, 존재하지 않을 수도 있음.

• 사이클이 없는 그래프는 ‘비순환 그래프’(acyclic graph) 라고 부름.

• 프로그래밍으로 그래프를 표현할 때 일반적으로 다음 두 가지 방법을 사용함.

인접 리스트 (adjacency list)

• 그래프를 표현하는 가장 일반적인 방법
• 모든 정점을 인접 리스트에 저장함.
  • 무방향 그래프에서 (a, b) 간선은 두 번 저장됨.
  • a 정점에서 인접한 간선 저장 / b 정점에서 인접한 간선

class Graph {
    public Node[] nodes;
}

class Node {
    public String name;
    public Node[] children;
}

• 그래프에서 노드를 정의하는 간단한 클래스는 트리의 노드 클래스와 궁극적으로 같아보임.
• 트리에서는 특정 노드 하나(루트 노드)에서 다른 모든 노드로 접근이 가능했음.
  • 그래프는 트리와 달리 특정 노드에서 다른 모든 노드로 접근이 가능하지 않음.
  • 그래서 Graph 클래스를 만들어서, 모든 노드에 대한 내용을 담도록 한다.
• 그래프를 표현하기 위해 배열(or 해시 테이블)과 배열의 각 인덱스마다 존재하는 또 다른 리스트(ex : 배열, 동적 가변 크기 배열, 연결리스트)를 이용하여 인접 리스트를 표현할 수 있음.

인접 행렬

• NxN 불린 행렬로써 matrix[i][j] 가 true 라면 i에서 j로의 간선이 있다는 뜻임.
  • boolean 이 아닌, 정수 행렬을 사용할 수도 있음.
  • N은 노드의 개수를 의미함.
• 무방향 그래프를 인접행렬로 표현하면 대칭 행렬이 됨.
  • 방향 그래프는 대칭 행렬이 안 될 수도 있음.