Graph Classnotes

 Absolutely, Siri. Here are interview-ready Graphs notes, organized from your class material.

📘 GRAPHS — CLASS NOTES

1. What is a Graph?

A Graph is a data structure made up of:

• Vertex (Node) → represents an item

• Edge (Connection) → represents a relationship between two vertices

Example:

      A
     / \
    B---C

Here:

• A, B, C → Vertices

• A-B, A-C, B-C → Edges

There is no fixed limit on how many other vertices one vertex can connect to.

---

2. Important Graph Terminology

Vertex

Singular = Vertex
Plural = Vertices

Edge

Connection between two vertices.

Hop

Moving from one vertex to another through an edge.

A ---- B ---- C

A → B → C = 2 hops

A → C directly, if an edge exists = 1 hop.

---

3. Weighted vs Unweighted Graph

Unweighted Graph

Edges don't have a cost/value.

A ----- B

Weighted Graph

Edges have a weight/cost.

A --5-- B
 \      
  \15
   \
    C

The weight can represent:

• Distance

• Time

• Traffic

• Cost

Real-world example

Google Maps may choose a route with a smaller cost even if it requires an additional hop.

Network routing can similarly prefer multiple fast links over one slow link.

---

4. Bidirectional vs Directional Graph

Bidirectional

Connection works both ways.

A -------- B

Example: Facebook friendship.

If A is friends with B, B is also friends with A.

Usually no arrows are shown.

Directional / Directed

Connection has a specific direction.

A ------> B

Example: following someone on Instagram/Twitter.

You follow the celebrity, but they don't necessarily follow you back.

---

5. Graph → Tree → Linked List

This is a very important relationship:

Graph
  ↓
Tree
  ↓
Linked List

A Tree is a type of Graph with additional restrictions.

A Linked List can also be viewed as a restricted form of these structures.

---

6. Two Ways to Represent a Graph

There are two important representations:

1. Adjacency Matrix

2. Adjacency List

---

7. Adjacency Matrix

An adjacency matrix uses a 2D array.

Suppose:

A ----- B
|
|
E

We can represent connections using 1 and 0.

• 1 → edge exists

• 0 → edge doesn't exist

Example:

    A B C D E
A   0 1 0 0 1
B   1 0 1 0 0
C   0 1 0 1 0
D   0 0 1 0 1
E   1 0 0 1 0

Important interview point

The diagonal is normally 0:

A → A = 0
B → B = 0
C → C = 0

For a bidirectional graph, the matrix is symmetrical around the diagonal:

A → B = 1
B → A = 1

If the graph becomes directional, that symmetry can disappear.

Weighted Matrix

Instead of 1, store the weight:

A → B = 5

So the matrix stores the actual edge weight.

---

8. Adjacency List ⭐

An adjacency list stores each vertex and the vertices it connects to.

Usually represented using:

HashMap<Vertex, ArrayList<Edges>>

Example:

A → [B, E]
B → [A, C]
C → [B, D]
D → [C, E]
E → [A, D]

Here:

Key   → Vertex
Value → ArrayList of connected vertices

---

9. Adjacency Matrix vs Adjacency List ⭐⭐⭐

Operation	Matrix	List
Space	O(V²)	O(V + E)
Add Vertex	O(V²)	O(1)
Add Edge	O(1)	O(1)
Remove Edge	O(1)	O(E)
Remove Vertex	O(V²)	O(V + E)

Where:

• V = number of vertices

• E = number of edges

Why is Adjacency List usually better?

Matrix stores all possible connections, including zeros for connections that don't exist.

For a very large sparse graph, this wastes a huge amount of space.

Therefore, the course uses an Adjacency List.

---

10. Java Implementation

The graph uses:

HashMap<String, ArrayList<String>>

Think:

HashMap
   ↓
Vertex → List of connected vertices

Example:

A → [B, E]
B → [A, C]

The String is the vertex and the ArrayList<String> contains its connections.

---

11. addVertex()

Purpose:

Add a new vertex to the graph.

Conceptually:

adjacencyList.put(vertex, new ArrayList<>());

But we first check whether the vertex already exists.

if (adjacencyList.get(vertex) == null) {
    adjacencyList.put(vertex, new ArrayList<>());
    return true;
}

return false;

Why return boolean?

true  → vertex successfully added
false → vertex already exists

Big-O

O(1)

---

12. addEdge() ⭐

Suppose:

A ----- B

For a bidirectional graph:

A → [B]
B → [A]

Conceptually:

adjacencyList.get(vertex1).add(vertex2);
adjacencyList.get(vertex2).add(vertex1);

