Graph Terminology Vertices Edges Directed Undirected Weighted in DSA Javascript - Build from Scratch

Graph Terminology: Vertices, Edges, Directed, Undirected, Weighted

📖 Scenario: Imagine you are organizing a small social network where people are connected by friendships. You want to represent these connections using a graph. Each person is a vertex, and each friendship is an edge. Some friendships are one-way (like following someone), and some are two-way (mutual friends). Also, some friendships have a strength score showing how close the friends are.

🎯 Goal: You will build a simple graph using JavaScript objects and arrays to represent vertices and edges. You will mark edges as directed or undirected and add weights to show friendship strength.

📋 What You'll Learn

Create a graph object with vertices and edges

Add a configuration variable to mark if the graph is directed or undirected

Add weights to edges to represent friendship strength

Print the graph structure showing vertices and edges with direction and weights

💡 Why This Matters

🌍 Real World

Graphs are used to model networks like social connections, roads, or computer networks where relationships and directions matter.

💼 Career

Understanding graph basics is important for jobs in software development, data science, and network engineering.

1

Create the graph vertices and edges

Create a variable called graph as an object with two properties: vertices and edges. Set vertices to an array with these exact strings: 'Alice', 'Bob', 'Charlie'. Set edges to an array with these exact objects: { from: 'Alice', to: 'Bob' }, { from: 'Bob', to: 'Charlie' }.

DSA Javascript

# Your code here

Hint

Use an object with vertices and edges arrays. Each edge is an object with from and to keys.

2

Add a directed flag to the graph

Add a property called directed to the graph object and set it to true to indicate the edges have direction.

DSA Javascript

const graph = {
  vertices: ['Alice', 'Bob', 'Charlie'],
  edges: [
    { from: 'Alice', to: 'Bob' },
    { from: 'Bob', to: 'Charlie' }
  ]
};
# Add the directed property to graph below

Hint

Add directed: true inside the graph object.

3

Add weights to the edges

Add a weight property to each edge object in graph.edges. Set the weight from 'Alice' to 'Bob' as 5 and from 'Bob' to 'Charlie' as 3.

DSA Javascript

const graph = {
  vertices: ['Alice', 'Bob', 'Charlie'],
  edges: [
    { from: 'Alice', to: 'Bob' },
    { from: 'Bob', to: 'Charlie' }
  ],
  directed: true
};
# Add weight properties to each edge below

Hint

Add weight keys with numbers to each edge object.

4

Print the graph structure

Write a console.log statement to print the graph object.

DSA Javascript

const graph = {
  vertices: ['Alice', 'Bob', 'Charlie'],
  edges: [
    { from: 'Alice', to: 'Bob', weight: 5 },
    { from: 'Bob', to: 'Charlie', weight: 3 }
  ],
  directed: true
};
# Print the graph object below

Hint

Use console.log(graph) to show the graph object in the console.

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