Complete the code to check if a graph has no cycles, which is a key property of a tree.
function isTree(graph: Map<number, number[]>): boolean {
// A tree has no cycles
return !hasCycle(graph, [1]);
}We start cycle detection from node 1 (assuming nodes start at 1). Trees have no cycles.
Complete the code to count edges in a tree given nodes count n.
function countEdgesInTree(n: number): number {
// A tree with n nodes has [1] edges
return n - 1;
}A tree with n nodes always has n-1 edges.
Fix the error in the function that checks if a graph is connected (a tree must be connected).
function isConnected(graph: Map<number, number[]>, n: number): boolean {
const visited = new Set<number>();
function dfs(node: number) {
visited.add(node);
for (const neighbor of graph.get(node) || []) {
if (!visited.has(neighbor)) {
dfs([1]);
}
}
}
dfs(1);
return visited.size === n;
}We must call dfs on the neighbor to visit all connected nodes.
Fill both blanks to create a function that checks if a graph is a tree by verifying connectivity and edges count.
function isTree(graph: Map<number, number[]>, n: number): boolean {
const edgesCount = [1];
const connected = isConnected(graph, n);
return connected && edgesCount === [2];
}A tree must be connected and have exactly n-1 edges.
Fill all three blanks to implement a function that counts edges in an undirected graph represented by adjacency list.
function countEdges(graph: Map<number, number[]>): number {
let count = 0;
for (const [1] of graph.values()) {
count += [2];
}
return count [3] 2;
}We sum the length of neighbors arrays and divide by 2 because edges are counted twice in undirected graphs.