X1593: Complete method has3Cycle

Description

Write a method boolean has3Cycle(Graph g, int a, int c) that checks if an undirected graph contains a triangle, also known as a 3-node cycle. For example, consider a graph with nodes n1, n2, and n3; a triangle is formed if there is an edge connecting n1 to n2, an edge connecting n2 to n3, and an edge connecting n3 to n1. Because the graph is undirected, the edges are not directional.

This method takes 3 parameters, a graph g, and two nodes, a and c. It returns true if:

there is an edge to/from a and another node, call it x
there is an edge to/from c and node x,
and there is an edge to/from a to c.

Reference

The documentation for the GraphADT interface is available online.

We have included a partial definition of Graph here for your convenience.

public class Graph implements GraphADT<String> ...
{
// Is this graph a directed graph?
public boolean isDirected();

// Return the number of nodes in this graph
public int getNodeCount();

// Return the number of edges in the graph.
public int getEdgeCount();

// Returns true iff the graph has the edge
// from v to w.
public boolean hasEdge(int v, int w);

// Return the number of edges on node v.
public int getNodeDegree(int v);
}

Your Answer:

Feedback

Your feedback will appear here when you check your answer.