Graph Terminology Vertices Edges Directed Undirected Weighted in DSA C++ - 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. Edges can have directions (directed) or not (undirected), and they can also have weights that show how strong or costly the connection is.

Why it matters

Graphs help us solve many real problems like finding the shortest path on maps, organizing social networks, or managing tasks with dependencies. Without understanding graph terms, it would be hard to describe or work with these connections clearly and efficiently.

Where it fits

Before learning graph terminology, 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 vertices and roads are edges. Some roads go one way (directed), some both ways (undirected), and some roads are longer or have tolls (weighted).

Graph Structure:

Vertices (Nodes): O   O   O   O
Edges (Connections):
  - Undirected: O --- O
  - Directed:   O -> O
  - Weighted:   O --5--> O

Legend:
O = Vertex
--- = Undirected edge
-> = Directed edge
--5--> = Edge with weight 5

Build-Up - 7 Steps

1

Foundation

Understanding Vertices as Points

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

Vertices (also called nodes) are like dots on a paper. Each vertex can represent anything: a city, a person, or a computer. In code, vertices are often stored as numbers or labels.

Result

You can identify and refer to each point in a graph clearly.

Understanding vertices as individual points helps you see graphs as collections of objects before worrying about their connections.

2

Foundation

Edges Connect Vertices

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

Edges connect two vertices. If you think of vertices as cities, edges are the roads between them. Edges can be shown as lines connecting dots. In code, edges can be pairs of vertices.

Result

You can represent relationships or connections between objects.

Knowing edges connect vertices lets you model real-world relationships like friendships or routes.

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. It points from a start vertex to an end vertex. For example, if vertex A points to B, you can go from A to B but not from B to A unless there is another edge back.

Result

You can model one-way relationships like following on social media or one-way roads.

Understanding direction in edges helps model asymmetric relationships, which are common in real systems.

4

Intermediate

Undirected Edges Show Two-Way Connections

🤔Before reading on: does an undirected edge allow travel both ways or just one? Commit to your answer.

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

An undirected edge is like a two-way street or a friendship where both sides are connected equally. If vertex A and B are connected by an undirected edge, you can go from A to B and from B to A.

Result

You can represent mutual relationships like friendships or roads without direction.

Knowing undirected edges represent two-way connections helps you model symmetric relationships simply.

5

Intermediate

Weighted Edges Add Importance or Cost

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

Concept: Weighted edges have numbers (weights) that show how strong, costly, or long the connection is.

Weights are numbers attached to edges. For example, a road might have a weight showing its length or toll cost. In code, weights are stored alongside edges. This helps algorithms find shortest or cheapest paths.

Result

You can measure and compare connections, not just know if they exist.

Understanding weights lets you solve real problems like finding the fastest route or cheapest option.

6

Advanced

Combining Directed, Undirected, and Weighted Edges

🤔Before reading on: can a graph have both directed and undirected edges at the same time? Commit to your answer.

Concept: Graphs can mix directed, undirected, and weighted edges to model complex relationships.

Some graphs have only directed edges, some only undirected, and some mix both. Weights can be added to any edge type. For example, a social network might have undirected friendship edges and directed follower edges, each with weights showing interaction strength.

Result

You can model very rich and realistic networks.

Knowing graphs can combine these edge types helps you understand the flexibility and power of graph models.

7

Expert

Graph Representation Choices Affect Performance

🤔Before reading on: do you think the way you store vertices and edges affects how fast graph algorithms run? Commit to your answer.

Concept: How you represent graphs in code (like adjacency lists or matrices) depends on edge types and weights and affects efficiency.

Graphs can be stored as adjacency lists (each vertex stores connected vertices) or adjacency matrices (a 2D grid showing connections). Directed and weighted edges require careful representation. For example, weighted directed graphs often use adjacency lists with pairs (neighbor, weight). Choosing the right representation impacts memory use and speed of algorithms.

Result

You can write faster and more memory-efficient graph programs.

Understanding representation tradeoffs is key to building scalable graph solutions in real systems.

Under the Hood

Internally, a graph stores vertices as unique identifiers and edges as pairs or triples (for weighted edges) linking these identifiers. Directed edges store order (from, to), while undirected edges treat connections symmetrically. Weighted edges add a numeric value to each connection. Data structures like adjacency lists use arrays or linked lists to keep track of neighbors, enabling efficient traversal and updates.

Why designed this way?

