adjacency-list – Tarik Billa

Detecting cycles in a graph using DFS: 2 different approaches and what’s the difference

April 24, 2023 by Tarik

Answering my question: The graph has a cycle if and only if there exists a back edge. A back edge is an edge that is from a node to itself (selfloop) or one of its ancestor in the tree produced by DFS forming a cycle. Both approaches above actually mean the same. However, this method … Read more

What is better, adjacency lists or adjacency matrices for graph problems in C++?

November 16, 2022 by Tarik

It depends on the problem. Adjacency Matrix Uses O(n^2) memory It is fast to lookup and check for presence or absence of a specific edge between any two nodes O(1) It is slow to iterate over all edges It is slow to add/delete a node; a complex operation O(n^2) It is fast to add a … Read more