Graph Basics

Graph basics

Vertex and Edge

우선 Graph(이하 그래프.)는 V E의 쌍입니다. 여기서 V는 vertex set을 가리키고. E는 edge의 set을 가리킵니다. 우리나라 말로는 vertex 정점, edge 간선 이라고 할 수 있습니다.

또한 일부에선 vertex는 node라고 불리기도 하고 edge는 link라고 불리기도 합니다. Tree에서의 node라고 생각하면 편하겠습니다.

Directed graph, Undirected graph

Directed Graph는 우리나라 말로 유향그래프라고 하며, 유향 그래프는 유향 엣지(directed edge)를 사용한 그래프를 말합니다.

각각의 엣지들은 화살표로 표현되며 어떤 vertex에서 "다른" vertex로 들어가거나 "자기 자신" vertex로 들어갑니다.

어떤 vertex u에서 떠나 어떤 vertex v로 들어갔다면 (u, v)라고 쓰고, 우리는 incident from u 그리고 incident to v. 라고 합니다.

각각의 엣지는 "들어가고" "나오는" 순서가 있는 vertex의 쌍으로 식별될 수 있습니다.

예를 들어 V = {\{1,2,3,4,5,6\}} 이라고 하면

E= \{ (1,2),(2,2),(2,4),(2,5),(4.1),(4.5),(5.4),(6,3) \} 라고 쓸수 있고 이를 그래프로 그리면 아래와 같습니다.

Undirected Graph는 우리나라 말로 무향그래프 라고 하며, 무향 엣지를 가지고 있습니다.

이 무향 엣지는 이름 그대로 방향이 없으며, 단순히 선으로 표현합니다. Directed Graph와는 다르게 자신으로 되돌아 들어가는 엣지가 존재하지 않습니다.

따라서 (u,v)와 (v,u)가 똑같습니다. e.g. \space (2,4) = (4,2)

vertex 2에서 나와 다른 vertex 4로 들어갔다면 incident on vertices 2 and 4. 라고 표현합니다.

Adjacency

Adjacency는 인접해있는지를 나타냅니다. 만약 엣지가 (u, v)로 표현된다면, vertex v는 vertex u와 인접해 있다고 합니다.

Undirected Graph 일 때, u랑 v랑 엣지로 연결되어 있다면 그 둘은 서로 인접합니다.
(u는 v에 인접하고, v는 u에 인접합니다.)

하지만 Directed Graph일 때, (u, v)일 때, 즉 u에서 엣지가 나와 v로 들어갈 때 vertex u는 vertex v에 인접해 있다고 할 수 있습니다. 하지만 vertex v는 vertex u에 인접하다고 할 수 없습니다.

Adjacency를 리스트(list)로 표현할 수 있으며, 행렬(Matrix)로 표현 할 수 있습니다.

Adjacency-list representation

Adjacency-matrix representation

Adjacency-list representation

[사진출처] : Medium, Data Structure

위와같이 Directed Graph를 리스트로 표현할 수 있습니다. 또한 Undirected Graph는 아래와 같이 리스트로 표현할 수 있습니다.

Undirected Graph는 O(V+E)의 공간 복잡도(Space complexity)를 갖습니다.

Adjacency-matrix representation

행렬로 표현하는 방법은 |vertex| x |vertex|의 행렬의 크기를 갖기 때문에 O(V^2)의 공간복잡도를 갖습니다. 행렬에 0은 엣지가 존재하지 않음을 1은 엣지가 존재함을 나타냅니다.

Undirected Graph도 directed Graph와 같이 유사하게 나타납니다. 하지만 Undirected graph는 행렬의 주대각선을 기준으로 대칭이지만 directed graph는 행렬의 주대각선을 기준으로 대칭이지 않습니다. 때문에 Undirected Graph와 같은 경우에는 주대각선을 기준으로 아래만 표현하기도 합니다.

