Books/Graph Algorithms/ Chapter 2

The most common way to visually represent graphs is by drawing them. A drawing of a graph maps each vertex to a point in the plane (typically drawn as a small circle or some other shape) and each edge to a curve or straight line segment between the two vertices.

In computer science, graphs are usually represented by one of two standard data structures: adjacency matrices and adjacency lists. At a high level, both data structures are arrays indexed by vertices; this requires that each vertex has a unique integer identifier between 1 and V. In a formal sense, these integers are the vertices.

The adjacency matrix of a graph G is a square-matrix of 0’s and 1’s with a row for every vertex. It’s often represented as a two-dimensional array in computer programs. A[u][v] is 1 if there is an edge from u to v, otherwise it is 0. (In weighted graphs, if A is numeric valued, then A[u][v] would be the weight of the edge (u,v).)

The following asymmetric boolean matrix represents the directed graph shown below.

For undirected graphs, the adjacency matrix is always symmetric, meaning A[u, v] = A[v, u] for all vertices u and v, because uv and vu are just different names for the same edge, and the diagonal entries A[u, u] are all zeros. For directed graphs, the adjacency matrix may or may not be symmetric, and the diagonal entries may or may not be zero. Here’s another adjacency matrix for a graph where vertices are labelled a, b, c through m.

Free Question and Answers with Detailed Explanations

Code Example of Adjacency Matrix in Java

• Graphs are usually sparse, meaning that they have lots of zeros. There are $$N^{2}$$ entries in a matrix of N vertices, but the number of edges may only be a multiple of N
• Many problems that have efficient solutions cannot be solved efficiently when this representation is used, because they will all tend to be $$O\left(N^{2}\right)$$.