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

Related