Comparison of adjacency list and adjacency matrix

용량적인 측면에서
그래프가 작은 경우. adjacency list가 더 좋습니다.
왜냐하면 |E| < |V|^2 이므로 O(V+E) < O(V^2)이기 때문입니다.

그래프가 조밀하다면, adjacency matrix가 더 좋습니다.
왜냐하면 adjacency matrix 는 오직 1개의 엣지당 하나의 비트만 차지하기 때문입니다.

만약 Does and edge (i, j) exist? 라고 묻는다면,

Adjacency matrix : O(1) time.

Adjacency list : O(V) time.

라고 대답할 수 있습니다.

하지만 모든 엣지를 listing or visiting 한다면 이야기가 다릅니다.

Adjacency matrix : O(V^2) time.

Adjacency list : O(V+E) time.

알고리즘으로 돌아가기

Algorithm

메인으로 돌아가기

Graph basics

Vertex and Edge

우선 Graph(이하 그래프.)는 V E의 쌍입니다. 여기서 V는 vertex set을 가리키고. E는 edge의 set을 가리킵니다. 우리나라 말로는 vertex 정점, edge 간선 이라고 할 수 있습니다.

또한 일부에선 vertex는 node라고 불리기도 하고 edge는 link라고 불리기도 합니다. Tree에서의 node라고 생각하면 편하겠습니다.

Directed graph, Undirected graph

Directed Graph는 우리나라 말로 유향그래프라고 하며, 유향 그래프는 유향 엣지(directed edge)를 사용한 그래프를 말합니다.

각각의 엣지들은 화살표로 표현되며 어떤 vertex에서 "다른" vertex로 들어가거나 "자기 자신" vertex로 들어갑니다.

어떤 vertex u에서 떠나 어떤 vertex v로 들어갔다면 (u, v)라고 쓰고, 우리는 incident from u 그리고 incident to v. 라고 합니다.

각각의 엣지는 "들어가고" "나오는" 순서가 있는 vertex의 쌍으로 식별될 수 있습니다.

예를 들어 V = {\{1,2,3,4,5,6\}} 이라고 하면

E= \{ (1,2),(2,2),(2,4),(2,5),(4.1),(4.5),(5.4),(6,3) \} 라고 쓸수 있고 이를 그래프로 그리면 아래와 같습니다.

Undirected Graph는 우리나라 말로 무향그래프 라고 하며, 무향 엣지를 가지고 있습니다.

이 무향 엣지는 이름 그대로 방향이 없으며, 단순히 선으로 표현합니다. Directed Graph와는 다르게 자신으로 되돌아 들어가는 엣지가 존재하지 않습니다.

따라서 (u,v)와 (v,u)가 똑같습니다. e.g. \space (2,4) = (4,2)

vertex 2에서 나와 다른 vertex 4로 들어갔다면 incident on vertices 2 and 4. 라고 표현합니다.

Adjacency

Adjacency는 인접해있는지를 나타냅니다. 만약 엣지가 (u, v)로 표현된다면, vertex v는 vertex u와 인접해 있다고 합니다.

Undirected Graph 일 때, u랑 v랑 엣지로 연결되어 있다면 그 둘은 서로 인접합니다.
(u는 v에 인접하고, v는 u에 인접합니다.)

하지만 Directed Graph일 때, (u, v)일 때, 즉 u에서 엣지가 나와 v로 들어갈 때 vertex u는 vertex v에 인접해 있다고 할 수 있습니다. 하지만 vertex v는 vertex u에 인접하다고 할 수 없습니다.

Adjacency를 리스트(list)로 표현할 수 있으며, 행렬(Matrix)로 표현 할 수 있습니다.

Adjacency-list representation

Adjacency-matrix representation

Adjacency-list representation

[사진출처] : Medium, Data Structure

위와같이 Directed Graph를 리스트로 표현할 수 있습니다. 또한 Undirected Graph는 아래와 같이 리스트로 표현할 수 있습니다.

