cycle checking

a graph has a cycle if, at any point in the graph:

• it has a path of length > 2,
• where start vertex = end vertex
• without using an edge more than once

cycle checking = checking if there is a cycle about a particular vertex

i.e., starting from a particular vertex, is there a path back to it

solution: use DFS to find a path back to starting node

• cycle checking C code

connected components

answering the question: for a given graph, how many connected subgraphs are there?

solution: create a componentOf[] array, where each index refers to a vertex, and the value at that index refers to which graph it’s in

• e.g.

• connected components pseudocode

finding the number of connected components is quite time intensive

• to save time, cache info about the number of components in the graph struct and dynamically change it as edges are added/removed