Advanced Algorithms

Lab #6: Graph Cycle Detection


During this activity, students will be able to:


This activity must be developed in the pre-assigned teams of two.

In a file called, write a Python function called has_cycle that takes as input an initial vertex and a undirected connected graph. The function traverses the graph in DFS (Depth-First Search) order and when it detects a cycle it returns a list with the vertices that conform the path of the cycle. If there are multiple cycles in the graph, the function returns the first one found. The function returns None if the graph contains no cycles.

For example, the following graph contains a cycle:

If the DSF traversal starts at vertex A, the detected cycle has the following path:


Bear in mind that:

The has_cycle function should be called like this:

has_cycle('A', { 'A': ['B'],
                 'B': ['A', 'D'],
                 'C': ['D', 'E'],
                 'D': ['B', 'C', 'E'],
                 'E': ['C', 'D']

Note that strings are used to represent the vertices, while the graph is represented as a dictionary where each key is a string and its associated value is a list of strings (the neighbours of the corresponding vertex).

The previous function call returns the following result:

['D', 'C', 'E', 'D']

Use the following code as a starting point:

# File:

from typing import Optional

Graph = dict[str, list[str]]

def has_cycle(initial: str, graph: Graph) -> Optional[list[str]]:
    # The function's code goes here

Test your code using the tests in the file Finally, make sure no type or PEP 8 style errors are produced by using the mypy and pycodestyle linters. You can run them at the terminal like this:



Place in a comment at the top of the source file the authors’ personal information (student ID and name), for example:

# Lab #6: Graph Cycle Detection
# Date: 03-Nov-2023
# Authors:
#           A01770771 Kamala Khan
#           A01777771 Carol Danvers

Upload Instructions

To deliver the file, please provide the following information:

Request PIN

Only one team member needs to upload the file.

Due date is Friday, November 3.