Undirected Graph는 O(V+E)의 공간 복잡도(Space complexity)를 갖습니다.

Adjacency-matrix representation

행렬로 표현하는 방법은 |vertex| x |vertex|의 행렬의 크기를 갖기 때문에 O(V^2)의 공간복잡도를 갖습니다. 행렬에 0은 엣지가 존재하지 않음을 1은 엣지가 존재함을 나타냅니다.

Undirected Graph도 directed Graph와 같이 유사하게 나타납니다. 하지만 Undirected graph는 행렬의 주대각선을 기준으로 대칭이지만 directed graph는 행렬의 주대각선을 기준으로 대칭이지 않습니다. 때문에 Undirected Graph와 같은 경우에는 주대각선을 기준으로 아래만 표현하기도 합니다.

Comparison of adjacency list and adjacency matrix

용량적인 측면에서
그래프가 작은 경우. adjacency list가 더 좋습니다.
왜냐하면 |E| < |V|^2 이므로 O(V+E) < O(V^2)이기 때문입니다.

그래프가 조밀하다면, adjacency matrix가 더 좋습니다.
왜냐하면 adjacency matrix 는 오직 1개의 엣지당 하나의 비트만 차지하기 때문입니다.

만약 Does and edge (i, j) exist? 라고 묻는다면,

Adjacency matrix : O(1) time.

Adjacency list : O(V) time.

라고 대답할 수 있습니다.

하지만 모든 엣지를 listing or visiting 한다면 이야기가 다릅니다.

Adjacency matrix : O(V^2) time.

Adjacency list : O(V+E) time.

알고리즘으로 돌아가기

Algorithm

메인으로 돌아가기

Graph basics

Vertex and Edge

우선 Graph(이하 그래프.)는 V E의 쌍입니다. 여기서 V는 vertex set을 가리키고. E는 edge의 set을 가리킵니다. 우리나라 말로는 vertex 정점, edge 간선 이라고 할 수 있습니다.

또한 일부에선 vertex는 node라고 불리기도 하고 edge는 link라고 불리기도 합니다. Tree에서의 node라고 생각하면 편하겠습니다.

Directed graph, Undirected graph

Directed Graph는 우리나라 말로 유향그래프라고 하며, 유향 그래프는 유향 엣지(directed edge)를 사용한 그래프를 말합니다.

각각의 엣지들은 화살표로 표현되며 어떤 vertex에서 "다른" vertex로 들어가거나 "자기 자신" vertex로 들어갑니다.

어떤 vertex u에서 떠나 어떤 vertex v로 들어갔다면 (u, v)라고 쓰고, 우리는 incident from u 그리고 incident to v. 라고 합니다.

각각의 엣지는 "들어가고" "나오는" 순서가 있는 vertex의 쌍으로 식별될 수 있습니다.

예를 들어 V = {\{1,2,3,4,5,6\}} 이라고 하면

E= \{ (1,2),(2,2),(2,4),(2,5),(4.1),(4.5),(5.4),(6,3) \} 라고 쓸수 있고 이를 그래프로 그리면 아래와 같습니다.

Undirected Graph는 우리나라 말로 무향그래프 라고 하며, 무향 엣지를 가지고 있습니다.

이 무향 엣지는 이름 그대로 방향이 없으며, 단순히 선으로 표현합니다. Directed Graph와는 다르게 자신으로 되돌아 들어가는 엣지가 존재하지 않습니다.

따라서 (u,v)와 (v,u)가 똑같습니다. e.g. \space (2,4) = (4,2)

vertex 2에서 나와 다른 vertex 4로 들어갔다면 incident on vertices 2 and 4. 라고 표현합니다.

Adjacency

Adjacency는 인접해있는지를 나타냅니다. 만약 엣지가 (u, v)로 표현된다면, vertex v는 vertex u와 인접해 있다고 합니다.

