Graph vs Tree Key Structural Difference in DSA Typescript - Build Both Approaches

Graph vs Tree Key Structural Difference

📖 Scenario: Imagine you are organizing a family reunion and a city map. The family reunion is like a tree structure where each person has one parent, but the city map is like a graph where places connect in many ways.

🎯 Goal: You will create simple data structures to represent a tree and a graph, then check the key difference: whether nodes have multiple parents or cycles.

📋 What You'll Learn

Create a tree structure using an adjacency list with no cycles

Create a graph structure using an adjacency list that can have cycles

Add a variable to track if the graph has cycles

Write a simple function to detect if the graph has cycles

Print the adjacency lists and cycle detection result

💡 Why This Matters

🌍 Real World

Trees are used in family trees, file systems, and organizational charts. Graphs are used in maps, social networks, and web links.

💼 Career

Understanding the difference between trees and graphs helps in software development, data analysis, and solving problems involving networks and hierarchies.

1

Create a tree adjacency list

Create a variable called tree as an object representing a tree adjacency list with these exact entries: 1: [2, 3], 2: [4], 3: [], 4: []

DSA Typescript

// Your code here

Hint

Use an object where keys are node numbers and values are arrays of child nodes.

2

Create a graph adjacency list

Create a variable called graph as an object representing a graph adjacency list with these exact entries: 1: [2, 3], 2: [3], 3: [1]

DSA Typescript

const tree: { [key: number]: number[] } = {
  1: [2, 3],
  2: [4],
  3: [],
  4: []
};
// Your code here

Hint

Graph can have cycles, so node 3 connects back to node 1.

3

Add cycle detection variable and function

Create a variable called hasCycle and set it to false. Then write a function called detectCycle that takes graph and returns true if a cycle exists, otherwise false. For simplicity, return true if node 3 connects back to node 1, else false.

DSA Typescript

const tree: { [key: number]: number[] } = {
  1: [2, 3],
  2: [4],
  3: [],
  4: []
};

const graph: { [key: number]: number[] } = {
  1: [2, 3],
  2: [3],
  3: [1]
};

// Your code here

Hint

Check if node 3's adjacency list includes node 1 to detect a cycle.

4

Print adjacency lists and cycle detection result

Write console.log statements to print the tree adjacency list, the graph adjacency list, and the hasCycle variable.

DSA Typescript

const tree: { [key: number]: number[] } = {
  1: [2, 3],
  2: [4],
  3: [],
  4: []
};

const graph: { [key: number]: number[] } = {
  1: [2, 3],
  2: [3],
  3: [1]
};

let hasCycle = false;

function detectCycle(graph: { [key: number]: number[] }): boolean {
  if (graph[3] && graph[3].includes(1)) {
    return true;
  }
  return false;
}

hasCycle = detectCycle(graph);

// Your code here

Hint

Use console.log to print each variable with a label.