Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Javascript - 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 items or spots, and edges are the links between them. Graphs can have directions on edges, meaning the connection goes one way, or be undirected, 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 model relationships or paths between objects clearly. They let us find shortest routes, detect groups, or understand how things connect, which is crucial in technology and daily life.

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 complex problems.

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 are one-way (directed), some two-way (undirected), and some roads take longer to travel (weighted).

Graph Structure:

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

Example:

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

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 or points. Each vertex can represent anything like a person, city, or computer. In code, vertices can be stored as numbers, strings, or objects. For example, vertices = ['A', 'B', 'C'] means three points named A, B, and C.

Result

Vertices represent the 'things' or 'places' in a graph.

Understanding vertices as individual points helps you see graphs as collections of objects 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 vertices. For example, an edge between A and B means A is connected to B. Edges can be stored as pairs like (A, B). In code, edges = [['A', 'B'], ['B', 'C']] means A connects to B, and B connects to C.

Result

Edges define how vertices relate or connect to each other.

Seeing edges as connections between points helps you understand the structure and relationships in a graph.

3

Intermediate

Directed vs Undirected Edges

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

Concept: Edges can have direction, meaning the connection goes one way (directed) or both ways (undirected).

In a directed graph, edges have arrows showing direction, like A -> B means from A to B only. In an undirected graph, edges have no arrows, so A -- B means A connects to B and B connects to A equally. This affects how you travel or search in the graph.

Result

Directed edges show one-way connections; undirected edges show two-way connections.

Knowing edge direction changes how you think about movement or flow in a graph, which is key for algorithms.

4

Intermediate

Weighted Edges Add Costs

🤔Before reading on: do you think weights on edges represent strength or number of connections? Commit to your answer.

Concept: Edges can have weights, numbers that show cost, distance, or strength of the connection.

A weighted edge has a number attached, like A --(3)-- B means the connection from A to B costs 3 units. Weights help find shortest paths or cheapest routes. In code, edges can be stored as triples: ['A', 'B', 3].

Result

Weights add meaning to edges beyond just connection, enabling optimization.

Understanding weights lets you solve real problems like finding fastest or cheapest routes, not just if a path exists.

5

Intermediate

Representing Graphs in Code

🤔Before reading on: do you think adjacency lists or matrices use less memory for sparse graphs? Commit to your answer.

Concept: Graphs can be stored in different ways in code, mainly adjacency lists or adjacency matrices.

An adjacency list stores each vertex with a list of connected vertices and weights if any. For example: { A: [{node: 'B', weight: 3}], B: [{node: 'C', weight: 1}], C: [] } An adjacency matrix is a 2D array where rows and columns represent vertices, and cells show edge weights or 0 if no edge.

Result

Different storage methods affect memory use and speed of graph operations.

Knowing graph representations helps you choose the right structure for your problem size and type.

6

Advanced

Directed Weighted Graphs in Practice

🤔Before reading on: do you think a directed weighted graph can have cycles? Commit to your answer.

Concept: Directed weighted graphs combine direction and weights, allowing complex modeling like traffic flow or task scheduling.

In directed weighted graphs, edges have arrows and weights. For example, A -> B (weight 5) means going from A to B costs 5. These graphs can have cycles (loops), which affect algorithms like shortest path. Detecting and handling cycles is important in such graphs.

Result

Directed weighted graphs model real-world systems with direction and cost, but cycles add complexity.

Understanding cycles and weights in directed graphs prepares you for advanced algorithms and real-world problems.

7

Expert

Edge Cases and Graph Terminology Nuances

🤔Before reading on: do you think a graph must have edges to be valid? Commit to your answer.

Concept: Graphs can have isolated vertices, self-loops, and multiple edges between the same vertices, which affect terminology and algorithms.

An isolated vertex has no edges. A self-loop is an edge from a vertex to itself. Multigraphs allow multiple edges between the same vertices. These cases change how algorithms behave and how we define connectivity or paths.

Result

Graph terminology covers special cases that impact graph behavior and algorithm design.

Knowing these nuances prevents mistakes in graph modeling and algorithm application in complex scenarios.

Under the Hood

Internally, graphs are stored as collections of vertices and edges. Vertices are stored as nodes or keys, and edges as references or links between these nodes. Directed edges store direction by linking from one vertex to another specifically. Weighted edges store extra data (numbers) alongside the connection. This structure allows efficient traversal and querying of relationships.

Why designed this way?