Undirected Graph 일 때, u랑 v랑 엣지로 연결되어 있다면 그 둘은 서로 인접합니다.
(u는 v에 인접하고, v는 u에 인접합니다.)

하지만 Directed Graph일 때, (u, v)일 때, 즉 u에서 엣지가 나와 v로 들어갈 때 vertex u는 vertex v에 인접해 있다고 할 수 있습니다. 하지만 vertex v는 vertex u에 인접하다고 할 수 없습니다.

Adjacency를 리스트(list)로 표현할 수 있으며, 행렬(Matrix)로 표현 할 수 있습니다.

Adjacency-list representation

Adjacency-matrix representation

Adjacency-list representation

[사진출처] : Medium, Data Structure

위와같이 Directed Graph를 리스트로 표현할 수 있습니다. 또한 Undirected Graph는 아래와 같이 리스트로 표현할 수 있습니다.

Undirected Graph는 O(V+E)의 공간 복잡도(Space complexity)를 갖습니다.

Adjacency-matrix representation

행렬로 표현하는 방법은 |vertex| x |vertex|의 행렬의 크기를 갖기 때문에 O(V^2)의 공간복잡도를 갖습니다. 행렬에 0은 엣지가 존재하지 않음을 1은 엣지가 존재함을 나타냅니다.

Undirected Graph도 directed Graph와 같이 유사하게 나타납니다. 하지만 Undirected graph는 행렬의 주대각선을 기준으로 대칭이지만 directed graph는 행렬의 주대각선을 기준으로 대칭이지 않습니다. 때문에 Undirected Graph와 같은 경우에는 주대각선을 기준으로 아래만 표현하기도 합니다.

Comparison of adjacency list and adjacency matrix

용량적인 측면에서
그래프가 작은 경우. adjacency list가 더 좋습니다.
왜냐하면 |E| < |V|^2 이므로 O(V+E) < O(V^2)이기 때문입니다.

그래프가 조밀하다면, adjacency matrix가 더 좋습니다.
왜냐하면 adjacency matrix 는 오직 1개의 엣지당 하나의 비트만 차지하기 때문입니다.

만약 Does and edge (i, j) exist? 라고 묻는다면,

Adjacency matrix : O(1) time.

Adjacency list : O(V) time.

라고 대답할 수 있습니다.

하지만 모든 엣지를 listing or visiting 한다면 이야기가 다릅니다.

Adjacency matrix : O(V^2) time.

Adjacency list : O(V+E) time.

알고리즘으로 돌아가기

Algorithm

메인으로 돌아가기

Graph basics

Vertex and Edge

우선 Graph(이하 그래프.)는 V E의 쌍입니다. 여기서 V는 vertex set을 가리키고. E는 edge의 set을 가리킵니다. 우리나라 말로는 vertex 정점, edge 간선 이라고 할 수 있습니다.

또한 일부에선 vertex는 node라고 불리기도 하고 edge는 link라고 불리기도 합니다. Tree에서의 node라고 생각하면 편하겠습니다.

Directed graph, Undirected graph

Directed Graph는 우리나라 말로 유향그래프라고 하며, 유향 그래프는 유향 엣지(directed edge)를 사용한 그래프를 말합니다.

각각의 엣지들은 화살표로 표현되며 어떤 vertex에서 "다른" vertex로 들어가거나 "자기 자신" vertex로 들어갑니다.

어떤 vertex u에서 떠나 어떤 vertex v로 들어갔다면 (u, v)라고 쓰고, 우리는 incident from u 그리고 incident to v. 라고 합니다.

각각의 엣지는 "들어가고" "나오는" 순서가 있는 vertex의 쌍으로 식별될 수 있습니다.

예를 들어 V = {\{1,2,3,4,5,6\}} 이라고 하면

