Graphs

A graph is a collection of nodes called vertices that are connected to one another through edges.

Direction

Direction relates to the way vertices are connected with one another. If one vertex points to another vertex, but that other vertex does not necessarily point back, then we have a directed graph. If the connection goes both ways, then it is an undirected graph or a bi-directional graph.

Connection

A graph is considered connected when you can reach any vertex from any other vertex, or that there are no sets of vertices that are disconnected from the other vertices. A graph is considered strongly connected if all of the connections are bi-directional. Otherwise it is weakly connected.

Cycles

A cycle is when three or more vertices connect to form a closed loop. A graph that has no cycles is called a acyclic graph. A graph with at least one cycle is a cyclic graph. When traversing cyclic graphs you need to be careful to not get into an infinite loop, and instead mark nodes as visited.

Respresenting in code

Graphs are created using an adjacency list, or list of nodes with their adjacent nodes in another list.

class Vertex:
    def __init__(self, val, edges):
        self.var = val
        self.edges = list(edges) # Pointers

Complexity

The space complexity of a graph is O(v+e) where v is the number of vertices and e is the number of edges.

• Depth First Search Traversing: O(v+e)
• Bredth First Search Traversing: O(v+e)