Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Python - Deep Dive

Overview - Graph Terminology Vertices Edges Directed Undirected Weighted

What is it?

A graph is a way to show connections between things. The things are called vertices or nodes. The connections between them are called edges. These edges can have directions or weights to show how they relate.

Why it matters

Graphs help us understand and solve problems where things connect, like social networks, maps, or websites. Without graphs, it would be hard to find paths, relationships, or optimize routes in many real-world systems.

Where it fits

Before learning graphs, you should know basic data structures like arrays and lists. After this, you can learn graph algorithms like searching, shortest path, and spanning trees.

Mental Model

Core Idea

A graph is a collection of points (vertices) connected by lines (edges) that can have direction and weight to represent relationships.

Think of it like...

Imagine 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).

Graph Structure:

Vertices (Nodes): V1, V2, V3, ...
Edges (Connections):
  V1 --- V2 (undirected)
  V2 -> V3 (directed)
  V3 --- V4 (weighted: 5)

Example:

  V1
  / \
 V2->V3
     |
    (5)
     V4

Build-Up - 7 Steps

1

Foundation

Understanding Vertices as Points

Concept: Vertices are the basic units or points in a graph representing objects or entities.

Think of vertices as dots or points. Each vertex can represent anything like a person, place, or thing. In code, vertices can be stored as numbers, strings, or objects.

Result

You can identify and list all the points in a graph clearly.

Understanding vertices as individual points helps you see the graph as a set of objects before worrying about connections.

2

Foundation

Edges Connect Vertices

Concept: Edges are the links or lines that connect two vertices, showing a relationship or path.

Edges connect two vertices. They can be thought of as roads between intersections. In code, edges can be pairs of vertices like (V1, V2).

Result

You can represent how points relate or connect in a graph.

Knowing edges connect vertices lets you model relationships, which is the core of graph usefulness.

3

Intermediate

Directed Edges Show One-Way Connections

🤔Before reading on: do you think a directed edge means you can travel both ways or only one way? Commit to your answer.

Concept: Directed edges have a direction, meaning the connection goes from one vertex to another but not necessarily back.

A directed edge is like a one-way street. If there is an edge from V1 to V2, you can go from V1 to V2 but not from V2 to V1 unless there is another edge.

Result

You can model situations where relationships are not mutual, like following someone on social media.

Understanding direction in edges allows you to represent asymmetric relationships, which are common in real systems.

4

Intermediate

Undirected Edges Show Two-Way Connections

🤔Before reading on: do you think undirected edges allow movement both ways or just one? Commit to your answer.

Concept: Undirected edges connect two vertices without direction, meaning the connection works both ways.

An undirected edge is like a two-way street. If V1 and V2 are connected, you can go from V1 to V2 and from V2 to V1 freely.

Result

You can model mutual relationships like friendships or roads that allow travel both ways.

Knowing undirected edges represent mutual connections helps you choose the right graph type for your problem.

5

Intermediate

Weighted Edges Add Importance or Cost

🤔Before reading on: do you think weights on edges represent quantity, cost, or something else? Commit to your answer.

Concept: Weighted edges have numbers attached that show cost, distance, or strength of the connection.

Weights can represent things like distance between cities, cost of travel, or strength of a friendship. For example, an edge with weight 5 means it costs 5 units to travel that edge.

Result

You can model real-world problems where connections have different values or costs.

Understanding weights lets you solve optimization problems like shortest path or cheapest route.

6

Advanced

Combining Directed and Weighted Edges

🤔Before reading on: can edges be both directed and weighted at the same time? Commit to your answer.

Concept: Edges can be both directed and weighted, meaning they have a direction and a cost or value.

A directed weighted edge means you can go one way and the cost to go that way is the weight. For example, a road that only goes from V1 to V2 and costs 10 units to travel.

Result

You can model complex real-world networks like traffic systems with one-way streets and varying distances.

Knowing edges can have multiple properties allows you to build detailed and accurate graph models.

7

Expert

Graph Terminology in Data Structures

🤔Before reading on: do you think graphs are stored only as lists of edges or can there be other ways? Commit to your answer.

Concept: Graphs can be stored in different ways like adjacency lists or matrices, each affecting performance and use cases.

An adjacency list stores each vertex with a list of connected vertices and edge info. An adjacency matrix uses a 2D grid to show connections. Choice depends on graph size and operations needed.

Result

You can choose the best storage method for your graph problem.

Understanding storage methods helps optimize graph algorithms and memory use in real applications.

Under the Hood

Internally, a graph is stored as collections of vertices and edges. Vertices are stored as unique identifiers. Edges are stored as pairs of vertices, optionally with direction and weight. Data structures like adjacency lists use arrays or linked lists to keep track of neighbors, while adjacency matrices use 2D arrays to mark connections. This structure allows efficient traversal and querying of relationships.

