Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Javascript - Execution Trace

Concept Flow - Graph Terminology Vertices Edges Directed Undirected Weighted

Start: Define Graph

↓

Identify Vertices (Nodes)

↓

Identify Edges (Connections)

↓

Check Edge Type

↓

Directed

↓

Check Weight

↓

Weighted

↓

Graph Fully Defined

This flow shows how a graph is built by defining nodes (vertices), connections (edges), then classifying edges as directed or undirected, and weighted or unweighted.

Execution Sample

DSA Javascript

const graph = {
  vertices: ['A', 'B', 'C'],
  edges: [
    {from: 'A', to: 'B', directed: true, weight: 5},
    {from: 'B', to: 'C', directed: false}
  ]
};

Defines a graph with 3 vertices and 2 edges, one directed with weight, one undirected without weight.

Execution Table

Step	Operation	Vertices	Edges	Edge Type	Weight	Visual State
1	Define vertices	['A', 'B', 'C']	[]	-	-	Graph with nodes A, B, C; no edges yet
2	Add edge from A to B	['A', 'B', 'C']	[A->B]	Directed	5	A → B (weight 5)
3	Add edge from B to C	['A', 'B', 'C']	[A->B, B--C]	Mixed	Mixed	A → B (5), B — C (no weight)
4	Graph complete	['A', 'B', 'C']	[A->B, B--C]	Mixed	Mixed	Graph with directed weighted and undirected unweighted edges

💡 All vertices and edges defined with their types and weights

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
vertices	[]	['A', 'B', 'C']	['A', 'B', 'C']	['A', 'B', 'C']	['A', 'B', 'C']
edges	[]	[]	[{from:'A',to:'B',directed:true,weight:5}]	[{from:'A',to:'B',directed:true,weight:5},{from:'B',to:'C',directed:false}]	[{from:'A',to:'B',directed:true,weight:5},{from:'B',to:'C',directed:false}]
edge_types	N/A	N/A	['Directed']	['Directed','Undirected']	['Directed','Undirected']
weights	N/A	N/A	[5]	[5, None]	[5, None]

Key Moments - 3 Insights

Why do we say an edge is directed or undirected?

Because a directed edge has a clear start and end (like A → B), while an undirected edge connects two vertices both ways (like B — C). See execution_table steps 2 and 3.

What does it mean if an edge has a weight?

Weight is a number showing cost or distance on that edge. In step 2, edge A→B has weight 5, meaning it carries a value, unlike the edge in step 3 which has no weight.

Can a graph have both directed and undirected edges?

Yes, as shown in step 4, the graph has mixed edges: one directed weighted and one undirected unweighted.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what type of edge is added?

A Weighted but undirected

B Undirected

C Directed

D No edge added

💡 Hint

Check the 'Edge Type' column at step 2 in execution_table

At which step does the graph first include an undirected edge?

A Step 3

B Step 2

C Step 1

D Step 4

💡 Hint

Look at the 'Edge Type' column and 'Edges' column in execution_table

If the edge from B to C had a weight of 3, how would the 'weights' variable change after step 3?

A [5, None]

B [5, 3]

C [3, 5]

D [None, None]

💡 Hint

Check variable_tracker 'weights' row after step 3

Concept Snapshot

Graph = collection of vertices (nodes) and edges (connections).
Edges can be directed (one-way) or undirected (two-way).
Edges may have weights (numbers) or be unweighted.
Graphs can mix directed and undirected edges.
Vertices are unique points; edges link them.
Weighted edges represent cost or distance.

Full Transcript

A graph is made of vertices, which are points or nodes, and edges, which connect these points. Edges can be directed, meaning they go one way, or undirected, meaning they connect both ways. Some edges have weights, which are numbers showing cost or distance. A graph can have both directed and undirected edges, and some edges may have weights while others do not. This example shows a graph with three vertices A, B, and C, with one directed weighted edge from A to B, and one undirected unweighted edge between B and C.

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