A graph is an ordered pair G=(V,E), where Vis a finite set and E ⊆ VxV. The elements of V are called nodes or vertices,and the elements of E are called edges.
This is a module added in Python 3.9 that provides utilities for working with graphlike data structures.
A graph is a data structure consisting of nodes connected by edges. Graphs are a
concept from the field of mathematics known as graph theory. Depending on the
edge type, we can distinguish between two main types of graphs:
• An undirected graph is a graph where every edge is undirected. If a graph
was a system of cities connected by roads, the edges in an undirected graph
would be two-way roads that can be traversed from either side. So, if two
nodes, A and B, are connected to edge E in an undirected graph, you can
traverse from A to B and from B to A using the same edge, E.
• A directed graph is a graph where every edge is directed. Again, if a graph
was a system of cities connected by roads, the edges in a directed graph
would be a single-way road that can be traversed from a single point of
origin only. If two nodes, A and B, are connected to a single edge, E, that
starts from node A, you can traverse from A to B using that edge, but can't
traverse from B to A
Moreover, graphs can be either cyclic or acyclic. A cyclic graph is a graph that
has at least one cycle—a closed path that starts and ends at the same node. An
acyclic graph is a graph that does not have any cycles.
Graph theory deals with many mathematical problems that can be modeled using
graph structures. In programming, graphs are used to solve many algorithmic
problems. In computer science, graphs can be used to represent the flow of data or
relationships between objects. This has many practical applications, including:
• Modeling dependency trees
• Representing knowledge in a machine-readable format
• Visualizing information
• Modeling transportation systems
Topological sorting is the operation of ordering nodes of a Directed Acyclic Graph
(DAG) in a specific way. The result of topological sorting is a list of all nodes where
every node appears before all the nodes that you can traverse to from that node, in
other words:
• The first node will be the node that cannot be traversed to from any other
node
• Every next node will be a node from which you cannot traverse to previous
nodes
• The last node will be a node from which you cannot traverse to any node