Implementing Graphs in Java: Adjacency Lists and Graph Operations

Conceptual Overview: The lecture focuses on the practical implementation of graph data structures in Java, transitioning from the theoretical discussion held in the previous session (Friday).
Implementation Goals:
- Define core graph classes: Node and Graph.
- Implement methods to add and remove nodes.
- Implement methods to add and remove edges.
- Explore and implement graph traversal algorithms (Depth-First Search and Breadth-First Search).

Definition: A graph is a set of nodes (also called vertices) and edges that connect them.
Flexibility: Graphs are exceptionally flexible data structures. They can represent various real-world scenarios by including additional information, such as:
- Node Coloring: Visualizing categories or states.
- Directed vs. Undirected: Whether edges have a specific direction (arrows) or are bidirectional.
- Cyclic vs. Acyclic: Whether it is possible to loop infinitely through paths in the graph.
- Weighted vs. Unweighted: Weighted graphs add information to edges, typically representing distance (e.g., $24\,km$ ) or cost.
- Sparse vs. Dense:
  - Sparse Graphs: Have relatively few edges.
  - Dense Graphs: Have many edges connecting the nodes.

Structure: Represented as a two-dimensional array (an array of arrays).
Mechanism: If an edge exists between two nodes, the corresponding cell in the matrix contains a $1$ ( $\text{true}$ ); otherwise, it contains a $0$ ( $\text{false}$ ).
Dimensions: The number of rows and columns is equal to the number of nodes in the graph.
Pros/Cons:
- Pros: Easy to implement; efficient for dense graphs where many cells are filled.
- Cons: For sparse graphs (e.g., only $1\%$ of nodes are connected), it results in an enormous amount of wasted memory because most cells are empty.
Weighting in Matrices: To represent weights, the $1$ is replaced with the weight value. A potential conflict arises if $0$ is a valid weight (meaning free travel) versus $0$ meaning "no edge."
- Solution: Instead of an integer, the matrix can store Edge objects. A null value indicates no connection, while an Edge object with a value of $0$ represents a zero-cost connection.
Symmetry: In an undirected graph, an adjacency matrix will always be symmetric across the diagonal ( $A$ to $B$ is the same as $B$ to $A$ ).

Structure: Represented as a list of lists.
Mechanism: Each node maintains its own list of neighbors (the nodes it is directly connected to).
Pros/Cons:
- Pros: More dynamic and memory-efficient for sparse graphs. Easier to add new nodes and edges without reserving large blocks of memory (unlike arrays which might require resizing).

Purpose: To represent individual vertices and track their specific connections.
Attributes:
- String name: The identifier for the node (e.g., "A", "B", "C").
- ArrayList<Node> neighbors: A list of all other nodes directly connected to this instance.
Constructor: Initializes the node with a name and an empty ArrayList for neighbors.
Helper Methods:
- addNeighbor(Node n): Adds a node reference to the neighbors list.
- removeNeighbor(Node n): Removes a node reference from the list.
- getNeighbor(String name): Iterates through neighbors to find a node by name. Uses .equals() for string comparison to ensure value equality rather than memory address equality.
- toString(): Returns a string representation of the node's neighbors for printing purposes.

Purpose: To manage the overall collection of nodes and perform high-level operations.
Attributes:
- ArrayList<Node> nodes: A master list of all nodes currently in the graph.
Core Methods:
- findNode(String s): Returns a boolean indicating if a node with name $s$ exists.
- getNode(String s): Returns the actual Node object for name $s$ , or null if not found.
- print(): Iterates through the nodes list and prints each node's name followed by its neighbor list.

Add Node:
- Checks if the node name already exists using findNode to avoid duplicates.
- If unique, adds a new Node(name) to the master nodes array.
Add Edge:
- In an undirected graph, adding an edge between $A$ and $B$ requires adding $B$ to $A$ 's neighbor list AND adding $A$ to $B$ 's neighbor list.
- The implementation first fetches both Node objects using getNode. If either is null, the operation aborts to maintain integrity.
- Self-Loops: If an edge is added from $D$ to $D$ , the logic adds $D$ to the list twice. While functional for traversal, it is usually refactored to remove duplicates in neighbors.

Remove Edge: Finds both nodes and calls removeNeighbor on each one to delete the bidirectional link.
Remove Node: This is a multi-step process to avoid "dangling" or "ghost" references:
1. Get the target Node object.
2. Iterate through the target node's list of neighbors.
3. For each neighbor, visit their neighbor list and remove the reference to the target node.
4. Finally, remove the target node from the master nodes list in the Graph class.

Depth-First Search (DFS):
- Strategy: Explores as deep as possible into a branch before backtracking.
- Implementation: Often recursive. It requires a visitedNodes array to track where the algorithm has already been to prevent infinite loops (especially in cyclic graphs).
- Logic: Start at a node, add it to visitedNodes, get neighbors, and for every neighbor not already in visitedNodes, call the function recursively.
Breadth-First Search (BFS):
- Strategy: Explores one level of distance at a time (all immediate neighbors, then all neighbors' neighbors).

Question: Why is there a difference between dense and sparse graphs in terms of representation selection?
Answer: It is about memory efficiency. A table (matrix) is excellent when you have lots of information (edges). A list is better when information is sparse because you only store what exists, saving memory.
Question: Since an undirected graph matrix is symmetric, can we save storage by only storing half the matrix?
Answer: Yes, in theory, knowledge of symmetry allows memory reduction, though it would require a more complex data structure than a simple 2D array to implement. Similarly, in an adjacency list, an undirected edge is represented twice ( $A \rightarrow B$ and $B \rightarrow A$ ), which is a trade-off for easier data retrieval.