Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Introduction to Graph Theory
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

What is Graph Theory?

Graph theory is the study of graphs, which are mathematical structures used to model pairwise relationships between objects. A graph is made up of vertices (nodes) connected by edges (lines). Graphs can represent various systems such as social networks, transportation networks, and computer networks.

Key Concepts in Graph Theory

  1. Vertices and Edges: The basic units of graphs. Vertices are points, and edges are lines connecting these points.
  2. Degree of a Vertex: The number of edges connected to a vertex.
  3. Path: A sequence of edges that connect a sequence of vertices.
  4. Cycle: A path that starts and ends at the same vertex, with no other repeated vertices.
  5. Connected Graph: A graph in which there is a path between every pair of vertices.
  6. Bipartite Graph: A graph whose vertices can be divided into two disjoint sets such that no two vertices within the same set are adjacent.
  7. Tree: A connected acyclic graph.
  8. Directed vs. Undirected Graphs: In directed graphs, edges have a direction; in undirected graphs, edges do not.

Real-Time Use Cases

  1. Social Networks: Modeling relationships between individuals.
  2. Transportation Networks: Representing cities as vertices and roads as edges.
  3. Computer Networks: Connecting computers or routers with edges representing data links.

Now, we will cover two problems to understand key concepts in graph theory:

  1. Detecting a cycle in an undirected graph.
  2. Finding the degree of a vertex in a graph.

Problem 1: Detecting a Cycle in an Undirected Graph

Problem Statement

Given an undirected graph, determine if there is a cycle present. A cycle is a path that starts and ends at the same vertex with no other repeated vertices.

Step-by-Step Algorithm

  1. Initialize Data Structures:

    • Create a visited set to keep track of all the nodes that have been visited.
    • Define a helper function dfs to perform depth-first search on the graph.

  2. Iterate Through Each Vertex:

    • For each vertex in the graph, check if it has been visited.
    • If the vertex has not been visited, call the dfs function starting from that vertex with -1 as the parent (indicating it has no parent).

  3. DFS Traversal:

    • Inside the dfs function:
      1. Mark the current node as visited by adding it to the visited set.
      2. Iterate through all the neighbors of the current node.
      3. For each neighbor:
        • If the neighbor has not been visited, recursively call the dfs function with the neighbor as the current node and the current node as its parent.
        • If the neighbor has been visited and is not the parent of the current node, a cycle is detected and the function returns True.
      4. If no cycles are found in the current path, return False.

  4. Return the Result:

    • If the dfs function returns True for any vertex, return True indicating a cycle is detected.
    • If no cycles are detected after traversing all vertices, return False.

Algorithm Walkthrough

Let’s walk through the algorithm with an example graph to understand how it detects cycles.

Example Graph

graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1, 3],
    3: [2]
}
Image

  1. Initialization:

    • visited = {} (an empty set).
    • Define the dfs function.

  2. Iteration through Vertices:

    • Start with vertex 0.
    • Since 0 is not in visited, call dfs(0, -1).

  3. DFS from Vertex 0:

    • Mark 0 as visited: visited = {0}.
    • Check neighbors of 0: 1 and 2.

  4. DFS from Vertex 1:

    • Neighbor 1 is not visited, call dfs(1, 0).
    • Mark 1 as visited: visited = {0, 1}.
    • Check neighbors of 1: 0 and 2.
    • Neighbor 0 is visited but it is the parent of 1, so continue.
    • Neighbor 2 is not visited, call dfs(2, 1).

  5. DFS from Vertex 2:

    • Mark 2 as visited: visited = {0, 1, 2}.
    • Check neighbors of 2: 0, 1, and 3.
    • Neighbor 0 is visited and it is not the parent of 2, so a cycle is detected.
    • Return True to indicate a cycle is found.

  6. Result:

    • Since a cycle is detected, detectCycle returns True.

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: O(V + E), where (V) is the number of vertices and (E) is the number of edges. Each vertex and edge is processed once.
  • Space Complexity: O(V) for the visited set and recursion stack.

Problem 2: Finding the Degree of a Vertex in a Graph

Problem Statement

Given an undirected graph, find the degree of a specified vertex. The degree of a vertex is the number of edges connected to it.

Step-by-step Algorithm

  1. Input: The graph and the vertex for which the degree is to be found.
  2. Count Edges:
    • For the given vertex, count the number of edges connected to it.

Code

Python3
Python3
. . . .

Complexity Analysis

  • Time Complexity: O(1). Finding the degree involves accessing the adjacency list of the vertex and counting its elements.
  • Space Complexity: O(1) as no additional space is required apart from the input graph.

In this lesson on graph theory, we have covered the foundational concepts and tackled two essential problems: detecting cycles in an undirected graph and finding the degree of a vertex. These exercises have introduced us to key techniques such as depth-first search and the use of adjacency lists to represent graphs.

Now, let's start solving the problems on Graph theory.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible