What is the figure
- A graph is an abstract model of a network structure.
- A graph is a set of nodes (or vertices) connected by edges.
Since any binary relation can be represented by a graph, it is particularly important to learn the graph.
The mathematical and technical concepts of graphs
A graph G = (V, E) consists of the following elements.
- V: a set of vertices.
- E: a set of edges connecting vertices in V.
Terms related to graphs
- Adjacent vertices: vertices joined together by an edge. In the figure above, A and B are adjacent, A and D are adjacent, A and
C is adjacent, A and E are not adjacent.
- Degree: The degree of a vertex is the number of adjacent vertices. In the figure above, A is connected to three other vertices, so its degree is 3; E
It’s connected to two other vertices, so E has a degree of 2.
- Path: vertices v1, v2… , a continuous sequence of vk, where vi and vi+1 are adjacent. In the figure above, there are paths A, B, E, I and A, C, D, G.
- Simple paths require that there be no duplicate verticesFor example, A, D, and G in the figure above are simple paths.
- A ring is also a simple pathBecause the last vertex of the ring is the same vertex as the first vertex. For example, the A, D, C, A rings in the figure above.
- A graph is acyclic if there are no rings in it.
- A graph is connected if there are paths between every two vertices.
The types of figure
- Directed graph: means that the edges of a graph have directions.
- Undirected graph: is when the edges of a graph have no direction.
The graph can also be unweighted or weighted. As shown in the figure below, the edges of the weighted graph are given weights.
The representation of figure
From a data structure perspective, there are several ways to represent graphs. In all representations, there is no infallible way. The correct representation of a graph depends on the problem to be solved and the type of graph.
- Adjacency matrixThe most common implementation of graphs is adjacency matrices. Each node is associated with an integer that acts as an index to the array. We use a two-dimensional array to represent the connections between vertices. If the node whose index is I is adjacent to the node whose index is j, array[I][j] === 1; otherwise array[I][j] === 0
If a graph that is not strongly connected (sparse graph) is represented by an adjacency matrix, the matrix will have a lot of zeros, which means we waste computer storage to represent edges that don’t exist at all. For example, to find adjacent vertices of a given vertex, even if the vertex has only one adjacent vertex, we have to iterate over an entire row. Another reason the adjacency matrix representation is not good enough is that the number of vertices in the graph can change, and two-dimensional arrays are less flexible.
- Adjacency listWe can also use a dynamic data structure called an adjacency list to represent graphs. The adjacency list consists of a list of adjacent vertices for each vertex in the graph. There are several ways to represent this data structure. We can use lists (arrays), linked lists, or even hash tables or dictionaries to represent lists of adjacent vertices.
Although an adjacency list is probably a better choice for most problems, both of these representations are useful and have different properties (for example, it is faster to use an adjacency matrix to find out whether vertices V and W are adjacent).
- Incidence matrices: Graphs can also be represented by incidence matrices. In an association matrix, the rows of the matrix represent vertices and the columns represent edges. As shown in the figure below, a two-dimensional array is used to represent the connectivity between the two. If vertex V is the incident point of edge E, array[v][e] === 1; Otherwise, array[v][e] === 0.
The incidence matrix is usually used when there are more edges than vertices to save space and memory.