Chapter 3: Graphs

A graph is a data structure that provides a way of “encoding pairwise relationships among a set of objects”. It contains a set of nodes, which can also be called vertices, and collection of edges, where each edge joins a pair of nodes. If you are creating a graph where edges indicate a “symmetric relationship” between the nodes they connect, you are creating an undirected graph. However, if you want to code asymmetric relationships, you want to use a directed graph, where each edge has a head and a tail node. Graphs are useful for representing a number of things, which include: Transportation networks, communication networks, information networks, social networks, and dependency networks. Transportation networks can be represented by nodes as the cities or particular locations, and the edges representing the paths of travel between the locations. Communication networks utilize the nodes as devices, and the edges as representing the link between them. Information networks represent the webpages as the nodes, and hyperlinks between two webpages as the edges. Social networks represent people as the nodes, and social connections between them as the edges. Dependency networks represent elements as the nodes, and dependencies/requisites as the edges. “One of the fundamental operations in a graph is traversing a sequence of nodes connected by edges”. A simple path is a path in which all vertices are distinct from each other, meaning no vertex is visited more than once. A cycle is a path that begins at a node and ends at the same node where the nodes visited in the path are only visited once. A connected graph is a graph that maintains a path between every pair of vertices. The distance between two nodes is the minimum number of edges that must be traversed to get from one node to another. A graph can be defined as a tree if it is connected and does not contain a cycle. Trees look very similar to the heaps discussed in the previous chapter where each node has a parent and descendants. Rooted trees are trees that have a designated root node. If g is an undirected graph with n nodes, then if it has two of these three characteristics it automatically has the third, and thus means that it is a tree: 1) G is connected, 2) G does not contain a cycle, 3) G has n-1 edges.