A graph is a generalization of a tree. In a tree, every node has one parent. In a graph, a node can have multiple parents. The most common way to think about a graph is as a set of vertices and edges. Vertices are like points and edges are like lines that connect the points. In the generic notion of a graph, there is no restriction on which vertices can be connected by edges. This allows graphs to model a versatile category of real-life concepts. The Internet, for example, is a graph where the vertices are the web pages and the edges the hyperlinks between the pages. A social networking site, such as Facebook, has a graph of profiles in which the vertices are the profiles and the edges the friendships between the profiles. Each software has a graph of dependencies, called a dependency graph, in which the vertices are the different software libraries used and the edges the dependencies between the software libraries. There is no end to examples of graphs. In this chapter, we will discuss the following topics:

What is a graph?

A graph is a collection of vertices and edges that connect the vertices. Figure 1 gives a visual representation of an example of a graph. There are a few features to note here, which we will discuss next:

Figure 1: Example of an undirected graph

• Undirected graph: An undirected graph is a graph in which the edges have no direction, as shown in Figure 1.
• Directed graph: This is a graph in which the edges have a direction.
• Path: A path is a sequence of edges that connects a set of vertices that are distinct from one another, except the first and the last vertices as they may be the same. For example, in Figure 1, the edges AB, BD, and DE represent a path. It can also be described as the ABDE path, which does not repeat its vertices. In the case of a directed graph, the edges must traverse only in the specified direction to form the sequence of edges required to make a path.
• Cycle: A cycle is a path with at least two vertices involved; it starts and ends on the same vertex. For example, in Figure 1, the path DCED is a cycle.
• Loop: A loop is an edge that connects a node to itself. In Figure 1, vertex A has a loop.
• Subgraph: The subgraph of a graph is another type of graph where all the edges and vertices are the same as the edges and vertices of the original graph. For example, in Figure 1, the nodes A, B, and C along with the edges AB and BC represent a subgraph.
• Connected graph: A connected graph is a graph in which there exists a path that starts from any arbitrary vertex and ends in any arbitrary, but different vertex. The graph in Figure 1 is not connected. But, the subgraph with vertices H, I, and J and the edges HI, IJ, and JH represent a connected subgraph:
  

  Figure 2. Example directed graph

• Tree: A tree is a connected but undirected graph with no cycles and loops. Figure 3 shows an example of a tree. Note that this is slightly different from the tree we have studied earlier. This tree does not have any particular root. The nodes in this tree do not have any particular parent, and any node can act as a root:
  

  Figure 3. Example tree

• Forest: A forest is an unconnected, undirected graph with no cycles or loops. You can think of a forest as a collection of trees. A single tree is also a forest. In other words, a forest is a collection of zero or more trees.
• Complete graph: A complete graph is an undirected graph that has the maximum number of edges, given a certain number of vertices. It also has constraints as per which there can only be one edge between two given vertices, with no loops. Figure 4 shows an example of a complete graph. For a complete graph with the set of vertices V and the set of edges E, |E| = |V| ( |V| - 1) / 2. It is easy to see why this is the case. Each vertex will have an edge between itself and other |V| - 1 nodes. That makes a total of |V| ( |V| - 1) edges. However, in this approach, each edge is counted twice, once for each of its two vertices. So, the actual number of edges in a complete graph is |V| ( |V| - 1) / 2:
  

  Figure 4. A complete graph