Graphs were designed to model relationships naturally and flexibly. Direction and weights add expressiveness to represent real-world scenarios like one-way streets or distances. Alternatives like trees or lists are too limited for complex connections, so graphs provide a general framework.

Graph Internal Structure:

┌─────────┐      ┌─────────┐
│ Vertex  │─────▶│ Vertex  │
│   A     │      │   B     │
└─────────┘      └─────────┘
     │               ▲
     │               │
     └────(weight=3)─┘

Storage:
Vertices: ['A', 'B']
Edges: [{from: 'A', to: 'B', weight: 3}]

Myth Busters - 4 Common Misconceptions

Quick: Does an undirected edge mean you can only travel one way? Commit yes or no.

Common Belief: Undirected edges mean you can only go one way between vertices.

Reality: Undirected edges mean the connection goes both ways equally; you can travel from either vertex to the other.

Why it matters: Misunderstanding this leads to wrong assumptions about connectivity and pathfinding in graphs.

Quick: Can a graph have vertices without any edges? Commit yes or no.

Common Belief: A graph must have edges connecting all vertices; isolated vertices don't count.

Reality: Graphs can have isolated vertices with no edges; these are still valid vertices in the graph.

Why it matters: Ignoring isolated vertices can cause errors in algorithms that assume full connectivity.

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 cost, like time, money, or strength, not just distance.

Why it matters: Assuming weights are distances limits the use of graphs in diverse applications.

Quick: Does a directed graph never have cycles? Commit yes or no.

Common Belief: Directed graphs cannot have cycles because edges go one way.

Reality: Directed graphs can have cycles if edges form a loop following their directions.

Why it matters: Failing to recognize cycles in directed graphs can cause infinite loops in algorithms.

Expert Zone

1

In weighted graphs, zero or negative weights have special meanings and require careful algorithm choice.

2

Self-loops and parallel edges (multiedges) complicate graph definitions and algorithm correctness.

3

The choice between adjacency list and matrix impacts performance drastically depending on graph density.

When NOT to use

Graphs are not ideal when relationships are strictly hierarchical (use trees) or when data is linear or tabular (use arrays or tables). For very large sparse graphs, specialized data structures like compressed sparse row (CSR) are better than naive adjacency matrices.

Production Patterns

Graphs are used in routing systems (GPS navigation), social network analysis (friend recommendations), dependency resolution (package managers), and recommendation engines (product suggestions). Real systems optimize storage and traversal based on graph size and density.

Connections

Network Topology

Graphs model network topology by representing devices as vertices and connections as edges.

Understanding graph terminology helps grasp how physical and logical networks are structured and analyzed.

Matrix Algebra

Adjacency matrices in graphs relate directly to matrices in algebra, enabling use of matrix operations for graph algorithms.

Knowing graph matrices connects graph theory to linear algebra, unlocking powerful computational techniques.

Project Management (Task Dependencies)

Directed graphs represent task dependencies where edges show order and weights can show task duration.

Graph terminology helps model and optimize project schedules by visualizing and analyzing task relationships.

Common Pitfalls

#1 Confusing directed and undirected edges leads to wrong path assumptions.

Wrong approach:

const graph = { A: ['B'], B: ['A'] }; // Treat as undirected but actually directed edges

Correct approach:

const graph = { A: ['B'], B: ['A'] }; // Explicitly treat as undirected by adding edges both ways

Root cause:

Not recognizing that directed edges require explicit two-way connections to behave like undirected.

#2 Ignoring weights when they affect path cost causes incorrect shortest path results.

Wrong approach:

const edges = [['A', 'B'], ['B', 'C']]; // No weights considered in path calculation

Correct approach:

const edges = [['A', 'B', 5], ['B', 'C', 2]]; // Weights included and used in algorithms

Root cause:

Treating weighted graphs like unweighted ones misses critical cost information.

#3 Assuming all graphs are connected and have no isolated vertices.

Wrong approach:

const vertices = ['A', 'B', 'C']; const edges = [['A', 'B']]; // Ignoring isolated vertex C

Correct approach:

const vertices = ['A', 'B', 'C']; const edges = [['A', 'B']]; // Recognize C is isolated and handle accordingly

Root cause:

Overlooking isolated vertices leads to incomplete graph analysis.

Key Takeaways

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

Edges may have weights representing costs or strengths, adding depth to graph modeling.

Understanding graph terminology is essential before learning graph algorithms and applications.

Graphs can represent many real-world systems like maps, networks, and dependencies.

Recognizing special cases like cycles, isolated vertices, and weighted edges prevents common mistakes.

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