Graph Algorithms - Part 0: Basic Concepts

    Introduction


    As  it turned out, the topic of algorithms is interesting to the Habra community. Therefore, as I promised, I will begin a series of reviews of "classical" algorithms on graphs.
    Since the audience on Habré is different, and the topic is interesting to many, I have to start from the zero part. In this part I will tell you what a graph is, how it is represented on a computer and why it is used. I apologize in advance to those who already know this all well, but in order to explain the algorithms on graphs, you must first explain what a graph is. No way without it.


    The basics


    In mathematics, a graph  is an abstract representation of many objects and the connections between them. A graph is a pair (V, E) where V is a set of  vertices , and E is a set of pairs, each of which is a connection (these pairs are called edges ).
    The graph may be oriented or  non-oriented . In a directed graph, the connections are directional (that is, the pairs in E are ordered, for example, the pairs (a, b) and (b, a) are two different connections). In turn, in an undirected graph, the connections are non-directional, and therefore if there is a connection (a, b) then it means that there is a connection (b, a).

    Fig.  1

    Example:
    Undirected Count: Neighborhood (in life). If (1) is neighbor (3), then (3) is neighbor (1). See pic. 1.a

    Oriented graph: Links. Site (1) can link to site (3), but it’s not at all necessary (although possible) that site (3) is linking to site (1). See pic. 1.b


    The degree of the vertex can be incoming and outgoing (for undirected graphs, the incoming degree is equal to the outgoing).
    The input degree of a vertex v is the number of edges of the form (i, v ), that is, the number of edges that “enter” into v.
    The outgoing degree of a vertex v is the number of edges of the form ( v , i), that is, the number of edges that “exit” from v.
    This is not a completely formal definition (a more formal definition through  incidence ), but it fully reflects the essence of the

    Wayin a graph, this is a finite sequence of vertices in which every two vertices in a row are connected by an edge. The path can be oriented or non-oriented depending on the graph. In Fig. 1.a, the path is, for example, the sequence [(1), (4), (5)] in Fig. 1.b, [(1), (3), (4), (5)].

    Graphs still have many different properties (for example, they can be connected, dicotyledonous, complete), but I will not describe all these properties now, but in the following parts we will need these concepts.

    Graph view


    There are two ways to represent a graph as adjacency lists and as an adjacency matrix. Both methods are suitable for representing oriented and non-oriented graphs.

    Adjacency matrix
    This method is convenient for representing  dense graphs in which the number of edges (| E |) is approximately equal to the number of vertices squared (| V | 2 ).
    In this view, we fill in a matrix of size | V | x | V | as follows:
    A [i] [j] = 1 (If there is an edge from i to j)
    A [i] [j] = 0 (Otherwise)
    This method is suitable for oriented and undirected graphs. For undirected graphs, the matrix A is symmetric (that is, A [i] [j] == A [j] [i], because if there is an edge between i and j, then it is also an edge from i to j, and edge from j to i). Thanks to this property, you can almost halve the memory usage by storing elements only in the upper part of the matrix, above the main diagonal)
    It is clear that with this presentation method, you can quickly check if there is an edge between the vertices v and u by simply looking at cell A [ v] [u].
    On the other hand, this method is very cumbersome, since it requires O (| V | 2 ) memory to store the matrix.

    Fig.  2
    In fig. 2 shows the representations of the graphs from Fig. 1 using adjacency matrices.

    Adjacency lists
    This presentation method is more suitable for sparse graphs, that is, graphs whose number of edges is much less than the number of vertices in the square (| E | << | V | 2 ).
    This view uses an Adj array containing | V | lists. Each list Adj [v] contains all the vertices of u, so there is an edge between v and u. The memory required for presentation is O (| E | + | V |) which is a better indicator than the adjacency matrix for sparse graphs.
    The main drawback of this presentation method is that there is no quick way to check if an edge (u, v) exists.


    Fig.  3
    In fig. Figure 3 shows the representations of the graphs in Fig. 1 using adjacency lists.

    Application

    Those who read to this place probably asked themselves a question, but where exactly can I use the graphs. As I promised, I will try to give examples. The very first example that comes to mind is a social network. The vertices of the graph are people, and the edges of the relationship (friendship). The graph can be disoriented, that is, I can only be friends with those who are friends with me. Or oriented (like for example in LiveJournal), where you can add a person as a friend, without him adding you. If he adds you, you will be “mutual friends”. That is, there will be two ribs: (He, You) and (You, He)
    Another application of the graph that I have already mentioned is the link from site to site. Suppose you want to make a search engine and want to consider which sites have more links (for example, site A), while taking into account how many sites link to site B, which links to site A. You will have an adjacency matrix for these links. You will want to introduce some sort of rating calculation system that does some calculations on this matrix, well, and then ... it's Google (more precisely, PageRank) =)

    Conclusion

    This is a small part of the theory that we need in order for the following parts. I hope you understood, and most importantly liked it and interested in reading further parts! Leave your feedback and suggestions in the comments.

    In the next part

    BFS - Width Search Algorithm

    Bibliography

    Kormen, Lizerson, Riverst, Stein - Algorithms. Construction and analysis. Williams Publishing House, 2007.
    Glossary of Graph Theory Terms.
    Count - Wikipedia

    article. This article is a cross-post from my blog - " Programming as is - notes by a programmer"

    ______________________
    The text is prepared in the Habr Editor

    Also popular now: