In all the algorithms, always explain their correctness and analyze their time c

Question

In all the algorithms, always explain their correctness and analyze their time complexity. Explain the ideas behind your algorithm. In such a case, even if the algorithm is may get partial credit. The complexity should be as small as possible. A correct algorithm with large complexity, may not get full credit. A simple cycle of size 3 is a path a-b-c-d-a that starts and ends at a and so that all the vertices of the path are different. Give an algorithm that finds the number of simple cycles of size 3 in a graph.

Explanation / Answer

Depth first search algorithm with backtracking might help you.

Initialise an array of boolean values to keep track of visited nodes before.

If you run oout of new nodes to go to, then back track and try different branch. The DFS is easy to implement if you have an adjacency list to represent the graph. For example adj[A] = {B,C} indicates that B and C are the children of A.

Pseudocode is below , "Start" is node to start from :

visited = {}

dfs(adj,start,visited)

dfs(adj,node,visited):

if (visited[node]):

    if (node == start):

      "found path"

    return;

visited[node]=YES;

for child in adj[node]:

    dfs(adj,child,visited)

visited[node]=NO;

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.