A graph is a data structure that consists of a set of nodes connected by edges. Graphs are used to simulate many real-world problems, such as routes in cities, circuit networks, and social networks. This is graph implementation part 1 – an unweighted graph.

### Terminology

A node in the graph is also called a vertex.  A line between two nodes is an edge. Two nodes are adjacent, called neighbors if they are connected through an edge. A path represents a sequence of edges between the two nodes.

In a directed graph, all of the edges represent a one-way relationship. In an undirected graph, all edges are bidirectional.

If the edges in the graph have weights (represent costs or distances), the graph is said to be a weighted graph. If the edges do not have weights, the graph is said to be unweighted.

A graph can be presented as an adjacency list or adjacency matrix. An adjacency list is a “list of lists”, i.e. a list of nodes, with each node having a list of neighbors. An adjacency list is used for the representation of a sparse graph. An adjacency matrix is a square matrix with dimensions equivalent to the number of nodes in the graph. An adjacency matrix is preferred when the graph is dense.

### You are here

Part 1 – Graph as an adjacency list
Part 2 – Weighted graph as an adjacency list
Part 3 – Depth first search in an adjacency matrix
Part 4 – Shortest path in an adjacency matrix

First, we define a Graph class. The Graph class has two fields:  adj and directedadj is a HashMap in which the key is the node, the value is all its neighbors. The value is represented as a linked list of neighbors. directed is a boolean variable to specify whether the graph is directed or undirected. By default, it is undirected.

In many old implementations of adjacency lists, adj is defined as an array of node lists. The disadvantage of this implementation is that we have to define the length of the array first. To avoid this, we use a hashmap. By using hashmap, we can retrieve the node and its neighbors by node itself, not by index in the array. Note the node can be any data type, such as Integer or String, or a customer-defined graphNode class.

To add a node to the graph is to add a key in the hashmap. To add an edge is to add an item in this key’s value. The following method addEdge includes both adding a node and adding an edge. For a directed graph, we add an edge from a to b. For the undirected graph, we also add an edge from b to a.

## Doodle

### Remove node and edge

The removal operation can be removing an edge or removing a node. To remove an edge, we use the first node as the key to find its neighbors in the hashmap. Then remove the second node from its neighbors. For a directed graph, we just need to remove the edge from a to b. For an undirected graph, we also need to remove the edge from b to a.

## Doodle

To remove a node, we have to remove all connected edges before removing the node itself. For an undirected graph, first, we get all the neighbors of the node. Then for each of its neighbors, remove itself from the value list. For a directed graph, we search all keys in the hashmap for their values and check whether this node exists in their neighbors. If it does, remove it. The last step is to remove the node as the key in the hashmap. Then this node is no longer in the hashmap’s key set.

## Doodle

Search can be a search of a node, an edge, or a path. We can check whether there is a node existing in the graph. This can be done by simply checking if the hashmap contains the key. We can also check whether there is a direct connection between two nodes (aka whether there is an edge). This can be done by checking whether the second node is in the first node’s neighbors.

## Doodle

### Find path with depth first search in graph

A more useful operation is to search for a path. A path is a sequence of edges. There can be more than one path between two nodes. There are two common approaches: depth first search (DFS) and breadth first search (BFS). In this section, we use DFS and BFS to find out whether there is a path from one node to another.

Depth First Search starts from the source node and explores the adjacent nodes as far as possible before returning. DFS is usually implemented with recursion or stack. It is used to solve find-path or detect cycle problems.

## Doodle

### Find path with breadth first search in graph

Breath First Search starts from the source node and explores all its adjacent nodes before going to the next level of adjacent nodes. BFS is usually implemented with a queue. It is often used to solve shortest-path problems.

## Python

### Print graph as adjacency list

The print operation is to display all nodes and their neighbors. Since it is a hashmap, you can print all keys and entries in the hashmap. This method is used for debugging purposes.

## Python

### Traverse with depth first search in graph

DFS traversal is to use depth-first search to visit nodes in the graph and print the node’s information. This is similar to DFS traversal in a binary tree. Starting from the source node, we call the recursive method to visit one of its neighbors, then a neighbor of the neighbor, and so on. Please note the source node might be any node in the graph. Some nodes might not be reached in a directed graph. (In a binary tree, we always start from the root and all nodes should be visited.)

## Doodle

### Traverse with breadth first search in graph

BFS traversal is to use breadth-first search to visit all nodes in the graph and print the node’s information. This is similar to BFS traversal in a binary tree. Starting from the source node, visit all its neighbors first before visiting the next level of neighbors. Please note the source might be any node in the graph. Some nodes might not be reached in a directed graph. (In a binary tree, we always start from the root and all nodes should be visited.)