Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a vertex in a graph?

A vertex (or node) is a fundamental part of a graph representing a point or position where edges meet or connect.

beginner

Define an edge in graph terminology.

An edge is a connection or link between two vertices in a graph. It can represent relationships or paths.

beginner

What is the difference between a directed and an undirected edge?

A directed edge has a direction from one vertex to another (like a one-way street), while an undirected edge connects two vertices without direction (like a two-way street).

beginner

What does it mean if a graph is weighted?

A weighted graph has edges that carry a value or weight, such as distance, cost, or time, representing the strength or cost of the connection.

intermediate

Can a graph have both directed and undirected edges?

Yes, such graphs are called mixed graphs, containing both directed and undirected edges depending on the relationships modeled.

What is a vertex in a graph?

A A point where edges connect

B A connection between two points

C A direction of an edge

D A weight assigned to an edge

A vertex is a point or node where edges meet in a graph.

Which type of edge has a direction?

A Mixed edge

B Weighted edge

C Undirected edge

D Directed edge

Directed edges have a direction from one vertex to another.

What does a weighted edge represent?

A A connection without direction

B A vertex in the graph

C A connection with a value like cost or distance

D An isolated node

Weighted edges carry values such as cost or distance.

In an undirected graph, edges are:

A Two-way connections

B One-way connections

C Always weighted

D Always disconnected

Undirected edges connect vertices in both directions.

What is a mixed graph?

A A graph with only weighted edges

B A graph with both directed and undirected edges

C A graph with no edges

D A graph with isolated vertices

Mixed graphs contain both directed and undirected edges.

Explain the difference between directed and undirected edges in a graph.

Think about how traffic flows on roads.

Describe what a weighted graph is and why weights might be useful.

Imagine planning a trip with distances or costs.

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