[C] Graph, 그래프

A graph is a nonlinear data structure that expresses the relationship between objects, and expresses a many-to-many relationship. It should be noted that graphs in C language are different from the concepts of graphs in other languages ​​and commonly used. The graph is mainly represented by G and is defined as information of V and E like G=(V,E). V represents the relationship that is the target of the graph, that is, the vertex, and E represents the edge, which means the relationship between the vertices. Types of graphs can be classified into direction graphs and non-direction graphs depending on whether the edge has a direction or not. The non-directed graph is a graph that has no direction on the edge connecting the two vertices, and is expressed as (V1, V2), and the directional graph is <V1, V2> because accessibility between the vertices is limited due to the directionality of the edge. The path is a list of all the vertices encountered when going from the vertex V_i to V_j in order, and the number of edges at that time is called the path length.

그래프란객체 간의 관계를 표현하는 비선형 자료구조이며, 다 대 다의 관계를 표현한다. C 언어에서의 그래프는 다른 언어 및 일반적으로 사용하는 그래프의 개념과는 다름을 유의해야한다. 그래프는 주로 G 로 나타내며 G=(V,E) 와 같이 V 와 E의 정보로 정의된다. V 는 그래프로 표현의 대상이 되는 관계, 즉 정점을 의미하며 E는 정점 간의 관계를 의미하는 간선을 표현한다. 그래프의 종류는 간선이 방향을 가지느냐 아니냐에 따라 방향그래프와 무방향그래프로 분류할 수 있다. 무방향그래프는 두 정점을 연결하는 간선에 방향성이 없는 그래프로 (V1, V2) 와 같이 표현하며 방향그래프는 간선에 방향성이 존재하여 정점 간의 접근성이 제한되는 것으로 <V1, V2> 와 같이 표현한다. 경로란 정점 V_i 에서 V_j로 갈때 만나는 모든 정점들을 순서대로 나열한 리스트이며 그때의 간선 수를 경로 길이라고 한다.

There are two ways to implement a graph: an adjacency matrix method using a two-dimensional array and an adjacency list method using a linked list. This article introduces the adjacency matrix method. The adjacency matrix method constructs a n x n square matrix for the number of target vertices n, and allocates 1/0 by referring to the row and column indexes for the presence or absence of edges from V_i to V_j. Since the diagonal component means the vertex itself, it is always 0, and since the undirected graph has no direction, a symmetric matrix is created.

그래프를 구현하는 방법에는 2차원 배열을 사용한 인접행렬방법과 연결 리스트를 사용한 인접리스크방법이 있으며 이번 글에서는 인접행렬방법을 소개한다. 인접행렬방법은 대상 정점 수 n에 대해 n x n 정방행렬을 구성하여 V_i 에서 V_j로의 간선 유무를 각각 행과 열 인덱스를 참조하여 1/0을 할당한다. 대각 성분은 정점 자기자신을 의미하므로 항상 0이며 무방향 그래프는 방향성이 없으므로 대칭행렬을 만들게 된다.

Pictures related to the graph concept will be updated in the future.

먼 훗날 graph 개념과 관련된 그림들이 업데이트 될 예정임