###### Books / Graph Algorithms / Chapter 1

# Introduction to Graph Algorithms

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:

- the air distance between v and w,
- the air time between them, or
- 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.