Graphs were designed to model relationships naturally found in many fields like geography, social sciences, and computer networks. The distinction between directed and undirected edges reflects real-world asymmetry or symmetry in connections. Weights allow quantifying relationships, making graphs versatile for optimization problems. Early graph theory formalized these concepts to unify diverse problems under one framework.

Graph Internal Structure:

┌─────────────┐
│  Vertices   │
│  [A, B, C]  │
└─────┬───────┘
      │
      ▼
┌─────────────────────────────┐
│       Edges Storage          │
│                             │
│ Directed: (A -> B), (B -> C)│
│ Undirected: (A -- C)         │
│ Weighted: (A --5--> B)       │
└─────────────┬───────────────┘
              │
              ▼
┌─────────────────────────────┐
│  Adjacency List or Matrix   │
│  Efficient lookup & updates │
└─────────────────────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does an undirected edge mean you must store two edges internally? Commit yes or no.

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

Reality: Undirected edges are often stored once, with data structures designed to treat the connection symmetrically without duplicating edges.

Why it matters: Storing two edges wastes memory and can cause bugs if updates are not synchronized.

Quick: Do weighted edges always represent distance? Commit yes or no.

Common Belief: Weights on edges always mean physical distance between vertices.

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

Why it matters: Assuming weights mean distance limits the use of graphs in many applications like network bandwidth or social influence.

Quick: Can a graph have both directed and undirected edges mixed? Commit yes or no.

Common Belief: Graphs must be either fully directed or fully undirected, not both.

Reality: Graphs can mix directed and undirected edges to model complex systems.

Why it matters: Believing this limits modeling real-world networks like social media where both types coexist.

Quick: Does the number of vertices always equal the number of edges? Commit yes or no.

Common Belief: The number of vertices and edges in a graph are always the same or similar.

Reality: Vertices and edges are independent; a graph can have many vertices with few edges or vice versa.

Why it matters: Misunderstanding this leads to wrong assumptions about graph density and algorithm performance.

Expert Zone

1

In weighted graphs, zero or negative weights can drastically change algorithm choices and correctness.

2

Directed graphs can have cycles or be acyclic; recognizing this affects traversal and topological sorting.

3

Edge representation impacts parallel processing of graphs in distributed systems.

When NOT to use

Graphs are not ideal when relationships are simple and fixed, where arrays or hash maps suffice. For very large sparse graphs, specialized data structures like compressed sparse row (CSR) are better. For dynamic graphs with frequent changes, incremental or streaming graph algorithms are preferred.

Production Patterns

In production, graphs model social networks with weighted follower edges, road networks with directed weighted edges for traffic, and dependency graphs in build systems. Efficient adjacency lists with hash maps or balanced trees are common. Graph databases use these concepts to query relationships quickly.

Connections

Network Routing Protocols

Graphs model the network topology where vertices are routers and edges are connections.

Understanding graph edges and weights helps grasp how routing protocols find shortest or least-cost paths.

Project Management (PERT Charts)

Directed weighted graphs represent tasks (vertices) and dependencies with durations (weights).

Knowing graph terminology clarifies how project timelines and critical paths are calculated.

Neural Networks in AI

Neural networks can be seen as directed weighted graphs where vertices are neurons and edges are weighted connections.

Recognizing this connection helps understand how information flows and is weighted in AI models.

Common Pitfalls

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

Wrong approach:

Using undirected edges to represent one-way streets:
Edges: (A -- B)
Assuming travel possible both ways.

Correct approach:

Use directed edges for one-way streets:
Edges: (A -> B)
Travel only from A to B.

Root cause:

Misunderstanding edge direction causes incorrect representation of relationships.

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

Wrong approach:

Treating all edges equally in shortest path:
Edges: (A -> B), (B -> C)
Ignoring weights like distance or cost.

Correct approach:

Include weights in calculations:
Edges: (A --5--> B), (B --2--> C)
Use weighted shortest path algorithms.

Root cause:

Overlooking edge weights leads to inaccurate modeling of real costs.

#3 Storing undirected edges as two directed edges without synchronization.

Wrong approach:

Edges: (A -> B) and (B -> A) stored separately without update consistency.

Correct approach:

Store undirected edge once and treat symmetrically in code.

Root cause:

Not recognizing undirected edges as single connections causes data inconsistency.

Key Takeaways

Graphs consist of vertices (points) connected by edges (lines) that can be directed or undirected.

Directed edges show one-way connections, while undirected edges show two-way connections.

