Graph Theory and Searching Algorithms Review

Graph Theory Fundamentals: Adjacency Matrix and Adjacent Nodes

• Definition of Adjacent Nodes:

  • In a graph $G = (V, E)$, two nodes (or vertices) $u$ and $v$ are said to be adjacent if there is an edge $(u, v)$ or $e \text{ connects } u \text{ and } v$ directly linking them.
  • If the graph is undirected, adjacency is mutual: if $u$ is adjacent to $v$, then $v$ is adjacent to $u$.
  • If the graph is directed, node $v$ is adjacent to $u$ if there is a directed edge from $u$ to $v$.

• Definition of Adjacency Matrix:

  • An Adjacency Matrix is a mathematical way of representing the connections (edges) between the nodes of a graph in a square matrix format.
  • For a graph with $n$ nodes, the adjacency matrix $A$ is an $n \times n$ matrix where:
    • $A[i][j] = 1$ if there is an edge from node $i$ to node $j$.
    • $A[i][j] = 0$ if there is no edge between node $i$ and node $j$.
  • Properties for Undirected Graphs: The matrix is symmetric ($A[i][j] = A[j][i]$) because an edge between $i$ and $j$ implies a connection in both directions.
  • Properties for Directed Graphs: The matrix may or may not be symmetric, depending on the presence of reciprocal edges.
  • Diagonal Elements: If a node has a self-loop (an edge connecting a node to itself), the diagonal element $A[i][i]$ will be $1$. Otherwise, it is typically $0$.

Searching Techniques: Linear and Binary Search

• Definition of Searching:

  • Searching is the process used to find the location or existence of a specific element (target/key) within a given collection of data, such as an array, list, or tree.

• Linear Search:

  • Mechanism: This algorithm starts at the beginning of the data set and examines each element sequentially one by one until the target is found or the end of the collection is reached.
  • Requirement: The data does not need to be sorted.
  • Example: Finding the number $45$ in the list $[10, 20, 45, 30, 50]$. The search checks index $0$, then index $1$, then finds $45$ at index $2$.
  • Time Complexity:
    • Best Case: $O(1)$ (target is at the first position).
    • Average/Worst Case: $O(n)$ (target is at the end or not present).

• Binary Search:

  • Mechanism: A divide-and-conquer algorithm that repeatedly divides the search interval in half. It compares the target value to the middle element of the array.
  • Requirement: The data must be sorted in ascending or descending order.
  • Steps:
    1. Start with the middle element.
    2. If the target is equal to the middle element, the search is complete.
    3. If the target is smaller, repeat the process on the left half.
    4. If the target is larger, repeat the process on the right half.
  • Example: Finding the number $67$ in a sorted list $[10, 20, 30, 45, 55, 67, 88]$.
    • Sorted List: $[10, 20, 30, 45, 55, 67, 88]$
    • Middle is $45$. Since $67 > 45$, search the right half: $[55, 67, 88]$.
    • Middle is $67$. Target found.
  • Time Complexity:
    • Best Case: $O(1)$.
    • Average/Worst Case: $O(\log(n))$.

• Differentiation of Time Complexities:

  • Efficiency: Binary search ($O(\log(n))$) is significantly faster than Linear search ($O(n)$) for large datasets.
  • Example Comparison: In a dataset of $1,000,000$ elements, Linear Search might take up to $1,000,000$ steps, whereas Binary Search would take at most around $\log_2(1,000,000) \approx 20$ steps.

Construction of an Undirected Graph and Adjacency Matrix

• Specification of Graph G:

  • Vertices $V(G) = \{1, 2, 3, 4\}$
  • Edges $E(G) = \{(1,2), (1,3), (3,3), (3,4), (4,1)\}$

• Graph Visualization (Undirected):

  • Node 1 is connected to: 2, 3, and 4.
  • Node 2 is connected to: 1.
  • Node 3 is connected to: 1, 3 (self-loop), and 4.
  • Node 4 is connected to: 3 and 1.

• Adjacency Matrix for Graph G:

  • Since the graph is undirected, every edge $(u, v)$ creates an entry for both $A[u][v]$ and $A[v][u]$. The self-loop $(3,3)$ creates a single entry at $A[3][3]$.

