[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.

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.

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