릿코드(leetcode) 1일차 시작하기 - learn Graph

 Graph is probably the data structure that has the closest resemblance to our daily life. There are many types of graphs describing the relationships in real life. For instance, our friend circle is a huge “graph”.

Graph 는 아마도 우리 삶과 가장 근접한 data 구조이다. 현실 속에는 관계를 묘사하는 수많은 타입의 그래프가 있다. 예를 들어, 친구관계가 커다란 그래프이다.  

In Figure 1 above, we can see that person G, B, and E are all direct friends of A, while person C, D, and F are indirect friends of A. This example is a social graph of friendship. So, what is the “graph” data structure?

위의 1번 그림을 보면, G,B,E 는 A와 직접적인 친구이며, 반면에 C,D,F는 A와 직접적인 친구는 아니다. 이 그래프는 교우관계 그래프의 예시이다. 그럼 data 구조란 무엇일까

Types of “graphs”

그래프의 종류

There are many types of “graphs”. In this Explore Card, we will introduce three types of graphs: undirected graphs, directed graphs, and weighted graphs.

많은 종류의 그래프가 있다. 이번 챕터에서는 3종류의 그래프를 소개할 것이다.

undirected graphs, directed graphs, and weighted graphs

Undirected graphs

The edges between any two vertices in an “undirected graph” do not have a direction, indicating a two-way relationship.

Figure 1 is an example of an undirected graph.

'Undirected graphs'에서 두 개체 사이의 연결은 두 개체의 관계를 가르키는 방향이 없다.

그림 1 이 'Undirected graphs'의 예시이다.

Directed graphs

The edges between any two vertices in a “directed graph” graph are directional.

Figure 2 is an example of a directed graph.

'Directed graphs'의 개체들 사이의 연결은 뱡향성을 가진다

그림2가 'Directed graphs'의 예시이다.

Weighted graphs

Each edge in a “weighted graph” has an associated weight. The weight can be of any metric, such as time, distance, size, etc. The most commonly seen “weighted map” in our daily life might be a city map. In Figure 3, each edge is marked with the distance, which can be regarded as the weight of that edge.

'weighted graph'에서의 각각의 연결은 관련된 가중치를 갖는다. 가중치는 시간,거리, 사이드 증 어떠한 종류의 metric이 될 수 있다. 우리 삶에서 볼 수 있는 'weighted map'은 'city map'일 것이다. 그림3에서 각각의 연결에는 각 연결의 가중치와 연관된 거리가 적혀있다. 

The Definition of “graph” and Terminologies

'Graph'의 정의와 용어들

“Graph” is a non-linear data structure consisting of vertices and edges. There are a lot of terminologies to describe a graph. If you encounter an unfamiliar term in the following Explore Card, you may look up the definition below.

'Graph'는 vertices와 edges가 계속되는 비선형의 데이터구조이다. graph를 설명하기위해서는 수많은 용어가 있다. 만약 이번 챕터에서 익숙하지 않은 용어를 마주하게 된다면, 아래 정의에서 찾을 수 있다.