$\begin{pmatrix} & 1 & 2 & 3 & 4 \\ 1 & 0 & 1 & 1 & 1 \\ 2 & 1 & 0 & 0 & 0 \\ 3 & 1 & 0 & 1 & 1 \\ 4 & 1 & 0 & 1 & 0 \end{pmatrix}$

Directed vs. Undirected Graphs and Node Degrees

• Directed Graph (Digraph):

  • A graph where edges have a specific direction. Edges are represented by ordered pairs $(u, v)$, indicating a path from $u$ to $v$.

• Undirected Graph:

  • A graph where edges have no direction. Edges are unordered pairs, meaning the connection $(u, v)$ is the same as $(v, u)$.

• Finding In-degree and Out-degree (Directed Graph):

  • In-degree: The number of edges coming into a specific node. In an adjacency matrix, this is the sum of the columns for that node.
  • Out-degree: The number of edges going out from a specific node. In an adjacency matrix, this is the sum of the rows for that node.

• Degree Calculation Example:

  • Suppose a graph with edges: $(1 \rightarrow 2), (1 \rightarrow 3), (2 \rightarrow 3), (3 \rightarrow 1)$.
  • Node 1:
    • Out-degree: $2$ (Edges to 2 and 3)
    • In-degree: $1$ (Edge from 3)
  • Node 2:
    • Out-degree: $1$ (Edge to 3)
    • In-degree: $1$ (Edge from 1)
  • Node 3:
    • Out-degree: $1$ (Edge to 1)
    • In-degree: $2$ (Edges from 1 and 2)

Spanning Trees and Minimum Cost Spanning Tree (MCST)

• What is a Spanning Tree?

  • A spanning tree is a subset of a connected, undirected graph that includes all the vertices of the graph and forms a tree (no cycles).
  • If a graph has $V$ vertices, the spanning tree must have exactly $V-1$ edges.

• Minimum Cost Spanning Tree (MCST):

  • In a weighted graph, the MCST is the spanning tree where the sum of the weights of the edges is minimized.

• Algorithm to find MCST (Kruskal's Algorithm):

  1. Sort all the edges of the graph in non-decreasing order of their weight.
  2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If a cycle is not formed, include this edge.
  3. Repeat step 2 until there are $(V-1)$ edges in the spanning tree.

• Example of MCST Algorithm:

  • Consider a graph with edges: $(A,B)=2, (B,C)=1, (A,C)=3, (C,D)=4$.
  • Step 1 (Sort Edges): $(B,C)=1, (A,B)=2, (A,C)=3, (C,D)=4$.
  • Step 2: Add $(B,C)$; total cost = $1$.
  • Step 3: Add $(A,B)$; no cycle formed; total cost = $1+2=3$.
  • Step 4: Consider $(A,C)$? Adding $(A,C)$ creates a cycle $(A-B-C-A)$. Discard it.
  • Step 5: Add $(C,D)$; no cycle formed; total cost = $3+4=7$.
  • Final MCST edges: $(B,C), (A,B), (C,D)$.

Graph Traversal Algorithms: BFS and DFS

• Breadth-First Search (BFS):

  • Concept: Explores neighbors before moving to the next level (Layer-by-layer exploration).
  • Data Structure: Uses a Queue (First-In-First-Out).
  • Algorithm:
    1. Maintain a queue and a list of visited nodes.
    2. Enqueue the starting node and mark it as visited.
    3. De-queue a node, visit all its unvisited adjacent neighbors, mark them as visited, and enqueue them.
    4. Repeat until the queue is empty.
  • Example: From Node 1 in a graph with connections $(1-2), (1-3), (2-4), (3-5)$.
    • BFS Order: $1, 2, 3, 4, 5$.

• Depth-First Search (DFS):

  • Concept: Explores as far as possible along each branch before backtracking.
  • Data Structure: Uses a Stack or Recursion (Last-In-First-Out).
  • Algorithm:
    1. Maintain a stack and a list of visited nodes.
    2. Push the starting node onto the stack.
    3. Pop a node, if not visited, mark it as visited.
    4. Push all its unvisited neighbors onto the stack.
    5. Repeat until the stack is empty.
  • Example: From Node 1 in a graph with connections $(1-2), (2-4), (1-3), (3-5)$.
    • DFS Order: $1, 3, 5, 2, 4$ (depending on push order).