Why designed this way?

Graphs were designed to model relationships naturally and flexibly. Using vertices and edges separates objects from their connections, making it easy to represent many real-world problems. Directed and weighted edges add expressiveness for asymmetric and valued relationships. Different storage methods balance speed and memory depending on graph density.

Graph Internal Structure:

┌─────────┐      ┌───────────────┐
│ Vertices│─────▶│Adjacency List │
│ (Nodes) │      │ or Matrix     │
└─────────┘      └───────────────┘
      │                  │
      │                  │
      ▼                  ▼
  Unique IDs         Edge info:
                      - Connected vertex
                      - Direction
                      - Weight

Myth Busters - 4 Common Misconceptions

Quick: Does an undirected edge mean you must have two edges, one each way? Commit yes or no.

Common Belief: An undirected edge is stored as two directed edges, one in each direction.

Reality: An undirected edge is stored as a single connection without direction, not two edges.

Why it matters: Storing undirected edges as two directed edges doubles memory and can cause confusion in algorithms expecting undirected graphs.

Quick: Can a graph have edges that connect a vertex to itself? Commit yes or no.

Common Belief: Graphs cannot have edges that start and end at the same vertex (no self-loops).

Reality: Graphs can have self-loops where an edge connects a vertex to itself.

Why it matters: Ignoring self-loops can cause errors in algorithms that assume simple graphs, missing important cases like feedback loops.

Quick: Does the weight on an edge always represent distance? Commit yes or no.

Common Belief: Edge weights always represent physical distance or length.

Reality: Weights can represent any value like cost, time, capacity, or strength, not just distance.

Why it matters: Assuming weights are distances limits the use of graphs in diverse problems like network flow or social influence.

Quick: Is a directed edge always one-way with no return path? Commit yes or no.

Common Belief: If an edge is directed, you cannot go back the other way unless another edge exists.

Reality: This is true, but sometimes graphs model bidirectional edges by having two directed edges in opposite directions.

Why it matters: Misunderstanding this can lead to incorrect assumptions about connectivity and pathfinding.

Expert Zone

1

Directed edges can represent asymmetric relationships but may require careful handling in traversal algorithms to avoid missing reachable nodes.

2

Weighted edges can have negative weights, which complicates shortest path algorithms and requires special algorithms like Bellman-Ford.

3

Graph storage choice (adjacency list vs matrix) greatly impacts performance; sparse graphs favor lists, dense graphs favor matrices.

When NOT to use

Graphs are not ideal when relationships are simple or fixed, like linear sequences or trees where specialized structures are more efficient. For very large graphs with dynamic changes, specialized graph databases or streaming algorithms may be better.

Production Patterns

In production, graphs model social networks, recommendation systems, routing in maps, and dependency management. Weighted directed graphs are common in traffic navigation apps, while undirected graphs appear in friendship networks.

Connections

Network Theory

Graphs are the mathematical foundation of network theory.

Understanding graph terminology helps grasp how networks like the internet or social media are structured and analyzed.

Linear Algebra

Graphs can be represented by matrices, linking to linear algebra concepts.

Knowing graph matrices connects graph problems to matrix operations, enabling advanced algorithms like spectral clustering.

Urban Planning

Graphs model city layouts and traffic flow in urban planning.

Recognizing graphs in city maps helps apply graph algorithms to optimize routes and infrastructure.

Common Pitfalls

#1 Confusing directed and undirected edges leads to wrong graph representation.

Wrong approach:

edges = [(1, 2), (2, 1)] # Treating undirected edge as two directed edges without clarity

Correct approach:

edges = [(1, 2)] # Single undirected edge between 1 and 2

Root cause:

Misunderstanding that undirected edges are bidirectional by nature and do not need two entries.

#2 Ignoring weights when they matter causes incorrect algorithm results.

Wrong approach:

edges = [(1, 2), (2, 3)] # No weights given, but problem requires cost

Correct approach:

edges = [(1, 2, 5), (2, 3, 10)] # Including weights for accurate modeling

Root cause:

Not recognizing the importance of weights in representing real-world costs or distances.

#3 Using adjacency matrix for very large sparse graphs wastes memory.

Wrong approach:

matrix = [[0]*10000 for _ in range(10000)] # Large matrix mostly zeros

Correct approach:

adj_list = {vertex: [] for vertex in range(10000)} # Efficient adjacency list

Root cause:

Not understanding the trade-offs between adjacency matrix and list for graph storage.

Key Takeaways

Graphs consist of vertices (points) and edges (connections) that can be directed or undirected.

Directed edges show one-way relationships, while undirected edges show mutual connections.

Weighted edges add values like cost or distance to connections, enabling richer modeling.

Choosing the right graph representation and understanding edge properties is crucial for solving real problems.

Misunderstanding graph basics leads to errors in algorithms and inefficient solutions.

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