Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Java

Mental Model

A graph is a way to connect points (vertices) with lines (edges) that can have directions and weights.

Analogy: Think of a city map where intersections are points (vertices) and roads are lines (edges). Some roads go one way (directed), some both ways (undirected), and some roads are longer or shorter (weighted).

Vertices: A, B, C, D
Edges:
A -> B (directed)
B ↔ C (undirected)
C -> D (directed, weight 5)

  A -> B
      ↘
       C ↔ D

Weights shown as numbers on edges if any.

Dry Run Walkthrough

Input: Graph with vertices A, B, C, D; edges: A->B (directed), B↔C (undirected), C->D (directed, weight 5)

Goal: Understand how vertices and edges connect, and how direction and weight affect the graph

Step 1: Add vertex A

Vertices: [A]
Edges: none

Why: Start with one point to build the graph

Step 2: Add vertex B and directed edge from A to B

Vertices: [A, B]
Edges: A -> B

Why: Connect A to B with a one-way line

Step 3: Add vertex C and undirected edge between B and C

Vertices: [A, B, C]
Edges: A -> B, B ↔ C

Why: Connect B and C with a two-way line

Step 4: Add vertex D and directed weighted edge from C to D with weight 5

Vertices: [A, B, C, D]
Edges: A -> B, B ↔ C, C -> D (weight 5)

Why: Add a one-way line with a cost or distance

Result:

Vertices: [A, B, C, D]
Edges: A -> B, B ↔ C, C -> D (weight 5)

Annotated Code

DSA Java

import java.util.*;

class Graph {
    static class Edge {
        String from, to;
        boolean directed;
        int weight;

        Edge(String from, String to, boolean directed, int weight) {
            this.from = from;
            this.to = to;
            this.directed = directed;
            this.weight = weight;
        }

        @Override
        public String toString() {
            String arrow = directed ? "->" : "↔";
            String w = weight > 0 ? " (weight " + weight + ")" : "";
            return from + " " + arrow + " " + to + w;
        }
    }

    Set<String> vertices = new LinkedHashSet<>();
    List<Edge> edges = new ArrayList<>();

    void addVertex(String v) {
        vertices.add(v);
    }

    void addEdge(String from, String to, boolean directed, int weight) {
        addVertex(from);
        addVertex(to);
        edges.add(new Edge(from, to, directed, weight));
    }

    void printGraph() {
        System.out.println("Vertices: " + vertices);
        System.out.println("Edges:");
        for (Edge e : edges) {
            System.out.println(e);
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph();
        g.addEdge("A", "B", true, 0); // directed edge A->B
        g.addEdge("B", "C", false, 0); // undirected edge B<->C
        g.addEdge("C", "D", true, 5); // directed weighted edge C->D weight 5
        g.printGraph();
    }
}

edges.add(new Edge(from, to, directed, weight));

Add edge with direction and weight info

System.out.println(e);

Print each edge showing direction and weight

g.addEdge("A", "B", true, 0);

Add directed edge from A to B

g.addEdge("B", "C", false, 0);

Add undirected edge between B and C

g.addEdge("C", "D", true, 5);

Add directed weighted edge from C to D with weight 5

Output

Vertices: [A, B, C, D]

Edges:

A -> B

B ↔ C

C -> D (weight 5)

Complexity Analysis

Time: O(V + E) because adding vertices and edges each take constant time, done for all vertices and edges

Space: O(V + E) because we store all vertices and edges explicitly

vs Alternative: Compared to adjacency matrix which uses O(V^2) space, this adjacency list style is more efficient for sparse graphs

Edge Cases

Empty graph with no vertices or edges

Prints empty vertices and edges lists

DSA Java

vertices.add(v);

Adding edge where vertices do not exist yet

Vertices are automatically added before edge is created

DSA Java

addVertex(from); addVertex(to);

Edge with zero weight

Weight is shown only if greater than zero, zero means no weight displayed

DSA Java

String w = weight > 0 ? " (weight " + weight + ")" : "";

When to Use This Pattern

When a problem involves connecting points with lines that may have directions or costs, recognize it as a graph problem and use graph terminology to model it.

Common Mistakes

Mistake: Confusing directed and undirected edges by not specifying direction clearly
Fix: Always specify direction explicitly and handle undirected edges as two-way connections or special cases

Mistake: Ignoring weights or treating all edges as equal
Fix: Include weight information in edges and use it when needed for algorithms like shortest path

Summary

Graphs connect points called vertices with lines called edges that can be directed or undirected and may have weights.

Use graphs when you need to model relationships or connections between items with possible directions and costs.

The key insight is that edges can have direction and weight, changing how you traverse or analyze the graph.

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