Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of adjacency list for an undirected weighted graph

What is the printed adjacency list representation of this undirected weighted graph after adding edges?

DSA Java

import java.util.*;

class Graph {
    Map<Integer, List<int[]>> adjList = new HashMap<>();

    void addEdge(int u, int v, int w) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(u).add(new int[]{v, w});
        adjList.get(v).add(new int[]{u, w});
    }

    void printGraph() {
        for (int key : adjList.keySet()) {
            System.out.print(key + " -> ");
            for (int[] pair : adjList.get(key)) {
                System.out.print("(" + pair[0] + ", " + pair[1] + ") ");
            }
            System.out.println("null");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2, 5);
        g.addEdge(1, 3, 10);
        g.addEdge(2, 3, 2);
        g.printGraph();
    }
}

A

1 -> (2, 5) (3, 10) null
2 -> (1, 5) (3, 2) (1, 10) null
3 -> (1, 10) (2, 2) null

B

1 -> (2, 5) (3, 10) null
2 -> (3, 2) null
3 -> (1, 10) (2, 2) null

C

1 -> (2, 5) (3, 10) null
2 -> (1, 5) (3, 2) null
3 -> (1, 10) (2, 2) null

D

1 -> (2, 5) null
2 -> (1, 5) (3, 2) null
3 -> (1, 10) (2, 2) null

💡 Hint

Remember that in an undirected graph, edges are added in both directions with the same weight.

Each edge is stored twice: once from u to v and once from v to u with the same weight. So vertex 1 connects to 2 and 3, vertex 2 connects back to 1 and also to 3, and vertex 3 connects back to 1 and 2.

❓ Predict Output

intermediate

Output of adjacency list for a directed weighted graph

What is the printed adjacency list representation of this directed weighted graph after adding edges?

DSA Java

import java.util.*;

class Graph {
    Map<Integer, List<int[]>> adjList = new HashMap<>();

    void addEdge(int u, int v, int w) {
        adjList.putIfAbsent(u, new ArrayList<>());
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.get(u).add(new int[]{v, w});
    }

    void printGraph() {
        for (int key : adjList.keySet()) {
            System.out.print(key + " -> ");
            for (int[] pair : adjList.get(key)) {
                System.out.print("(" + pair[0] + ", " + pair[1] + ") ");
            }
            System.out.println("null");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2, 5);
        g.addEdge(1, 3, 10);
        g.addEdge(2, 3, 2);
        g.printGraph();
    }
}

A

1 -> (2, 5) null
2 -> (3, 2) null
3 -> null

B

1 -> (2, 5) (3, 10) null
2 -> (1, 5) (3, 2) null
3 -> null

C

1 -> (2, 5) (3, 10) null
2 -> (3, 2) (1, 5) null
3 -> null

D

1 -> (2, 5) (3, 10) null
2 -> (3, 2) null
3 -> null

💡 Hint

In a directed graph, edges go only one way from source to destination.

Edges are stored only from the source vertex to the destination vertex with the given weight. No reverse edges are added.

🧠 Conceptual

advanced

Identify the type of graph from description

You have a graph where edges have directions and weights. Which of the following terms correctly describes this graph?

A Directed weighted graph

B Undirected unweighted graph

C Undirected weighted graph

D Directed unweighted graph

💡 Hint

Edges have arrows and numbers representing cost or distance.

A graph with edges that have directions (arrows) and weights (numbers) is called a directed weighted graph.

🧠 Conceptual

advanced

Difference between vertices and edges

Which statement correctly describes the difference between vertices and edges in a graph?

A Vertices are connections; edges are points.

B Vertices are points; edges are connections between points.

C Vertices are weights; edges are directions.

D Vertices are directions; edges are weights.

💡 Hint

Think of a graph like a map of cities and roads.

Vertices are the points or nodes (like cities), and edges are the connections or links (like roads) between them.

🔧 Debug

expert

Identify the error in weighted directed graph edge addition

What error will this code produce when adding edges to a weighted directed graph?

DSA Java

import java.util.*;

class Graph {
    Map<Integer, List<int[]>> adjList = new HashMap<>();

    void addEdge(int u, int v, int w) {
        adjList.get(u).add(new int[]{v, w});
    }

