The graph data structure is a set of nodes that have data and are connected to other nodes.
Let's try to understand this with an example. On facebook, everything is a node. This includes user, photo, album, event, group, page, comment, story, video, link, note... anything that has data is a node.
Each relation is an edge from one node to another. Whether you're posting a photo, joining a group such as a page, etc. A new edge is created for these relationships.
Then the whole facebook is a collection of nodes and edges. This is because facebook uses a graph data structure to store its data.
More precisely, graph is a data structure (V, E) that consists of:
- Vertex collection V.
- A set of edges E, represented as ordered pairs of vertices (u, v).
Count introduced
V = {0, 1, 2, 3}
E = {(0,1), (0,2), (0,3), (1,2)}
G = {V, E}
Terminology graph
Adjacency.
A vertex is said to be adjacent to another vertex if there is an edge connecting them.
Vertices 2 and 3 are not adjacent because there is no edge between them.Path.
The sequence of edges that allows you to go from vertex A to vertex B is called a path.
0-1, 1-2 and 0-2 are paths from node 0 to node 2.Oriented graph.
A graph that has an edge (u, v) does not necessarily mean that there is also an edge (v, u). Edges in such a graph are represented by arrows to show the direction of the edge.
Graph representation methods
Graphs are usually represented in two ways:
one. Adjacency matrix
Adjacency Matrix is a two-dimensional (2D) array of V x V vertices. Each row and column represents a vertex.
If the value of any element of a[i][j] is 1, this means that there is an edge connecting vertex i and vertex j.
The adjacency matrix for the graph we created above.
Since this is an undirected graph, for edge (0,2) we also need to mark edge (2,0), making the adjacency matrix symmetric about the diagonal.
Edge lookup (checking if there is an edge between vertex A and vertex B) is extremely fast in adjacency matrix representation, but we have to reserve space for every possible connection between all vertices (V x V), so it needs more space.
2. adjacency list
Adjacency List is a graph in the form of an array of linked list.
The array index represents a vertex, and each element in its linked list represents other vertices that form an edge with the vertex.
The adjacency list for the graph we created in the first example looks like this:
The adjacency list is storage efficient because we only need to store values for edges. For a graph with millions of vertices, this can mean a lot of space saved.
Operations on graphs
The most common graph operations are:
- Check if the element is present in the graph.
- Graph traversal.
- Add elements (vertices, edges) to the graph.
- Finding a path from one vertex to another.
