# Research

# Write-up

# Section 1 - Understanding and Explanation of Graphs

What is a graph?

- A way of representing relationships between different items (known as nodes) via edges (the connections between the nodes). Shows how different nodes are linked non-linearly.

What is a directed and undirected graph?

- a directed graph is a graph where every edge has a specific direction, pointing from one node to another.
- a undirected graph is a graph where the edges don’t have a specific direction, the connection between any two nodes is mutual, meaning you can traverse the edge in either direction.

What is the difference between weighted and unweighted graphs?

- a weighted graph is a graph where every edge has a specific value assigned to it, this value can also be described as the cost/distance to another node.
- an unweighted graph is a graph where the edges simply indicate that a connection exists between two nodes, in this type of graph all connections have same cost to get to the next node.

Adjacency list vs adjacency matrix

- Adjacency list
    - For each vertex, store a list or vector) of its neighbouring vertices
    - Typically represented through arrays of lists
- Adjacency matrix
    - Square 2D array used to represent a finite graph with n vertices
    - Where each element, a 1 or a 0 is used to represent a link between two nodes.

Real world applications of graphs? 

- Some real world applications of directed graphs:
    - Social media followers
    - Web page hyperlinks
    - Traffic flow optimisation
    - Navigation systems
    - Biological food webs
- Some real world applications of undirected graphs:
    - Two-way road networks
    - Infrastructure connections
    - Used in optimising networks like power grids or cable laying using Minimum Spanning Trees (MST)

Traversal concepts (BFS/DFS overview)

- BFS:
    - Breadth-First Search
    - Explores level-by-level — visits all neighbours of a node before moving deeper
    - Uses a queue (FIFO):
        - Add start node to queue
        - Dequeue a node, mark it visited, enqueue all its unvisited neighbours
        - Repeat until queue is empty
- Depth-First Search (DFS)
    - Explores as deep as possible along one path before backtracking
    - Uses a stack (LIFO) or recursion:
        - Push start node to stack
        - Pop a node, mark it visited, push its unvisited neighbours
        - Repeat until stack is empty


|                      | BFS                         | DFS                           |
| -------------------- | --------------------------- | ----------------------------- |
| Data structure       | Queue                       | Stack/ Recursion              |
| Explores             | Wide first                  | Deep first                    |
| Finds shortest path? | Yes                         | Not guaranteed                |
| Memory usage         | Higher (stores whole level) | lower                         |
| Good for             | Shortest path, networking   | Maze solving, cycle detection |