    void printGraph() {
        for (int key : adjList.keySet()) {
            System.out.print(key + " -> ");
            for (int[] pair : adjList.get(key)) {
                System.out.print("(" + pair[0] + ", " + pair[1] + ") ");
            }
            System.out.println("null");
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge(1, 2, 5);
        g.addEdge(1, 3, 10);
        g.addEdge(2, 3, 2);
        g.printGraph();
    }
}

A NullPointerException

B ClassCastException

C No error, prints correctly

D IndexOutOfBoundsException

💡 Hint

Check if the adjacency list for a vertex is initialized before adding edges.

The code tries to add to a list for a vertex key that was never initialized, causing a NullPointerException.

Practice

1. Which of the following best describes a vertex in a graph?

easy

A. A point or node where edges meet

B. A line connecting two vertices

C. A graph with no edges

D. A graph that has weights on edges

Solution

1. Step 1: Understand the definition of vertex

   A vertex is a fundamental unit in a graph representing a point or node.

2. Step 2: Differentiate vertex from edges and graph types

   Edges connect vertices; weights and graph types describe edges or the whole graph, not vertices.

3. Final Answer:

   A point or node where edges meet -> Option A

4. Quick Check:

   Vertex = point/node [OK]

Hint: Vertices are points/nodes, edges are connections [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights define vertices
• Mixing graph types with vertex definition

2. Which of the following is the correct way to declare an undirected weighted graph using adjacency list in Java?

easy

A. Map graph = new HashMap<>();

B. Map graph = new TreeMap<>();

C. Map>> graph = new TreeSet<>();

D. Map>> graph = new HashMap<>();

Solution

1. Step 1: Identify data structure for weighted edges

   Weighted edges need to store both neighbor and weight, so Pair is used.

2. Step 2: Choose correct map and list types

   HashMap with List of pairs is standard for adjacency list of weighted graphs.

3. Final Answer:

   Map>> graph = new HashMap<>(); -> Option D

4. Quick Check:

   Weighted graph uses Pair for edges [OK]

Hint: Weighted edges need pairs: neighbor and weight [OK]

Common Mistakes:

• Using List<Integer> for weighted edges
• Using TreeSet instead of List for adjacency
• Confusing Map types for graph

3. Consider the following Java code snippet for a directed graph:

Map graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3));
graph.put(2, Arrays.asList(3));
graph.put(3, Arrays.asList());
System.out.println(graph.get(1));

What will be the output?

medium

A. null

B. [1, 2, 3]

C. [2, 3]

D. []

Solution

1. Step 1: Check what is stored for key 1

   Key 1 maps to list containing 2 and 3.

2. Step 2: Print the list for key 1

   Printing graph.get(1) outputs the list [2, 3].

3. Final Answer:

   [2, 3] -> Option C

4. Quick Check:

   graph.get(1) = [2, 3] [OK]

Hint: Print adjacency list for key to see neighbors [OK]

Common Mistakes:

• Expecting all vertices in output
• Confusing keys and values
• Assuming empty list prints null

4. The following code attempts to add an edge to an undirected graph represented by adjacency list. What is the bug?

void addEdge(Map graph, int u, int v) {
    graph.get(u).add(v);
}

medium

A. It adds edge only from u to v, missing v to u

B. It uses get() instead of put() to add edge

C. It should use a Set instead of List for adjacency

D. It should clear the adjacency list before adding

Solution

1. Step 1: Understand undirected graph edge addition

   Undirected edges must be added both ways: u to v and v to u.

2. Step 2: Analyze given code

   Code adds edge only from u to v, missing the reverse edge.

3. Final Answer:

   It adds edge only from u to v, missing v to u -> Option A

4. Quick Check:

   Undirected edges need both directions [OK]

Hint: Undirected edges require adding both directions [OK]

Common Mistakes:

• Adding edge only one way in undirected graph
• Confusing get() and put() usage
• Clearing adjacency list mistakenly

5. You have a weighted directed graph represented as:

Map>> graph = new HashMap<>();
graph.put(1, Arrays.asList(new Pair<>(2, 5), new Pair<>(3, 10)));
graph.put(2, Arrays.asList(new Pair<>(3, 2)));
graph.put(3, Arrays.asList());

How would you find the total weight of edges going out from vertex 1?

hard

A. Sum weights 10 + 2 = 12

B. Sum weights 5 + 10 = 15

C. Sum weights 5 + 2 = 7

D. Count edges: 2

Solution

1. Step 1: Identify edges from vertex 1

   Edges from 1 go to 2 with weight 5, and to 3 with weight 10.

2. Step 2: Sum the weights of these edges

   Total weight = 5 + 10 = 15.

3. Final Answer:

   Sum weights 5 + 10 = 15 -> Option B

4. Quick Check:

   Total outgoing weight from 1 = 15 [OK]

Hint: Add weights of all edges from the vertex [OK]

Common Mistakes:

• Adding weights from wrong vertices
• Counting edges instead of summing weights
• Mixing weights of different edges