Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Javascript

Mental Model

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

Analogy: Think of a city map where intersections are vertices and roads are 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: Identify vertices as points A, B, C, D

Vertices: [A] [B] [C] [D]

Why: Vertices are the main points or nodes in the graph

Step 2: Add directed edge from A to B

A -> B
Vertices: [A] [B] [C] [D]

Why: Directed edge means connection goes only from A to B

Step 3: Add undirected edge between B and C

A -> B
B ↔ C
Vertices: [A] [B] [C] [D]

Why: Undirected edge means connection goes both ways between B and C

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

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

Why: Weighted edge shows cost or distance; direction matters from C to D

Result:

Final graph:
A -> B
B ↔ C
C -> D (weight 5)
Vertices: [A] [B] [C] [D]

Annotated Code

DSA Javascript

class Graph {
  constructor() {
    this.vertices = new Set();
    this.edges = new Map(); // key: vertex, value: array of {to, directed, weight}
  }

  addVertex(v) {
    this.vertices.add(v);
    if (!this.edges.has(v)) {
      this.edges.set(v, []);
    }
  }

  addEdge(from, to, directed = true, weight = null) {
    this.addVertex(from);
    this.addVertex(to);
    this.edges.get(from).push({ to, directed, weight });
    if (!directed) {
      this.edges.get(to).push({ to: from, directed, weight });
    }
  }

  printGraph() {
    for (const v of this.vertices) {
      const conns = this.edges.get(v).map(e => {
        const w = e.weight !== null ? ` (weight ${e.weight})` : '';
        const arrow = e.directed ? '->' : '↔';
        return `${arrow} ${e.to}${w}`;
      }).join(' ');
      console.log(`${v} ${conns}`);
    }
  }
}

// Driver code
const graph = new Graph();
graph.addEdge('A', 'B', true); // directed A->B
graph.addEdge('B', 'C', false); // undirected B<->C
graph.addEdge('C', 'D', true, 5); // directed C->D with weight 5

graph.printGraph();

this.edges.get(from).push({ to, directed, weight });

Add edge from 'from' vertex to 'to' vertex with direction and weight

if (!directed) { this.edges.get(to).push({ to: from, directed, weight }); }

For undirected edges, add reverse edge as well

for (const v of this.vertices) { ... console.log(...) }

Print each vertex and its connected edges with direction and weight

Output

A -> B

B -> C ↔ A

C -> D (weight 5) ↔ B

D

Complexity Analysis

Time: O(V + E) because we add vertices and edges once and print all connections

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

vs Alternative: Compared to adjacency matrix (O(V^2) space), adjacency list used here is more efficient for sparse graphs

Edge Cases

Empty graph with no vertices or edges

Prints nothing, no errors

DSA Javascript

for (const v of this.vertices) { ... }

Graph with single vertex and no edges

Prints vertex with no connections

DSA Javascript

this.edges.get(v).map(...) handles empty edge list

Adding undirected edge between same vertex (self-loop)

Edge added twice pointing to same vertex, representing self-loop

DSA Javascript

if (!directed) { this.edges.get(to).push(...) }

When to Use This Pattern

When a problem involves connecting points with possible directions and costs, recognize it as a graph problem and use graph terminology to model it.

Common Mistakes

Mistake: Confusing directed and undirected edges by not adding reverse edge for undirected
Fix: Always add reverse edge in adjacency list when edge is undirected

Mistake: Ignoring weights on edges when they affect path cost
Fix: Include weight property and use it in algorithms that consider cost

Summary

Graphs connect points (vertices) with lines (edges) that can have direction and weight.

Use graphs to model networks where connections and their directions or costs matter.

Remember edges can be one-way (directed) or two-way (undirected), and weights show cost or distance.

Practice

1. In graph terminology, what is a vertex?

easy

A. A line connecting two nodes

B. A point or node in the graph where edges meet

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, not vertices.

3. Final Answer:

   A point or node in the graph where edges meet -> Option B