E= \{ (1,2),(2,2),(2,4),(2,5),(4.1),(4.5),(5.4),(6,3) \} 라고 쓸수 있고 이를 그래프로 그리면 아래와 같습니다.

Undirected Graph는 우리나라 말로 무향그래프 라고 하며, 무향 엣지를 가지고 있습니다.

이 무향 엣지는 이름 그대로 방향이 없으며, 단순히 선으로 표현합니다. Directed Graph와는 다르게 자신으로 되돌아 들어가는 엣지가 존재하지 않습니다.

따라서 (u,v)와 (v,u)가 똑같습니다. e.g. \space (2,4) = (4,2)

vertex 2에서 나와 다른 vertex 4로 들어갔다면 incident on vertices 2 and 4. 라고 표현합니다.

Adjacency

Adjacency는 인접해있는지를 나타냅니다. 만약 엣지가 (u, v)로 표현된다면, vertex v는 vertex u와 인접해 있다고 합니다.

Undirected Graph 일 때, u랑 v랑 엣지로 연결되어 있다면 그 둘은 서로 인접합니다.
(u는 v에 인접하고, v는 u에 인접합니다.)

하지만 Directed Graph일 때, (u, v)일 때, 즉 u에서 엣지가 나와 v로 들어갈 때 vertex u는 vertex v에 인접해 있다고 할 수 있습니다. 하지만 vertex v는 vertex u에 인접하다고 할 수 없습니다.

Adjacency를 리스트(list)로 표현할 수 있으며, 행렬(Matrix)로 표현 할 수 있습니다.

Adjacency-list representation

Adjacency-matrix representation

Adjacency-list representation

[사진출처] : Medium, Data Structure

위와같이 Directed Graph를 리스트로 표현할 수 있습니다. 또한 Undirected Graph는 아래와 같이 리스트로 표현할 수 있습니다.

Undirected Graph는 O(V+E)의 공간 복잡도(Space complexity)를 갖습니다.

Adjacency-matrix representation

행렬로 표현하는 방법은 |vertex| x |vertex|의 행렬의 크기를 갖기 때문에 O(V^2)의 공간복잡도를 갖습니다. 행렬에 0은 엣지가 존재하지 않음을 1은 엣지가 존재함을 나타냅니다.

Undirected Graph도 directed Graph와 같이 유사하게 나타납니다. 하지만 Undirected graph는 행렬의 주대각선을 기준으로 대칭이지만 directed graph는 행렬의 주대각선을 기준으로 대칭이지 않습니다. 때문에 Undirected Graph와 같은 경우에는 주대각선을 기준으로 아래만 표현하기도 합니다.

Comparison of adjacency list and adjacency matrix

용량적인 측면에서
그래프가 작은 경우. adjacency list가 더 좋습니다.
왜냐하면 |E| < |V|^2 이므로 O(V+E) < O(V^2)이기 때문입니다.

그래프가 조밀하다면, adjacency matrix가 더 좋습니다.
왜냐하면 adjacency matrix 는 오직 1개의 엣지당 하나의 비트만 차지하기 때문입니다.

만약 Does and edge (i, j) exist? 라고 묻는다면,

Adjacency matrix : O(1) time.

Adjacency list : O(V) time.

라고 대답할 수 있습니다.

하지만 모든 엣지를 listing or visiting 한다면 이야기가 다릅니다.

Adjacency matrix : O(V^2) time.

Adjacency list : O(V+E) time.

알고리즘으로 돌아가기

Algorithm

메인으로 돌아가기

Graph basics

Vertex and Edge

우선 Graph(이하 그래프.)는 V E의 쌍입니다. 여기서 V는 vertex set을 가리키고. E는 edge의 set을 가리킵니다. 우리나라 말로는 vertex 정점, edge 간선 이라고 할 수 있습니다.

또한 일부에선 vertex는 node라고 불리기도 하고 edge는 link라고 불리기도 합니다. Tree에서의 node라고 생각하면 편하겠습니다.

