Storing graphs using adjacency list

Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.
Introduction To Graph Theory …FTC 👈 👈 😉

To store a graph, two methods are common:

1. Adjacency Matrix
2. Adjacency List

An adjacency matrix is a square matrix used to represent a finite graph. Adjacency Matrix (Storing Graphs)  👈 👈 😉 

Adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbours of a vertex in a graph. It takes less memory to store graphs.

Let’s see a graph, and its adjacency matrix:

Now we create a list using these values.

This is called adjacency list. It shows which nodes are connected to which nodes. We can store this information using a 2D array. But will cost us the same memory as Adjacency Matrix.

Instead we are going to use dynamically allocated memory to store this one. Many languages support Vector or List which we can use to store adjacency list. For these, we don’t need to specify the size of the List. We only need to specify the maximum number of nodes.

The pseudo-code will be:

Procedure Adjacency-List(maxi, edgeN):   //maxi denotes maximum number of nodes
edge[maxi] = Vector()                   // edgeN denotes number of edges
for i from 1 to edgeN
  input -> x, y              // Here x, y denotes there is an edge between x, y
  edge[x].push(y)
  edge[y].push(x)
end for
Return edge

Since this one is an undirected graph, it there is an edge from x to y, there is also an edge from y to x. If it was a directed graph, we’d omit the second one. For weighted graphs, we need to store the cost too. We’ll create another vector or list named cost[] to store these.
The pseudo-code:

Procedure Adjacency-List(maxi, EdgeN):
edge[maxi] = Vector()
cost[maxi] = Vector()
for i from 1 to EdgeN
  input -> x, y, w
  edge[x].push(y)
  cost[x].push(w)
end for
Return edge, cost

From this one, we can easily find out the total number of nodes connected to any node, and what these nodes are.

It takes less time than Adjacency Matrix. But if we needed to find out if there’s an edge between u and v, it’d have been easier if we kept an adjacency matrix.

Introduction To Graph Theory …FTC 👈 👈 😉
Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

---

Morae Q!

1. Convert from binary number to decimal number.
2. Swap two numbers by using division and multiplication.
3. Compute foot and inches into centimetres.
4. Concatenate Strings.
5. Convert lowercase letters to uppercase letters.
6. Compute the sum of all the digits of N.
7. Compute the area of the pentagon.
8.  Get input using scanner.
9. Find the distance between two points (x1,y1) and (x2,y2).
10. Finding patterns in a file using frep and egrep .
11. Detecting a cycle in a directed graph using Depth First Traversal.
12. Topological ordering in a Graph.
13. Storing graphs using adjacency list.
14. Introduction to graph theory.
15. Graph Adjacency Matrix pseudo code.
16. Adjacency Matrix for storing graphs.
17. Dijkstra’s shortest path algorithm .
18. Breadth first search (BFS) Algorithm.
19. Find the multiple of given number in the list of integers.
20. Finding patterns in files using grep .

---