# Graph tutorial-directed & undirected graphs ,adjacency list & adjacency matrix

A graph is a collection of nodes and edges.

Nodes can be visualized as circles with data inside them. These can be simple data like numbers, alphabets or even complex objects that hold a lot of data. Nodes are also referred to as vertices (vertex in singular).

Edges are connections between nodes and are shown by lines with arrowheads showing the direction of the connection or lines without arrowheads in case the connection is in both directions.

A bidirectional connection/relation between A and B.

Taking the above illustrations, we can comfortably say that graphs model relationship between things. For instance ,a graph showing connectivity between cities, or routes within a city.

**Neighbor **node-node or nodes that you can travel to when positioned at a specific node while obeying the directionality of the relationship. In Illustration 2 above B is a neighbor of A but B does not consider A as a neighbor since there is no path to travel from B to A as per the directionality of the edge.

In Illustration 3 B is a neighbor to A and A is a neighbor to B since it is possible to travel to either node when positioned at any of the nodes.

## Types of Graphs

We have two main variants of graphs

- Directed graphs
- Undirected graphs

### Directed graphs

These are graphs whereby there is direction between the nodes.

This is indicated by arrow heads from the source node to its neighbor.

In above graph we can travel to B from A but not vice versa.

### Undirected graph

In this graph, direction is shown by lines without arrowheads and is bidirectional. If A and B are connected B is neighbor to A and A is neighbor to B since we can travel to either node from any of the nodes.

## Graph representation

Graphs can be represented in two (2) , major ways.

- Adjacency list
- Adjacency matrix

### Adjacency List

Adjacency list holds a list of neighbors for every node in the graph.It is best implemented in a map since a map data structure gives constant time during look up when checking the neighbors of a node.

Let’s explore with the below example.

The above graph is an example of a disjoint graph whereby some nodes have connections to each other but are outside the network of the other nodes in the graph.

The adjacency list will be ;

*Explanation*

p has neighbor q only hence the entry p:[q],conversely q has p as her only neighbor hence the entry q:[p].

i has 2 neighbors j and k hence the entry i:[j,k].j has only i as her neighbor hence the entry j:[i],k has 3 neighbors i ,m and l hence the entry k:[i,m,l],l has only 1 neighbor k hence the entry l:[k],m has only 1 neighbor k hence the entry m:[k] . n and o are disjoint from the bigger graph, nevertheless n has only 1 neighbor o hence the entry n:[o] and o has only 1 neighbor n hence the entry o:[n].

### Adjacency list implementation in Java

We can implement the adjacency list for the above graph in Illustration 4

package graphs;

import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;

public class AdjacencyList {

public static void main(String... args) {

List<List<String>> undirectedGraph = new ArrayList<>();

ArrayList<String> edge0 = new ArrayList<>();

edge0.add("i");

edge0.add("j");

ArrayList<String> edge1 = new ArrayList<>();

edge1.add("k");

edge1.add("i");

ArrayList<String> edge2 = new ArrayList<>();

edge2.add("m");

edge2.add("k");

ArrayList<String> edge3 = new ArrayList<>();

edge3.add("k");

edge3.add("l");

ArrayList<String> edge4 = new ArrayList<>();

edge4.add("o");

edge4.add("n");

ArrayList<String> edge5 = new ArrayList<>();

edge5.add("p");

edge5.add("q");

undirectedGraph.add(edge0);

undirectedGraph.add(edge1);

undirectedGraph.add(edge2);

undirectedGraph.add(edge3);

undirectedGraph.add(edge4);

undirectedGraph.add(edge5);

System.out.println("------Undirected edge list-----");

System.out.println(undirectedGraph);

Map<String, List<String>> adjList = buildAdjacencyList(undirectedGraph);

System.out.println("-----Adjacency list-----");

adjList.keySet().stream().forEach(key -> {

System.out.println(key + ":" + adjList.get(key));

});

}

private static Map<String, List<String>> buildAdjacencyList(List<List<String>> undirectedGraph) {

Map<String, List<String>> adjacencyList = new HashMap<>();

for (List<String> connection : undirectedGraph) {

String a = connection.get(0);

String b = connection.get(1);

if (!adjacencyList.containsKey(a)) {

adjacencyList.put(a, new ArrayList<>());

}

if (!adjacencyList.containsKey(b)) {

adjacencyList.put(b, new ArrayList<>());

}

adjacencyList.get(a).add(b);

adjacencyList.get(b).add(a);

}

return adjacencyList;

}

}

