Graph algorithms are an important concept in computer science and make frequent appearance in software engineering job interviews. In this book, we’ll review what a graph is, common terminology, and review important graph algorithms.

What is a Graph?

A graph is a collection of pairs: pairs of integers, pairs of people, pairs of cities, pairs of friends on social media, pairs of stars, pairs of countries, pairs of scientific papers, pairs of web pages, pairs of game positions, pairs of recursive subproblems, even pairs of graphs. Mirroring the most common method for visualizing graphs, the underlying objects being paired are usually called vertices (or nodes), and the pairs themselves are called edges (or arcs), but in fact the objects and pairs can be anything at all.

Simple or a Undirected Graphs

A graph G = (V, E) is a set of vertices V and a set of edges E. Each edge is a pair (v, w) where v belongs to V and w belongs to V. Formally, a simple graph is a pair of sets (V, E), where V is an arbitrary non-empty finite set, whose elements are called vertices (or nodes,) and E is a set of pairs of elements of V, which we call edges. In an undirected graph, the edges are unordered pairs, or just sets of size two; I usually write uv instead of {u, v} to denote the undirected edge between u and v.

Directed Graphs

A graph G = (V, E) is a directed graph (a digraph, for short) if E is a set of ordered pairs, in which case the edges are called directed edges. In other words, in a directed graph, the edges are ordered pairs of vertices; I usually write u->v instead of (u, v) to denote the directed edge from u to v.

Weighted Graphs

A weighted graph is a graph (directed or undirected), in which edges have weights, also called costs. A weight is a numeric value assigned to an edge. You can think of a weighted graph as having a weight, or cost, function that assigns an integer to each edge. Weighted graphs are very common because they model many real world relationships. For example, Let G = (V, E) be the graph in which V is the set of all American cities with airports, and E is the set of all edges (v, w) such that there is a scheduled flight from city v to city w by some commercial airline. The weight c(v, w) assigned to the edge (v, w) might be:

1. the air distance between v and w,
2. the air time between them, or
3. the price of a minimum price ticket. Online reservation systems often let the user choose from among many criteria for weighting flights.

Graph Algorithms - Common Definitions and Terminology

There is a lot of terminology associated with graphs and graph algorithms, so let’s review that in the remainder of this chapter.

Endpoints, Head and Tail

The endpoints of an edge uv or u->v are its vertices u and v. We distinguish the endpoints of a directed edge uv by calling u the tail and v the head.

Walk vs Path

A walk in an undirected graph G is a sequence of vertices, where each adjacent pair of vertices are adjacent in G; informally, we can also think of a walk as a sequence of edges. A walk is called a path if it visits each vertex at most once. For any two vertices u and v in a graph G, we say that v is reachable from u if G contains a walk (and therefore a path) between u and v. A walk is closed if it starts and ends at the same vertex; a cycle is a closed walk that enters and leaves each vertex at most once

Length of the path

The length of a path is the number of edges (not vertices) in the path, which is N − 1 if there are N vertices in the path.

Simple path

A simple path is a path such that all vertices are distinct except possible the first and the last.

Cycles in Undirected Graph

A cycle in an undirected graph is a path in which the first and last vertices are the same and the edges are distinct (to avoid the problem that a path like u, v, u is called a cycle even though the second edge is the same as the first edge.)

Cycles in Directed Graph

A cycle in a directed graph is a path of length at least 1 such that the first and last vertices are the same. A cycle is simple if it is a simple path.

Directed Acyclic Graph (DAG)

A graph is acyclic if it has no cycles. A directed acyclic graph is called a DAG for short. Acyclic graphs are also called forests.

Connected

An undirected graph is called connected if there is a path from every vertex to every other vertex. A directed graph with this property is called strongly connected.

Spanning Tree

A spanning tree of an undirected graph G is a subgraph that is a tree and contains every vertex of G. A graph has a spanning tree if and only if it is connected.

Spanning Forest

A spanning forest of G is a collection of spanning trees, one for each component of G.

---

---