Javascript Coding Test Course, Representation of Graphs

Definition of Graph

A graph is a data structure composed of vertices and edges, where vertices represent objects or nodes, and edges represent relationships between vertices. Graphs can be divided into directed graphs (Directed Graph) and undirected graphs (Undirected Graph).

Additionally, graphs can be weighted (Weighted Graph) or unweighted (Unweighted Graph). In weighted graphs, costs or distances are assigned to edges.

Ways to Represent Graphs

There are two main ways to represent graphs:

• Adjacency Matrix: Represent the relationships between vertices using a two-dimensional array. The size of the array is determined by the number of vertices, and the values in the matrix indicate the presence of an edge between two vertices or include weights.
• Adjacency List: Represent a list of adjacent vertices for each vertex. This method is memory efficient and advantageous for sparse graphs.

Problem: Finding Paths in a Graph

Let’s solve the following problem.

Problem Description: Given a graph with two vertices A and B, write a function to find and print all paths from A to B.

The graph is given as an adjacency list.

Example Problem

Input:
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
}
start = 'A'
end = 'E'

Output:
['A', 'B', 'D', 'E']
['A', 'C', 'D', 'E']
            

Problem-Solving Process

To solve this problem, we will use the Depth-First Search (DFS) algorithm. DFS is an algorithm that explores the depth of the graph to find all possible paths.

Step 1: Define the DFS Function

First, we define a DFS function that explores all paths starting from the current vertex. This function maintains the current path as a list and stores the path when it reaches the target vertex.

function findPaths(graph, start, end, path = [], paths = []) {
    path.push(start); // Add the current vertex to the path

    // Save the path if the target vertex is reached
    if (start === end) {
        paths.push([...path]);
    } else {
        // Call DFS for adjacent vertices
        for (const neighbor of graph[start] || []) {
            findPaths(graph, neighbor, end, path, paths);
        }
    }

    path.pop(); // Remove the current vertex from the path (backtracking)
    return paths; // Return all paths
}
            

Step 2: Define the Graph and Input Values

Now, we define the graph along with the starting and ending vertices.

const graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
};

const start = 'A';
const end = 'E';
            

Step 3: Execute the Function

We will execute the function to find all paths and print the results.

const allPaths = findPaths(graph, start, end);
console.log(allPaths);
            

Final Code

function findPaths(graph, start, end, path = [], paths = []) {
    path.push(start); // Add the current vertex to the path
    if (start === end) {
        paths.push([...path]); // Add the path when it is complete
    } else {
        for (const neighbor of graph[start] || []) {
            findPaths(graph, neighbor, end, path, paths); // Call DFS
        }
    }
    path.pop(); // Backtracking
    return paths; // Return all paths
}

const graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': ['E'],
    'E': []
};

const start = 'A';
const end = 'E';
const allPaths = findPaths(graph, start, end);
console.log(allPaths);
            

Conclusion

In this post, we explained how to represent graphs using JavaScript and how to solve the path-finding problem using DFS. Understanding the essence and applications of graphs is very important as they are useful for solving various real-life problems. I hope you will develop your problem-solving skills by tackling more algorithmic problems in the future.