Basics on Graphs

Basic Concepts on Graphs

• Think of a graph as a collection of nodes connected by edges.
• Terminology:

  • Directed Edges vs Undirected- Directed edges mean you can traverse in one direction, while undirected edges let you move in both directions. - For example, binary trees are directed graphs because you can't move back to a node's parent, only its children.
  • Connected Component: - This is a group of nodes connected by edges.
  • Indegree: - This is the number of edges that can be used to reach the node. - In graphs, nodes with an in-degree of zero are the smallest set of nodes from which all other nodes can be reached. - For instance, check out 1557. Minimum Number of Vertices to Reach All Nodes

    • In binary trees, all nodes except the root have an indegree of 1 (due to their parent). - In DAGs (Directed Acyclic Graphs), a node with an indegree of zero is called a source.
  • Outdegree: - This is the number of edges that can be used to leave the node. - In binary trees, an outdegree of 0 means it's a leaf.

    • In binary trees, all nodes have an outdegree of 0, 1, or 2. - In DAGs, an outdegree of zero is called a sink. - Visiting from sink components will yield all strongly connected graphs (using Kosaraju's algorithm).
  • Neighbors: Nodes that are connected by an edge.
  • Cyclic: - When you have a path in the edges that leads to visiting the same nodes infinitely. - By definition, binary trees are acyclic.

Input Formats:

1. Array Of Edges

• Needs Preprocessing! We can usually just use a hashmap, like this: graph = {node: [neighbors]}, since it's faster to find neighbors. On platforms like Leetcode, input is often given in a 2D array format.
• Each element of the array will be in the form [x, y], which indicates that there is an edge between x and y (these edges can be either directed or undirected).
• Example: edges = [[0, 1], [1, 2], [2, 0], [2, 3]].

1
from collections import defaultdict
2

3
def build_graph(edges):
4
    graph = defaultdict(list)
5
    for x, y in edges:
6
        graph[x].append(y)
7
        # graph[y].append(x)
8
        # Uncomment the above line if the graph is undirected
9

10
    return graph

2. Adjacency List

• Most convenient format!
• In an adjacency list, nodes are numbered from 0 to n - 1. The input will be a 2D integer array, let's call it graph. graph[i] will be a list of all the outgoing edges from the i-th node.
• Example: graph = [[1], [2], [0, 3], []]

3. Adjacency Matrix

• Can preprocess (if n is large) or not. The time complexity in both cases would be O(n^2), since you have n nodes and have to traverse each n times.
• Nodes will be numbered from 0 to n - 1. You'll be given a 2D matrix of size n x n, let's call it graph. If graph[i][j] == 1, that means there's an outgoing edge from node i to node j.

Graphs vs Trees

• Graphs don't always have an obvious start point, but trees have a root.
• Traversal:

  • In graphs, you need a for loop to iterate over the neighbors of the current node since a node could have any number of neighbors.
  • Trees have node.left and node.right.
• seen set:

  • Since trees are directed acyclic graphs, they don't have cycles.
  • However, graphs do!
  • Before visiting a node, first check if the node is in seen.
  • If it isn't, add it to seen before visiting it.
  • This ensures you only visit each node once in O(1) time because adding and checking for existence in a set takes constant time.