Graphs are powerful data structures for solving various problems. In this post, we will explore how to represent graphs and explain the problem-solving process in detail.<\/p>\n<\/header>\n 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).<\/p>\n Additionally, graphs can be weighted (Weighted Graph) or unweighted (Unweighted Graph). In weighted graphs, costs or distances are assigned to edges.<\/p>\n<\/section>\n There are two main ways to represent graphs:<\/p>\n Let’s solve the following problem.<\/p>\n Problem Description:<\/strong> Given a graph with two vertices A and B, write a function to find and print all paths from A to B.<\/p>\n The graph is given as an adjacency list.<\/p>\n 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.<\/p>\n 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.<\/p>\n Now, we define the graph along with the starting and ending vertices.<\/p>\n We will execute the function to find all paths and print the results.<\/p>\n 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.<\/p>\n<\/section>\n<\/article>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"Definition of Graph<\/h2>\n
Ways to Represent Graphs<\/h2>\n
\n
Problem: Finding Paths in a Graph<\/h2>\n
Example Problem<\/h3>\n
\nInput:\ngraph = {\n 'A': ['B', 'C'],\n 'B': ['D'],\n 'C': ['D'],\n 'D': ['E'],\n 'E': []\n}\nstart = 'A'\nend = 'E'\n\nOutput:\n['A', 'B', 'D', 'E']\n['A', 'C', 'D', 'E']\n <\/pre>\n<\/section>\nProblem-Solving Process<\/h2>\n
Step 1: Define the DFS Function<\/h3>\n
\nfunction findPaths(graph, start, end, path = [], paths = []) {\n path.push(start); \/\/ Add the current vertex to the path\n\n \/\/ Save the path if the target vertex is reached\n if (start === end) {\n paths.push([...path]);\n } else {\n \/\/ Call DFS for adjacent vertices\n for (const neighbor of graph[start] || []) {\n findPaths(graph, neighbor, end, path, paths);\n }\n }\n\n path.pop(); \/\/ Remove the current vertex from the path (backtracking)\n return paths; \/\/ Return all paths\n}\n <\/code><\/pre>\nStep 2: Define the Graph and Input Values<\/h3>\n
\nconst graph = {\n 'A': ['B', 'C'],\n 'B': ['D'],\n 'C': ['D'],\n 'D': ['E'],\n 'E': []\n};\n\nconst start = 'A';\nconst end = 'E';\n <\/code><\/pre>\nStep 3: Execute the Function<\/h3>\n
\nconst allPaths = findPaths(graph, start, end);\nconsole.log(allPaths);\n <\/code><\/pre>\n<\/section>\nFinal Code<\/h2>\n
\nfunction findPaths(graph, start, end, path = [], paths = []) {\n path.push(start); \/\/ Add the current vertex to the path\n if (start === end) {\n paths.push([...path]); \/\/ Add the path when it is complete\n } else {\n for (const neighbor of graph[start] || []) {\n findPaths(graph, neighbor, end, path, paths); \/\/ Call DFS\n }\n }\n path.pop(); \/\/ Backtracking\n return paths; \/\/ Return all paths\n}\n\nconst graph = {\n 'A': ['B', 'C'],\n 'B': ['D'],\n 'C': ['D'],\n 'D': ['E'],\n 'E': []\n};\n\nconst start = 'A';\nconst end = 'E';\nconst allPaths = findPaths(graph, start, end);\nconsole.log(allPaths);\n <\/code><\/pre>\n<\/section>\nConclusion<\/h2>\n