Confused about the need for DFS in for 19.5 (Degrees of Connectedness - I)

#1

Since the problem assumptions tell us the incoming graph is undirected and connected, can’t we just return the following boolean expression:

num_edges/2 == num_vertices - 1

That is the formula for the number of edges in a tree (which is minimally connected, as the text states).

I can see why you would need to perform DFS if the incoming graph was possibly unconnected, but I don’t understand why DFS is necessary with the given assumptions.

Thanks for the book by the way, I like how down-to-business it is.

EDIT: Also asked this question here, not sure I have conveyed all the details correctly though:

0 Likes
#2

Hey Nick,

I think the solution to your question is “Yes” as it definitely a good alternative for this problem. Also, like you mentioned, DFS solution is a general one.

0 Likes
#3

Thanks, that is good to know! I wanted to be positive I understood the question correctly.

0 Likes
#4

That’s a great simplification!

I was going to mention, besides checking for cycles, you should also check that the graph is not disconnected.

Nick’s predicate would check for that too of course, but if you’re going the DFS route you could check for disconnectedness this way, using the connected variable:

public boolean isMinimallyConnected(GraphNode[] nodes) {
    Set<Integer> visited = new HashSet<>();
    Set<Integer> inProgress = new HashSet<>();
    boolean connected = false;

    for (GraphNode node : nodes) {
        if (!visited.contains(node.id)) {
            if (connected || dfs(node, null, visited, inProgress)) {
                return false;
            }
            connected = true;
        }
    }

    return true;
}
0 Likes
#5

thanks to everyone for pointing this out. you are quite right, for a connected UNDIRECTED graph, a cycle exists iff the number of edges is greater than or equal to the number of vertices.

we’ve reworded the problem to directed graphs where it makes much more sense to use DFS and search for backedges.

thanks again,

cheers,
adnan

Programs: http://elementsofprogramminginterviews.com/static/solutions/2-exists.cc, http://elementsofprogramminginterviews.com/static/solutions/java/src/main/java/com/epi/TwoExists.java

New problem and solution:

0 Likes