The output of the above program is as below:

### Adjacency matrix

In this approach we have a matrix of N*N dimensionality whereby N is the number of nodes in the graph. If an edge exists between Nodes A and B, we have 1 in the matrix intersection N_{RC} and a 0 where there is no edge, R=row, C=column.

Going with the graph in *Illustration 4 *we have below adjacency matrix.

Explanation

i has 2 neighbors j and k so we have 1 at indices (0,1)=j and (0,2)=k.The rest of the row-column intersections have 0 .In the second row,we keep neighbors for j.j has only 1 neighbor i so at (1,0) we have 1.The rest of the row-column intersections for j have 0.On the 3^{rd} row,we keep neighbors for k.k has 3 neighbors i,l and m.At (2,0)=i we have 1,at (2,3)=l we have 1 and at (2,4)=m we have 1.All the other row-column intersections have 0’s since k has no connection with them.On the 4^{th} row we have data for l’s neighbors.l has only 1 neighbor k so at (3,2)=k,we have 1.However this was already set up when tracking k’s neighbors since l is k’s neighbor at index (2,3) in the previous row.This is because our graph in illustration 4 is a undirected graph.The process repeats for all the remaining nodes.

Lets look at sample code to implement the above adjacency matrix in Java.

### Adjacency matrix implementation in Java

package graphs;

import java.util.ArrayList;

import java.util.List;

public class AdjacencyMatrix {

public static void main(String... args) {

List<String> vertices = new ArrayList<>();

vertices.add("i");

vertices.add("j");

vertices.add("k");

vertices.add("l");

vertices.add("m");

vertices.add("n");

vertices.add("o");

vertices.add("p");

vertices.add("q");

List<List<String>> undirectedGraph = new ArrayList<>();

ArrayList<String> edge0 = new ArrayList<>();

edge0.add("i");

edge0.add("j");

ArrayList<String> edge1 = new ArrayList<>();

edge1.add("k");

edge1.add("i");

ArrayList<String> edge2 = new ArrayList<>();

edge2.add("m");

edge2.add("k");

ArrayList<String> edge3 = new ArrayList<>();

edge3.add("k");

edge3.add("l");

ArrayList<String> edge4 = new ArrayList<>();

edge4.add("o");

edge4.add("n");

ArrayList<String> edge5 = new ArrayList<>();

edge5.add("p");

edge5.add("q");

undirectedGraph.add(edge0);

undirectedGraph.add(edge1);

undirectedGraph.add(edge2);

undirectedGraph.add(edge3);

undirectedGraph.add(edge4);

undirectedGraph.add(edge5);

int[][] adjMatrix = buildAdjacencyMatrix(vertices, undirectedGraph);

//print constructed matrix

for (int i = 0; i < adjMatrix.length; i++) {

for (int j = 0; j < adjMatrix.length; j++) {

System.out.print(" " + adjMatrix[i][j]);

}

System.out.println();

}

}

private static int[][] buildAdjacencyMatrix(List<String> vertices, List<List<String>> undirectedGraph) {

int[][] adjMatrix = new int[vertices.size()][vertices.size()];

for (List<String> connection : undirectedGraph) {

String a = connection.get(0);

String b = connection.get(1);

int aindex = vertices.indexOf(a);

int bindex = vertices.indexOf(b);

adjMatrix[aindex][bindex] = 1;

adjMatrix[bindex][aindex] = 1;

}

return adjMatrix;

}

}

Running the above program outputs below which is the same adjacency matrix we have discussed.