4. Quick Check:

   Vertex = node/point [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 represent a directed edge from vertex A to vertex B in JavaScript adjacency list?

easy

A. { A: ['B'], B: ['A'] }

B. { A: [], B: ['A'] }

C. { A: ['B'], B: [] }

D. { A: [], B: [] }

Solution

1. Step 1: Understand adjacency list for directed edges

   In a directed graph, an edge from A to B means B is in A's adjacency list.

2. Step 2: Check each option's adjacency list

   { A: ['B'], B: [] } shows B in A's list and empty list for B, correctly representing A -> B.

3. Final Answer:

   { A: ['B'], B: [] } -> Option C

4. Quick Check:

   Directed edge A->B means B in A's list [OK]

Hint: Directed edge means target vertex in source's adjacency list [OK]

Common Mistakes:

• Adding reverse edge for directed graph
• Leaving adjacency list empty for source vertex
• Confusing undirected with directed representation

3. What will be the output of the following JavaScript code representing an undirected weighted graph adjacency list?

const graph = {
  A: [{ node: 'B', weight: 3 }, { node: 'C', weight: 5 }],
  B: [{ node: 'A', weight: 3 }],
  C: [{ node: 'A', weight: 5 }]
};

console.log(graph['A'][1].weight);

medium

A. 5

B. Error

C. undefined

D. 3

Solution

1. Step 1: Access the adjacency list for vertex 'A'

   graph['A'] is an array with two objects: first with weight 3, second with weight 5.

2. Step 2: Access the second element's weight

   graph['A'][1] is the second object { node: 'C', weight: 5 }, so weight is 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   graph['A'][1].weight = 5 [OK]

Hint: Index 1 means second element; check its weight property [OK]

Common Mistakes:

• Confusing index 0 and 1
• Accessing weight on wrong node
• Assuming undirected means no weights

4. Identify the error in this JavaScript code snippet representing a directed graph adjacency list:

const graph = {
  A: ['B'],
  B: ['C'],
  C: ['A']
};

// Add edge from B to A
graph.B.push('A');

// Add edge from C to B
graph.C.push('B');

console.log(graph);

medium

A. Edges added duplicate existing edges incorrectly

B. Edges added create a cycle, which is invalid

C. The graph object is mutated incorrectly causing unexpected behavior

D. No error, code correctly adds edges

Solution

1. Step 1: Check initial graph structure

   Graph has directed edges A->B, B->C, C->A forming a cycle, which is allowed.

2. Step 2: Verify edge additions

   Adding B->A and C->B edges extends the graph; push method correctly mutates adjacency lists.

3. Final Answer:

   No error, code correctly adds edges -> Option D

4. Quick Check:

   push adds edges correctly; cycles allowed [OK]

Hint: push adds edges; cycles allowed in directed graphs [OK]

Common Mistakes:

• Thinking cycles are invalid in directed graphs
• Assuming push does not mutate arrays
• Confusing undirected with directed edge additions

5. You have an undirected weighted graph represented as an adjacency list in JavaScript:

const graph = {
  A: [{ node: 'B', weight: 2 }, { node: 'C', weight: 4 }],
  B: [{ node: 'A', weight: 2 }, { node: 'C', weight: 1 }],
  C: [{ node: 'A', weight: 4 }, { node: 'B', weight: 1 }]
};

Which of the following statements is true about the edge weights?

hard

A. Weights are symmetric; weight from A to B equals weight from B to A

B. Weights differ for edges in opposite directions

C. Weights are ignored in undirected graphs

D. Weights must be zero for undirected edges

Solution

1. Step 1: Understand undirected weighted graph property

   In undirected graphs, edges have no direction, so weights between two vertices are equal both ways.

2. Step 2: Check given adjacency lists for symmetry

   Weight from A to B is 2, and from B to A is also 2; similarly for other edges.

3. Final Answer:

   Weights are symmetric; weight from A to B equals weight from B to A -> Option A

4. Quick Check:

   Undirected edge weights are symmetric [OK]

Hint: Undirected edges have equal weights both ways [OK]

Common Mistakes:

• Assuming weights differ by direction in undirected graphs
• Ignoring weights in undirected graphs
• Thinking weights must be zero