Algorithms Notes – Chapter 4

tree

xkcd/835

Graph Algorithms

Over the next few chapters, we will learn and analyse the following two graph algorithms:

  • Breadth First Search (BFS)
  • Depth First Search (DFS)

Representation of Graphs

In computer science, it is common to represent graphs in one of two ways.

  1. Adjacency List
  2. Adjacency Matrix

An adjacency list of a graph G = (V, E) is written as G.Adj.It is an array that contains a list of vertices adjacent to the vertex in the index. In other words, let u be a vertex of G. G.Adj[u] will then consist of all the vertices that are adjacent to u in G.

An adjacency matrix is a matrix defined in the following way. Let 1, 2, ... , |V| be any arbitrary ordering of the vertices in G. The a_{ij}th element of the adjacency matrix that represents G has a value of 1 if there exists an edge between the vertices i and j (i.e (i, j) \in E) and has a value of 0 otherwise.

The following figure shows both the adjacency list and adjacency matrix for a graph:

466_b

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s