Directed graph, Undirected graph

Directed Graph는 우리나라 말로 유향그래프라고 하며, 유향 그래프는 유향 엣지(directed edge)를 사용한 그래프를 말합니다.

각각의 엣지들은 화살표로 표현되며 어떤 vertex에서 "다른" vertex로 들어가거나 "자기 자신" vertex로 들어갑니다.

어떤 vertex u에서 떠나 어떤 vertex v로 들어갔다면 (u, v)라고 쓰고, 우리는 incident from u 그리고 incident to v. 라고 합니다.

각각의 엣지는 "들어가고" "나오는" 순서가 있는 vertex의 쌍으로 식별될 수 있습니다.

예를 들어 V = {\{1,2,3,4,5,6\}} 이라고 하면

E= \{ (1,2),(2,2),(2,4),(2,5),(4.1),(4.5),(5.4),(6,3) \} 라고 쓸수 있고 이를 그래프로 그리면 아래와 같습니다.

Undirected Graph는 우리나라 말로 무향그래프 라고 하며, 무향 엣지를 가지고 있습니다.

이 무향 엣지는 이름 그대로 방향이 없으며, 단순히 선으로 표현합니다. Directed Graph와는 다르게 자신으로 되돌아 들어가는 엣지가 존재하지 않습니다.

따라서 (u,v)와 (v,u)가 똑같습니다. e.g. \space (2,4) = (4,2)

vertex 2에서 나와 다른 vertex 4로 들어갔다면 incident on vertices 2 and 4. 라고 표현합니다.

Adjacency

Adjacency는 인접해있는지를 나타냅니다. 만약 엣지가 (u, v)로 표현된다면, vertex v는 vertex u와 인접해 있다고 합니다.

Undirected Graph 일 때, u랑 v랑 엣지로 연결되어 있다면 그 둘은 서로 인접합니다.
(u는 v에 인접하고, v는 u에 인접합니다.)

하지만 Directed Graph일 때, (u, v)일 때, 즉 u에서 엣지가 나와 v로 들어갈 때 vertex u는 vertex v에 인접해 있다고 할 수 있습니다. 하지만 vertex v는 vertex u에 인접하다고 할 수 없습니다.

Adjacency를 리스트(list)로 표현할 수 있으며, 행렬(Matrix)로 표현 할 수 있습니다.

Adjacency-list representation

Adjacency-matrix representation

Adjacency-list representation

[사진출처] : Medium, Data Structure

위와같이 Directed Graph를 리스트로 표현할 수 있습니다. 또한 Undirected Graph는 아래와 같이 리스트로 표현할 수 있습니다.

Undirected Graph는 O(V+E)의 공간 복잡도(Space complexity)를 갖습니다.

Adjacency-matrix representation

행렬로 표현하는 방법은 |vertex| x |vertex|의 행렬의 크기를 갖기 때문에 O(V^2)의 공간복잡도를 갖습니다. 행렬에 0은 엣지가 존재하지 않음을 1은 엣지가 존재함을 나타냅니다.

Undirected Graph도 directed Graph와 같이 유사하게 나타납니다. 하지만 Undirected graph는 행렬의 주대각선을 기준으로 대칭이지만 directed graph는 행렬의 주대각선을 기준으로 대칭이지 않습니다. 때문에 Undirected Graph와 같은 경우에는 주대각선을 기준으로 아래만 표현하기도 합니다.

Comparison of adjacency list and adjacency matrix

용량적인 측면에서
그래프가 작은 경우. adjacency list가 더 좋습니다.
왜냐하면 |E| < |V|^2 이므로 O(V+E) < O(V^2)이기 때문입니다.

그래프가 조밀하다면, adjacency matrix가 더 좋습니다.
왜냐하면 adjacency matrix 는 오직 1개의 엣지당 하나의 비트만 차지하기 때문입니다.

