Graph Theory I
In this post, I cover the basics of graph theory, including graph representations and simple graph search methods. In writing this post, I referenced my own study notes on Jeff Erickson’s textbook, Algorithms, which is available online under a Creative Commons Attribution 4.0 International License, as well as Youtube lectures by William Fiset and professor Erik Demaine.
Basics
Graph Notation
- Graph $(V,E)$ = Pair of sets $V, E$
- V = Set of nodes
- E = Set of edges between two nodes
- $ E \subset { {x, y} \mid x,y \in V, x \neq y } $
Terms & Definitions
- Degree of Node:
- Number of adjacent nodes
- Subgraph:
- $G’ = (V’, E’), \;\; (V’ \subseteq V, W’ \subseteq W)$
- Types of Graphs:
- Directed graph:
- In-degree: The number of nodes leading to the node
- Out-degree: The number of nodes leading out of the node
- Undirected graph:
- Closed graph: A graph that starts and ends on same node
- Cycle: A particular closed graph that has only one entry point
- Others: Forests, Trees, etc
- Directed graph:
Types of Graph Representations
- Adjacency List:
- A group of connected lists representing a graph, where each connected list contains all nodes adjacent to particular index node.
- Adjacency Matrix:
- A symmetric matrix where each element describes the connectivity of two nodes in a finite graph.
Types of Graph Searches / Traversals
\[\text{Depth-first Search}\]dfs(node = k):
if k NOT marked:
mark k
for each m adjacent to k:
dfs(m)
\(\)
\[\text{Breadth-first Search}\]bfs(G, s):
s.dist = 0
s.pred = NULL
s.color = GRAY
for all vertices v != s
v.color = WHITE
v.dist = ∞
v.pred = NULL
PUSH(s)
while Q is not empty
u = DEQUEUE(Q)
for all edges v adjacent to u
if v.dist > u.dist + 1
v.dist = u.dist + 1
v.pred = u
v.color = GRAY
PUSH(v)
u.color = BLACK
Exercise
Source: USA Computing Olympiad US Open 2007 Contest, Silver No. 2
Input
Output
Hint
Solution Code
import sys
def bfs(start, target, dist):
queue = []
queue.append(start)
while len(queue) != 0:
u = queue.pop(0)
if u == target:
print(dist[u])
break
for v in [u-1, u+1, 2*u]:
if (0 <= v <= 100000) and not dist[v]:
queue.append(v)
dist[v] = dist[u] + 1
input = sys.stdin.readline()
s,t = map(int, input.split())
dist = [0] * 100001
bfs(s,t, dist)
Conclusion
Over the past few weeks, I have taken some time each day to preview course materials for a class called “Algorithms and Data Structures,” offered by my university. Admittedly, the focus of this blog has diverged from ML/DL to a somewhat broader and less specific field, including recursion and graph theory. Nonetheless, I expect this blog to be a hodgepodge mix of various topics in computer science and mathematics in the near future, with a diversity of topics and discussions. In the next post, I hope to discuss either graph theory with an in-depth focus on more advanced subtopics, or other concepts such as network flows, dynamic programming, greedy algorithms, and etc.