Weights on edges add meaning like cost or distance, enabling richer problem solving.

Choosing the right graph representation affects how efficiently you can work with graphs.

Understanding these terms is essential before learning graph algorithms and applying graphs in real-world problems.

Practice

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

easy

A. Edges

B. Vertices

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 B

4. Quick Check:

   Points in graph = Vertices [OK]

Hint: Vertices are the dots, 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 declare an undirected graph using adjacency list in C++?

easy

A. vector graph; graph.resize(5); // Undirected graph

B. vector> graph[5]; // Weighted graph

C. int graph[5][5]; // Undirected graph

D. vector<int> graph(5); // Undirected graph

Solution

1. Step 1: Understand adjacency list declaration

   An adjacency list for a graph with 5 vertices can be declared as a vector of vectors and resized to 5.

2. Step 2: Check options for correct syntax

   vector graph; graph.resize(5); // Undirected graph uses vector graph; graph.resize(5); which is correct for undirected graph adjacency list.

3. Final Answer:

   vector graph; graph.resize(5); // Undirected graph -> Option A

4. Quick Check:

   Correct adjacency list syntax = vector graph; graph.resize(5); // Undirected graph [OK]

Hint: Use vector of vectors and resize for adjacency list [OK]

Common Mistakes:

• Using fixed size array without resize
• Confusing weighted graph syntax
• Using vector<int> graph(5) which is vector of ints, not list

3. What is the output of the following C++ code snippet that creates a weighted directed graph and prints the weight of edge from vertex 1 to 2?

vector> graph[3];
graph[1].push_back({2, 10});
graph[2].push_back({1, 5});
for(auto &edge : graph[1]) {
    if(edge.first == 2) {
        cout << edge.second << endl;
    }
}

medium

A. 0

B. 5

C. 10

D. Compilation error

Solution

1. Step 1: Understand graph construction

   graph[1] has an edge to vertex 2 with weight 10; graph[2] has edge to 1 with weight 5.

2. Step 2: Trace the loop output

   The loop checks edges from vertex 1; finds edge to 2 and prints weight 10.

3. Final Answer:

   10 -> Option C

4. Quick Check:

   Weight from 1 to 2 = 10 [OK]

Hint: Check which vertex's edges are printed and their weights [OK]

Common Mistakes:

• Confusing edge direction
• Printing weight from wrong vertex
• Assuming undirected graph

4. Identify the error in the following code snippet that tries to add an edge to an undirected weighted graph:

vector> graph[3];
graph[0].push_back({1, 4});
graph[1].push_back(0, 4);

medium

A. Using vector instead of list

B. Graph size is too small

C. Edge weight missing

D. Incorrect syntax in push_back for second edge

Solution

1. Step 1: Check push_back usage

   push_back expects a single argument; graph[1].push_back(0, 4) is invalid syntax.

2. Step 2: Identify correct syntax

   It should be graph[1].push_back({0, 4}); to add a pair.

3. Final Answer:

   Incorrect syntax in push_back for second edge -> Option D

4. Quick Check:

   push_back needs one argument (pair) [OK]

Hint: push_back takes one argument; use braces for pairs [OK]

Common Mistakes:

• Passing multiple arguments to push_back
• Not using braces for pair
• Confusing vector size with error

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

vector> graph[4];
graph[0].push_back({1, 3});
graph[1].push_back({0, 3});
graph[1].push_back({2, 5});
graph[2].push_back({1, 5});
graph[2].push_back({3, 7});
graph[3].push_back({2, 7});

How would you add an edge between vertex 0 and vertex 3 with weight 2 correctly?

hard

A. graph[0].push_back({3, 2}); graph[3].push_back({0, 2});

B. graph[0].push_back({3, 2});

C. graph[3].push_back({0, 2});

D. graph.push_back({0, 3, 2});

Solution

1. Step 1: Understand undirected edge addition

   In undirected graphs, edges must be added in both directions to represent connection.

2. Step 2: Add edge in both adjacency lists

   Add {3, 2} to graph[0] and {0, 2} to graph[3] to represent the edge with weight 2.

3. Final Answer:

   graph[0].push_back({3, 2}); graph[3].push_back({0, 2}); -> Option A

4. Quick Check:

   Undirected edge = add both directions [OK]

Hint: Add edges both ways for undirected weighted graph [OK]

Common Mistakes:

• Adding edge only one way
• Wrong syntax for push_back
• Trying to push triple instead of pair