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

Recall & Review

beginner

What is a vertex in a graph?

A vertex (or node) is a fundamental unit in a graph that represents an entity or point. It is where edges connect.

beginner

Define an edge in a graph.

An edge is a connection or link between two vertices in a graph. It shows a relationship or path between them.

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). An undirected edge has no direction and connects two vertices both ways (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. They contain both directed and undirected edges connecting vertices.

What is a vertex in a graph?

A A point or node representing an entity

B A connection between two nodes

C A value assigned to an edge

D A direction of an edge

A vertex is a point or node in a graph representing an entity.

Which type of edge has a direction?

A Undirected edge

B Directed edge

C Weighted edge

D Loop edge

A directed edge has a direction from one vertex to another.

What does a weighted edge represent?

A A connection without value

B An isolated node

C A vertex in the graph

D A connection with a value like cost or distance

A weighted edge carries a value such as cost or distance.

In an undirected graph, edges are:

A Two-way connections

B One-way connections

C Always weighted

D Always loops

Undirected edges connect vertices both ways, like two-way streets.

What is a mixed graph?

A A graph with no edges

B A graph with only weighted edges

C A graph with both directed and undirected edges

D A graph with only vertices

A mixed graph contains both directed and undirected edges.

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

Think about how traffic flows on one-way and two-way streets.

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

Consider how maps show distances or costs between places.

Practice

1. In a graph, what do we call the points or nodes where edges meet?

easy

A. Vertices

B. Edges

C. Weights

D. Paths

Solution

1. Step 1: Understand graph components

   A graph consists of points called vertices and connections called edges.

2. Step 2: Identify the term for points

   The points or nodes where edges meet are called vertices.

3. Final Answer:

   Vertices -> Option A

4. Quick Check:

   Points in graph = Vertices [OK]

Hint: Vertices are the points, edges are the lines connecting them [OK]

Common Mistakes:

• Confusing edges with vertices
• Thinking weights are points
• Mixing paths with vertices

2. Which of the following is the correct way to represent a weighted edge from vertex A to vertex B with weight 5 in Python using a tuple?

easy

A. (5, A, B)

B. [A, B, 5]

C. {'A': 'B', 'weight': 5}

D. (A, B, 5)

Solution

1. Step 1: Understand tuple representation

   A weighted edge is often represented as a tuple (start_vertex, end_vertex, weight).

2. Step 2: Match the correct tuple format

   The tuple (A, B, 5) correctly shows an edge from A to B with weight 5.

3. Final Answer:

   (A, B, 5) -> Option D

4. Quick Check:

   Weighted edge tuple = (start, end, weight) [OK]

Hint: Weighted edges use (start, end, weight) tuple format [OK]

Common Mistakes:

• Using list instead of tuple
• Putting weight first
• Using dictionary instead of tuple

3. What will be the output of the following Python code snippet?

graph = { 'A': ['B', 'C'], 'B': ['C'], 'C': ['A'] }
print(len(graph['A']))

medium

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Analyze the graph dictionary

   Key 'A' has a list of neighbors ['B', 'C'], so graph['A'] is ['B', 'C'].

2. Step 2: Calculate length of neighbors list

   len(graph['A']) counts the number of neighbors, which is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Neighbors of A = 2 [OK]

Hint: Count neighbors in adjacency list for vertex [OK]

Common Mistakes:

• Counting total keys instead of neighbors
• Confusing keys with values
• Off-by-one counting errors

4. Identify the error in the following Python code that tries to create an undirected graph using adjacency lists:

graph = { 'A': ['B'], 'B': ['C'], 'C': [] }
graph['C'].append('A')

medium

A. The code is correct for undirected graph

B. Appending 'A' to 'C' creates a cycle

C. The graph is directed, not undirected

D. Missing edge from 'B' to 'A'

Solution

1. Step 1: Understand undirected graph representation

   In an undirected graph, edges go both ways, so adjacency lists must be symmetric.

2. Step 2: Check the adjacency lists

   Initially, 'A' connects to 'B', but 'B' does not connect back to 'A', so it's directed.

3. Final Answer:

   The graph is directed, not undirected -> Option C

4. Quick Check:

   Undirected graph needs two-way edges [OK]

Hint: Undirected graphs have symmetric edges in adjacency lists [OK]

Common Mistakes:

• Assuming one-way edges are undirected
• Ignoring symmetry in adjacency lists
• Confusing cycles with direction

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

graph = {
  'A': [('B', 3), ('C', 5)],
  'B': [('A', 3), ('C', 1)],
  'C': [('A', 5), ('B', 1)]
}

What is the total weight of all edges in this graph?

hard

A. 18

B. 9

C. 6

D. 3

Solution

1. Step 1: List all edges with weights

   Edges: A-B(3), A-C(5), B-C(1). Each edge appears twice because graph is undirected.

2. Step 2: Sum weights and divide by 2

   Total sum counting duplicates = 3+5+3+1+5+1 = 18. Divide by 2 to avoid double counting: 18 / 2 = 9.

3. Final Answer:

   9 -> Option B

4. Quick Check:

   Sum weights once for undirected edges [OK]

Hint: Sum all weights then halve for undirected graphs [OK]

Common Mistakes:

• Counting edges twice
• Forgetting to divide by 2
• Ignoring weights in tuples