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