만약 Does and edge (i, j) exist? 라고 묻는다면,

Adjacency matrix : O(1) time.

Adjacency list : O(V) time.

라고 대답할 수 있습니다.

하지만 모든 엣지를 listing or visiting 한다면 이야기가 다릅니다.

Adjacency matrix : O(V^2) time.

Adjacency list : O(V+E) time.

알고리즘으로 돌아가기

Algorithm

메인으로 돌아가기

Graph basics

Vertex and Edge

우선 Graph(이하 그래프.)는 V E의 쌍입니다. 여기서 V는 vertex set을 가리키고. E는 edge의 set을 가리킵니다. 우리나라 말로는 vertex 정점, edge 간선 이라고 할 수 있습니다.

또한 일부에선 vertex는 node라고 불리기도 하고 edge는 link라고 불리기도 합니다. Tree에서의 node라고 생각하면 편하겠습니다.

Directed graph, Undirected graph

Directed Graph는 우리나라 말로 유향그래프라고 하며, 유향 그래프는 유향 엣지(directed edge)를 사용한 그래프를 말합니다.

각각의 엣지들은 화살표로 표현되며 어떤 vertex에서 "다른" vertex로 들어가거나 "자기 자신" vertex로 들어갑니다.

어떤 vertex u에서 떠나 어떤 vertex v로 들어갔다면 (u, v)라고 쓰고, 우리는 incident from u 그리고 incident to v. 라고 합니다.

각각의 엣지는 "들어가고" "나오는" 순서가 있는 vertex의 쌍으로 식별될 수 있습니다.

예를 들어 V = {\{1,2,3,4,5,6\}} 이라고 하면

E= \{ (1,2),(2,2),(2,4),(2,5),(4.1),(4.5),(5.4),(6,3) \} 라고 쓸수 있고 이를 그래프로 그리면 아래와 같습니다.

Undirected Graph는 우리나라 말로 무향그래프 라고 하며, 무향 엣지를 가지고 있습니다.

이 무향 엣지는 이름 그대로 방향이 없으며, 단순히 선으로 표현합니다. Directed Graph와는 다르게 자신으로 되돌아 들어가는 엣지가 존재하지 않습니다.

따라서 (u,v)와 (v,u)가 똑같습니다. e.g. \space (2,4) = (4,2)

vertex 2에서 나와 다른 vertex 4로 들어갔다면 incident on vertices 2 and 4. 라고 표현합니다.

Adjacency

Adjacency는 인접해있는지를 나타냅니다. 만약 엣지가 (u, v)로 표현된다면, vertex v는 vertex u와 인접해 있다고 합니다.

Undirected Graph 일 때, u랑 v랑 엣지로 연결되어 있다면 그 둘은 서로 인접합니다.
(u는 v에 인접하고, v는 u에 인접합니다.)

하지만 Directed Graph일 때, (u, v)일 때, 즉 u에서 엣지가 나와 v로 들어갈 때 vertex u는 vertex v에 인접해 있다고 할 수 있습니다. 하지만 vertex v는 vertex u에 인접하다고 할 수 없습니다.

Adjacency를 리스트(list)로 표현할 수 있으며, 행렬(Matrix)로 표현 할 수 있습니다.

Adjacency-list representation

Adjacency-matrix representation

Adjacency-list representation

[사진출처] : Medium, Data Structure

위와같이 Directed Graph를 리스트로 표현할 수 있습니다. 또한 Undirected Graph는 아래와 같이 리스트로 표현할 수 있습니다.

Undirected Graph는 O(V+E)의 공간 복잡도(Space complexity)를 갖습니다.

Adjacency-matrix representation

행렬로 표현하는 방법은 |vertex| x |vertex|의 행렬의 크기를 갖기 때문에 O(V^2)의 공간복잡도를 갖습니다. 행렬에 0은 엣지가 존재하지 않음을 1은 엣지가 존재함을 나타냅니다.