Before doing this, check that both vertices exist.

If A exists AND B exists
        ↓
    Add edge

Otherwise:

return false

Big-O

O(1)

---

13. removeEdge()

Suppose:

A ----- B

After removing:

A       B

Adjacency list changes:

Before:

A → [B]
B → [A]


After:

A → []
B → []

Code concept:

adjacencyList.get(vertex1).remove(vertex2);
adjacencyList.get(vertex2).remove(vertex1);

Both vertices must exist.

Big-O

O(E) for the adjacency-list implementation described in the class.

Why?

Because we may need to search through the ArrayList to find the vertex being removed.

---

14. removeVertex() ⭐⭐⭐

Suppose:

    A
   / \
  D---B
   \
    C

If we remove D, we must remove:

1. D → A

2. D → B

3. D → C

4. Finally D itself

Key idea

Because edges are bidirectional, if:

D → A
D → B
D → C

then we know:

A → D
B → D
C → D

So we only need to loop through D's own adjacency list.

Conceptually:

for (String otherVertex : adjacencyList.get(vertex)) {
    adjacencyList.get(otherVertex).remove(vertex);
}

adjacencyList.remove(vertex);

Steps to remember

Find D
 ↓
Get D's neighbors
 ↓
Remove D from each neighbor
 ↓
Remove D itself

Big-O

O(V + E)

---

🧠 QUICK MEMORY TRICK

Remember the four methods as:

ADD
 ↓
addVertex   → Put vertex
addEdge     → Connect vertices

REMOVE
 ↓
removeEdge  → Break connection
removeVertex→ Remove vertex + its connections

And representation:

Graph
 ├── Adjacency Matrix → 2D Array → O(V²) space
 │
 └── Adjacency List   → HashMap + ArrayList → O(V + E) space

⭐ Interview Questions to Prepare

1. What is a Graph?

2. What is the difference between vertex and edge?

3. What is a weighted graph?

4. What is a directed graph?

5. What is a bidirectional graph?

6. What is an adjacency matrix?

7. What is an adjacency list?

8. Why is adjacency list generally better for sparse graphs?

9. What is the space complexity of an adjacency matrix?

10. What is the space complexity of an adjacency list?

11. What data structures are used to implement the adjacency list in Java?

12. Explain addVertex().

13. Explain addEdge().

14. Explain removeEdge().

15. Explain removeVertex().

16. Why can removeVertex() be done efficiently with bidirectional edges?

These notes are based on your uploaded class material, keeping its terminology and examples.

-------

// THIS GOES IN YOUR MAIN CLASS TO TEST YOUR CODE:

// -----------------------------------------------

package datastructures.graph;

public class Main {

    public static void main(String[] args) {

        Graph myGraph = new Graph();

        myGraph.addVertex("A");

        myGraph.addVertex("B");

        myGraph.addVertex("C");

        myGraph.addEdge("A", "B");

        myGraph.addEdge("A", "C");

        myGraph.addEdge("B", "C");

        System.out.println("\nGraph before removeEdge():");

        myGraph.printGraph();

        myGraph.removeEdge("A", "B");

        System.out.println("\nGraph after removeEdge():");

        myGraph.printGraph();

        /*

            EXPECTED OUTPUT:

            ----------------

            Graph before removeEdge():

            {A=[B, C], B=[A, C], C=[A, B]}

            

            Graph after removeEdge():

            {A=[C], B=[C], C=[A, B]}

        */

    }

}

// THIS CODE GOES IN YOUR GRAPH CLASS:

// -----------------------------------

      

package datastructures.graph;

import java.util.ArrayList;

import java.util.HashMap;

public class Graph {

    private HashMap<String, ArrayList<String>> adjList = new HashMap<>();

    public void printGraph() {

        System.out.println(adjList);

    }

    public boolean addVertex(String vertex) {

        if (adjList.get(vertex) == null) {

            adjList.put(vertex, new ArrayList<String>());

            return true;

        }

        return false;

    }

    public boolean addEdge(String vertex1, String vertex2) {

        if (adjList.get(vertex1) != null && adjList.get(vertex2) != null) {

            adjList.get(vertex1).add(vertex2);

            adjList.get(vertex2).add(vertex1);

            return true;

        }

        return false;

    }

    public boolean removeEdge(String vertex1, String vertex2) {

        if (adjList.get(vertex1) != null && adjList.get(vertex2) != null) {

            adjList.get(vertex1).remove(vertex2);

            adjList.get(vertex2).remove(vertex1);

            return true;

        }

        return false;

    }

}