그래프

그래프는 노드(정점)과 엣지(간선)으로 이루어진 집합이다.

무방향 그래프

무방향그래프란 노드의 방향없이 그려진 그래프로 양방향 그래프라고 하기도한다.
만약 입력이 (1,2)이면 1번노드와 2번노드를 연ㄴ결한 간선이 있다고 판단한다.

방향 그래프

방향 그래프란 간선의 방향이 있는 그래프이다.
입력이 (1,2)라면 1에서 2로 향하는 노선이 있음을 의미한다.

인접행렬

이러한 그래프를 표현하는 방법중 하나는 인접행렬이다. 인접행렬은 정점간 연결 여부를 행렬로 표현한 것으로 i 정점에서 j정점로 향하는 향하는 간선이 있다면 a_ij = 1로 표현한다.
무방향 그래프의 경우 양방향으로 연결되므로 a_ij = a_j1 의 특징을 갖는다.

장점

인접행렬은 adj[i][j]로 정점간 연결여부를 바로 조회하므로 O(1)의 시간복잡도를 가진다.

단점

단 .인접 행렬은 정점의 갯수가 100개이상으로 늘어날 경우, 특정 정점 i에 대해 연결된 정점을 조회할때 n번씩 순회가 필요하므로 O(n)의 시간복잡도를 가진다. 또한 n*n 인접행렬을 만들어야 하기때문에 차지하는 메모리의 양도 크다

인접리스트

그래프를 표현하는 방법중 다른 하나로 인접리스트가 있다. 인접리스트는 정점 별로 인접한 정점 ,즉 갈 수 있는 정점만 리스트로 저장하는 방법이다.

장점

아무리 정점의 갯수가 많더라도, i라는 정점에 대해 연결된 정점만 저장이 되므로 메모리가 절약된다. 또한 특정 정점 i에 대해 연결된 정점을 조회할때 인접 정점만 조회하면 되므로 O(e) [e= 인접 정점의 갯수] 의 시간복잡도를 가진다.

단점

정점간 인접여부, 예를들어 i와 j의 정점간 연결여부 조회할때 O(e) [e= 인접 정점의 갯수] 의 시간복잡도를 가진다.