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

Overview - Graph Terminology Vertices Edges Directed Undirected Weighted

What is it?

A graph is a way to show connections between things using points called vertices and lines called edges. Vertices are the objects or places, and edges are the links between them. Graphs can have directions on edges, meaning the connection goes one way, or no direction, meaning the connection goes both ways. Sometimes edges have weights, which are numbers showing how strong or costly the connection is.

Why it matters

Graphs help us understand and solve many real-world problems like maps, social networks, and computer networks. Without graphs, it would be hard to organize and find relationships between many connected items. They let us find shortest paths, group related items, and model complex systems easily.

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 to solve problems using graphs.

Mental Model

Core Idea

A graph is a collection of points connected by lines that can have direction and strength.

Think of it like...

Imagine a city map where intersections are points (vertices) and roads are lines (edges). Some roads only allow one-way traffic (directed), some allow two-way (undirected), and some roads are longer or have tolls (weighted).

Graph Structure:

Vertices (Points): A, B, C, D
Edges (Lines):
  A --- B (undirected)
  B -> C (directed)
  C --- D (undirected, weighted 5)

Representation:
  A
 / \
B -> C
     |
     D (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.

Think of vertices as dots on a paper. Each dot can represent a person, a city, or any item you want to connect. In code, vertices can be numbers, strings, or objects that identify these points.

Result

You can identify and list all the points in a graph, like A, B, C, and D.

Understanding vertices as simple points helps you see graphs as collections of items before worrying about connections.

2

Foundation

Edges Connect Vertices

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

Edges link two points. For example, if A and B are vertices, an edge between them means you can go from A to B or they are related. Edges can be drawn as lines connecting dots.

Result

You can visualize or list connections like A connected to B, B connected to C.

Seeing edges as connections between points builds the foundation for understanding how graphs model relationships.

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 back.

Imagine a one-way street from B to C. You can go from B to C but not from C to B unless there is another edge. In diagrams, directed edges have arrows showing direction.

Result

You understand that B -> C means travel only from B to C, not the reverse.

Knowing edges can be one-way helps model real situations like traffic flow or data transfer where direction matters.

4

Intermediate

Undirected Edges Show Two-Way Connections

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

Concept: Undirected edges connect two vertices without direction, meaning you can move or relate both ways.

Think of a two-way street between A and B. You can travel from A to B and from B to A freely. In diagrams, undirected edges are simple lines without arrows.

Result

You see that A --- B means connection both ways between A and B.

Understanding undirected edges models mutual relationships like friendships or roads without restrictions.

5

Intermediate

Weighted Edges Add Importance or Cost

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

Concept: Weighted edges have numbers showing how strong, costly, or long the connection is.

Imagine a road between C and D that is 5 miles long. The weight 5 shows this length. Weights can represent distance, cost, or time. In code, edges store these numbers alongside connections.

Result

You can represent connections like C --- D with weight 5, meaning a cost or distance of 5.

Weights let graphs model real-world measures, enabling calculations like shortest path or cheapest route.

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 different edge types to model complex systems with various connection rules.

A graph might have some roads that are one-way (directed) and others that are two-way (undirected). Some edges have weights, others don't. This flexibility helps represent real networks like transportation or communication.

Result

You can design graphs that reflect mixed real-world scenarios with different edge types and weights.

Knowing graphs can combine edge types prepares you for advanced modeling and algorithm design.

7

Expert

Implications of Edge Types on Graph Algorithms

🤔Before reading on: Do you think algorithms like shortest path work the same on directed and undirected graphs? Commit to your answer.

Concept: The type of edges affects how algorithms traverse and analyze graphs, impacting correctness and performance.

Algorithms must respect edge directions and weights. For example, shortest path algorithms consider weights and direction to find valid routes. Ignoring edge types can lead to wrong answers or infinite loops.

Result

You understand that edge properties guide algorithm choice and implementation details.

Recognizing how edge types influence algorithms helps avoid bugs and optimize solutions in real applications.

Under the Hood

Internally, a graph stores vertices as nodes in memory and edges as links between these nodes. Directed edges are stored as one-way pointers or references from one vertex to another. Undirected edges are stored as two-way links or as a single link treated symmetrically. Weighted edges store an additional value with each connection. Data structures like adjacency lists or matrices represent these efficiently for fast access.

Why designed this way?

Graphs were designed to model relationships naturally found in the world, like roads or social ties. Direction and weights add realism by capturing one-way flows and varying connection strengths. Alternatives like trees or lists lack this flexibility. The design balances simplicity with expressive power to handle many problems.

Graph Internal Structure:

Vertices: [A] [B] [C] [D]

Adjacency List Example:
A: [(B, weight=1)]
B: [(C, weight=1)]
C: [(D, weight=5)]
D: []

Directed edges point from one vertex's list to another.
Undirected edges appear in both vertices' lists.
Weights stored alongside edges.

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 a single connection internally.

Reality: Undirected edges are typically stored as two directed edges, one in each direction, to simplify traversal.

Why it matters: Failing to store both directions can cause algorithms to miss connections or behave incorrectly.

Quick: Can a graph have both directed and undirected edges at the same time? 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 relationships.

Why it matters: Assuming uniform edge types limits modeling power and can cause design errors.

Quick: Does a weighted edge always mean a longer or worse connection? Commit yes or no.

Common Belief: Higher weights always mean worse or longer connections.

Reality: Weights can represent any measure, including strength or capacity, where higher can be better.

Why it matters: Misinterpreting weights can lead to wrong algorithm choices or results.

Quick: Do directed edges always prevent cycles in a graph? Commit yes or no.

Common Belief: Directed edges mean the graph cannot have cycles.

Reality: Directed graphs can have cycles if edges form loops following directions.

Why it matters: Assuming no cycles can cause infinite loops or incorrect algorithm behavior.

Expert Zone

1

Some graph representations optimize storage by using edge lists or compressed formats depending on density.

2

Edge weights can be dynamic, changing during algorithm execution, requiring careful update strategies.

3

Directed edges can represent asymmetric relationships, which affects symmetry assumptions in algorithms.

When NOT to use

Graphs are not ideal when data is strictly hierarchical (trees) or linear (lists). For very large sparse graphs, specialized data structures like adjacency lists are better than matrices. For unweighted, undirected simple connections, simpler sets or maps may suffice.

Production Patterns

In real systems, graphs model social networks with directed follows, road maps with weighted distances, and dependency graphs with mixed edges. Algorithms like Dijkstra or BFS adapt to edge types and weights to find routes or clusters efficiently.

Connections

Network Routing Protocols

Graphs model network nodes and connections; routing algorithms use graph edges and weights to find paths.

Understanding graph edges as network links helps grasp how internet data finds efficient routes.

Social Network Analysis

Vertices represent people; edges represent friendships or follows, directed or undirected.

Knowing graph terminology clarifies how social platforms analyze connections and influence.

Project Management (PERT Charts)

Tasks are vertices; dependencies are directed edges with weights as durations.

Graph concepts help plan and optimize project timelines by modeling task order and cost.

Common Pitfalls

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

Wrong approach:

const graph = { A: ['B'], B: ['A'] }; // Treating directed edges as undirected without direction info

Correct approach:

const graph = { A: [{node: 'B', directed: true}], B: [] }; // Explicitly store direction

Root cause:

Not distinguishing edge direction causes incorrect traversal and logic errors.

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

Wrong approach:

const edges = [{from: 'A', to: 'B'}]; // No weight stored or used

Correct approach:

const edges = [{from: 'A', to: 'B', weight: 5}]; // Store and use weights

Root cause:

Overlooking weights loses important cost or distance info needed for correct solutions.

#3 Storing undirected edges only once causes missing connections.

Wrong approach:

const graph = { A: ['B'], B: [] }; // Undirected edge stored only from A to B

Correct approach:

const graph = { A: ['B'], B: ['A'] }; // Store undirected edge in both directions

Root cause:

Misunderstanding undirected edges as single links breaks symmetric traversal.

Key Takeaways

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

Directed edges have a one-way direction, while undirected edges allow two-way connections.

Weighted edges carry numbers representing cost, distance, or strength of connections.

Understanding edge types is crucial for correctly modeling problems and applying graph algorithms.

Graphs can mix edge types and weights to represent complex real-world systems effectively.