How to Make Directed Graph in Python leetcode: Complete Guide

Hey there! Are you stuck somewhere between understanding a directed graph and struggling to solve problems associated with it? Not anymore, as we have come up with a comprehensive guide that will help you learn everything about directed graphs that will be at your fingertips from now on. In this article, you will find all the relevant details related to directed graphs breaking it all down into understanding what graph data structure is to working with directed graphs in Python. Let’s get started!

Graph data structure makes it easier to organize information in which several things are related to each other. Let me provide you with an example of this. Alicia and Bob are friends with each other on Instagram. How is the algorithm at work behind this? Alicia and Bob have Instagram profiles which are represented by a node. Since both are connected it will be represented by an edge which shows the relationship between two nodes that Alicia and Bob are friends. This is how with graph data structure relationship between the data can be explored.

What are directed graphs or digraphs? We now know that the relationship between the nodes is shown by an edge. But, when the edge has a point from where it starts (origin) and where it ends (destination), it gives the idea that it is a directed graph. Here we can establish that in Directed graphs direction matters the most. Think of it like we follow celebrities on Instagram but they don’t follow us back. Let’s say that my profile on Instagram is represented by point A and the celebrity profile is represented by point B. Here, point A and point B will be called nodes. The origin of an Edge is point A and the destination is point B.

Now let’s try to understand this with graph terminology. Vertex or nodes are connected via edge in a certain direction and these vertices are like the building blocks of a directed graph. These vertices are denoted by (u,v) which means the edge connects vertex u to vertex v. In this case, edge starts from vertex u and ends at vertex v and there us no other possible way.

The terms indegree and outdegree are used to mention the number of incoming and outgoing edges to and from the vertex. An edge is usually directed in one way unless it is specifically defined. Digraphs represent dependencies, are used for analysis, and are commonly applied in computer networks, transportation networks, etc.

One way to represent digraph in Python is by Adjacency matrix, where a 2d array is used like this: mat[u][v]=1. The integer 1 is used to show a directed edge. Another simple way of showing how nodes are connected to each other is Adjacency lists in which each node has a list of its neighboring nodes. Adjacency lists are memory efficient, especially for graphs that are not large with a small number of edges. It is also simple to add and remove edges.

Here we will focus on Adjacency lists as it is extensively used on leetcode to output digraphs. Following is an overview of the steps to form directed graphs.

Initialize the graph as dict with nodes and edges and provide it with the necessary functions like add an edge for example. Then the stored graph data will be displayed. This graph will then be ready to go through traversal algorithms like depth-first search and breadth-first search that are used in cycle detection, topological sorting, social media, etc.

Class DirectedGraph:

Def __init__(self):

# This starts an empty dictionary to store the given adjacency list

Self.graph = {}

Def add_edge(self, u, v):

“”” This helps adds a directed edge from u to v “””

If u not in self.graph:

Self.graph[u] = []

Self.graph[u].append(v)

Def get_neighbors(self, u):

“”” Returns a list of neighbors of vertex u “””

Return self.graph.get(u, [])

Def display_graph(self):

“”” Displays the adjacency list of the graph “””

For node in self.graph:

Print(f”{node} -> {self.graph[node]}”)

# Example of creating a directed graph

Graph = DirectedGraph()

Graph.add_edge(0, 1)

Graph.add_edge(0, 2)

Graph.add_edge(1, 3)

Graph.add_edge(2, 3)

Graph.add_edge(3, 4)

Graph.display_graph()

First we declared class with the name Directed Graph, where _init_ constructor is used to initialize the graph as a dictionary. In this given problem, a vertex is stored as key, and edges related to it in value. Then add_edge (u, v) function connects an edge from u to v. In next step, we find out if node u exists in the graph. If not, we initiate an empty list for it. To retrieve the list of neighboring outgoing edges, get_outedge(u) is used. Finally, show_graph displays the adjacency list. By running the code above, the output will show the list as:

Css

Copy code

0 -> [1, 2]

1 -> [3]

2 -> [3]

3 -> [4]

Here node 0 has directed edges to 1 and 2, node 1 has a directed edge to 3, node 2 has directed edge to 3 again, and node 3 has a directed edge to 4.

1.Given numCourses and a list of prerequisite pairs prerequisites, determine if it is possible to finish all courses. This can be viewed as detecting a cycle in a directed graph.

Initial step requires: Directed graph from the prerequisite pairs is to be created

To find out whether it’s possible to complete all courses topological sorting or cycle detection (DFS) is to be applied.

Class Solution:

Def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:

Create the graph

Graph = DirectedGraph()

For course, prereq in prerequisites:

Graph.add_edge(prereq, course)

: Implement DFS to detect cycles

Visited = [0] * numCourses # 0 = not visited, 1 = visiting, 2 = visited

Def dfs(node):

If visited[node] == 1: # cycle detected

Return False

If visited[node] == 2: # already visited

Return True

Visited[node] = 1

For neighbor in graph.get_neighbors(node):

If not dfs(neighbor):

Return False

Visited[node] = 2

Return True

For I in range(numCourses):

If not dfs(i):

Return False

Return True

Explanation

The graph.add_edge (prereq, course) shows that there is a directed edge from prereq course to the main course similar to the example (u,v) provided above.

Whereas, Depth-first search (DFS) looks for cycles, connectivity, and network flow. In this particular case if no cycle is found, then it gives an ideas that course cannot be completed.

2.Given a list of words sorted lexicographically by the rules of a new language, find the order of characters in the alphabet.

Solution requires topological sorting and creating a directed graph of characters.

Class Solution:

Def alienOrder(self, words: List[str]) -> str:

Graph = DirectedGraph()

For word in words:

For char in word:

If char not in graph.graph:

Graph.graph[char] = []

For I in range(len(words) – 1):

Word1, word2 = words[i], words[I + 1]

Min_length = min(len(word1), len(word2))

For j in range(min_length):

If word1[j] != word2[j]:

Graph.add_edge(word1[j], word2[j])

Break

Visited = {} # False = unvisited, True = visited

Result = []

Cycle = set()

Def dfs(char):

If char in cycle:

Return False # cycle detected

If char in visited:

Return True # already visited

Cycle.add(char)

For neighbor in graph.get_neighbors(char):

If not dfs(neighbor):

Return False

Cycle.remove(char)

Visited[char] = True

Result.append(char)

Return True

For char in graph.graph:

If char not in visited:

If not dfs(char):

Return “”

Return “”.join(result[::-1])

For Testings: To find out that they work correctly, take sample data to try the graph structures. This can also be done by using unit tests and also by using hands. By doing this, you’ll be confident that all graph operations are working properly.

Directed graphs help us to find the shortest and the best route possible on our way to our destination. They also help organizations in ensuring network security by identifying attacking paths and any loopholes in the network. Moreover, we use the Google search engine daily and find several websites on the top. Here also the directed graph is at work which ranks websites. Also. Many people use public transport daily and there are certain routes fixed for it. So, with the help of directed graphs, route planning and traffic flow modeling have become easier.

TellerToday collects & utilizes cookies from third-parties & affiliate networks to improve user experience. If you buy a product or service after clicking on one of our links, we may get a commission.