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! 

Here Is How You Can Create Directed Graphs In Python And Use In Coding Problems Found In Leetcode Platform 

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.

What Are The Ways To Represent Directed Graphs In Python 

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()

Explanation

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: 

Output

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. 

Example Problems From Leetcode 

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.

Steps:

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:
     

  # Step 1:

Create the graph
        Graph = DirectedGraph()
        For course, prereq in prerequisites:
            Graph.add_edge(prereq, course)
        
 

      # Step 2

: 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
        
     

  # Step 3: Check for cycles for each course

        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:
 

      # Step 1: Create a graph for characters

        Graph = DirectedGraph()
        For word in words:
            For char in word:
                If char not in graph.graph:
                    Graph.graph[char] = []
        

        # Step 2: Add edges based on the order of characters in words

        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
        

        # Step 3: Topological sort using DFS

        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])

End note: How Directed Graphs Are Useful 

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.