In this chapter, you will learn about another nonlinear data structure called graph. This will be the last data structure we will cover before diving into sorting and searching algorithms.
This chapter will cover a considerable part of the wonderful applications of graphs. Since this is a vast topic, we could write a book like this just to dive into the amazing world of graph.
A graph is an abstract model of a network structure. A graph is a set of nodes (or vertices) connected by edges. Learning about graphs is important because any binary relationship can be represented by a graph.
Any social network, such as Facebook, Twitter, and Google plus, can be represented by a graph.
We can also use graphs to represent roads, flights, and communications, as shown in the following image:
Let's learn more about the mathematical and technical concepts of graphs.
A graph G = (V, E) is composed of:
- V: A set of vertices
- E: A set of edges connecting the vertices in V
The following diagram represents a graph:
Let's cover some graph terminology before we start implementing any algorithms.
Vertices connected by an edge are called adjacent vertices. For example, A and B are adjacent, A and D are adjacent, A and C are adjacent, and A and E are not adjacent.
A degree of a vertex consists of the number of adjacent vertices. For example, A is connected to other three vertices, therefore, A has degree 3; E is connected to other two vertices, therefore, E has degree 2.
A path is a sequence of consecutive vertices v1, v2, …, vk, where vi and vi+1 are adjacent. Using the graph from the previous diagram as an example, we have paths A B E I and A C D G, among others.
A simple path does not contain repeated vertices. As an example, we have the path A D G. A cycle is a simple path, except for the last vertex, which is the same as the first vertex: A D C A (back to A).
A graph is acyclic if it does not have cycles. A graph is connected if there is a path between every pair of vertices.
Graphs can be undirected (where edges do not have a direction) or directed (digraph), where edges have a direction, as demonstrated here:
A graph is strongly connected if there is a path in both directions between every pair of vertices. For example, C and D are strongly connected while A and B are not strongly connected.
Graphs can also be unweighted (as we have seen so far) or weighted, where the edges have weights, as shown in the following diagram:
We can solve many problems in the Computer Science world using graphs, such as searching a graph for a specific vertex or searching for a specific edge, finding a path in the graph (from one vertex to another), finding the shortest path between two vertices, and cycle detection.