Graph Basics
Graph Basics¶
Overview¶
A graph is a data structure consisting of vertices and edges, used to represent networks, relationships, and paths. This lesson covers basic graph concepts and DFS, BFS traversal.
Table of Contents¶
- Graph Basic Concepts
- Graph Representation
- Depth First Search (DFS)
- Breadth First Search (BFS)
- DFS vs BFS
- Graph Applications
- Practice Problems
1. Graph Basic Concepts¶
Graph Terminology¶
Graph G = (V, E)
- V: Set of vertices
- E: Set of edges
Example:
(1)βββ(2)
β / β
β / β
(3)βββ(4)
V = {1, 2, 3, 4}
E = {(1,2), (1,3), (2,3), (2,4), (3,4)}
Types of Graphs¶
1. Directed/Undirected Graphs
Undirected: Directed:
(1)βββ(2) (1)ββββ(2)
β β
β β
(4)βββ(3)
2. Weighted Graph
(1)ββ5ββ(2)
β / β
3 2 4
β / β
(3)ββ1ββ(4)
3. Connected/Disconnected Graph
Connected: Disconnected:
(1)β(2) (1)β(2) (4)
β / β β
(3)β(4) (3)ββ
Graph Properties¶
- Degree: Number of edges connected to a vertex
- Undirected: degree(v)
- Directed: in-degree(v), out-degree(v)
- Path: Sequence of vertices
- Cycle: Path where start equals end
- Connected Component: Set of connected vertices
2. Graph Representation¶
2.1 Adjacency Matrix¶
Undirected graph:
(0)βββ(1)
β / β
β / β
(2)βββ(3)
Adjacency matrix:
0 1 2 3
0 [0, 1, 1, 0]
1 [1, 0, 1, 1]
2 [1, 1, 0, 1]
3 [0, 1, 1, 0]
Properties:
- Space: O(VΒ²)
- Edge existence check: O(1)
- Adjacent vertex iteration: O(V)
- Suitable for dense graphs
// C
#define MAX_V 100
int graph[MAX_V][MAX_V];
int V; // Number of vertices
void addEdge(int u, int v) {
graph[u][v] = 1;
graph[v][u] = 1; // Undirected
}
int hasEdge(int u, int v) {
return graph[u][v];
}
// C++
class GraphMatrix {
private:
vector<vector<int>> adj;
int V;
public:
GraphMatrix(int v) : V(v), adj(v, vector<int>(v, 0)) {}
void addEdge(int u, int v) {
adj[u][v] = 1;
adj[v][u] = 1; // Undirected
}
bool hasEdge(int u, int v) {
return adj[u][v] == 1;
}
};
# Python
class GraphMatrix:
def __init__(self, v):
self.V = v
self.adj = [[0] * v for _ in range(v)]
def add_edge(self, u, v):
self.adj[u][v] = 1
self.adj[v][u] = 1 # Undirected
def has_edge(self, u, v):
return self.adj[u][v] == 1
2.2 Adjacency List¶
Undirected graph:
(0)βββ(1)
β / β
β / β
(2)βββ(3)
Adjacency list:
0: [1, 2]
1: [0, 2, 3]
2: [0, 1, 3]
3: [1, 2]
Properties:
- Space: O(V + E)
- Edge existence check: O(degree)
- Adjacent vertex iteration: O(degree)
- Suitable for sparse graphs
// C - Linked list approach
#define MAX_V 100
typedef struct Node {
int vertex;
struct Node* next;
} Node;
Node* adj[MAX_V];
int V;
void addEdge(int u, int v) {
// u -> v
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = v;
newNode->next = adj[u];
adj[u] = newNode;
// v -> u (undirected)
newNode = (Node*)malloc(sizeof(Node));
newNode->vertex = u;
newNode->next = adj[v];
adj[v] = newNode;
}
// C++
class GraphList {
private:
int V;
vector<vector<int>> adj;
public:
GraphList(int v) : V(v), adj(v) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // Undirected
}
const vector<int>& neighbors(int u) {
return adj[u];
}
};
# Python
class GraphList:
def __init__(self, v):
self.V = v
self.adj = [[] for _ in range(v)]
def add_edge(self, u, v):
self.adj[u].append(v)
self.adj[v].append(u) # Undirected
def neighbors(self, u):
return self.adj[u]
# Or using defaultdict
from collections import defaultdict
graph = defaultdict(list)
graph[0].append(1)
graph[1].append(0)
Representation Comparison¶
ββββββββββββββββββ¬ββββββββββββββββ¬ββββββββββββββββ
β β Adj Matrix β Adj List β
ββββββββββββββββββΌββββββββββββββββΌββββββββββββββββ€
β Space β O(VΒ²) β O(V + E) β
β Edge check β O(1) β O(degree) β
β Neighbor iter β O(V) β O(degree) β
β Add edge β O(1) β O(1) β
β Best for β Dense graphs β Sparse graphs β
ββββββββββββββββββ΄ββββββββββββββββ΄ββββββββββββββββ
3. Depth First Search (DFS)¶
Concept¶
DFS: Go deep in one direction, backtrack when stuck
β Implemented with stack or recursion
(0)
/ | \
(1)(2)(3)
/ / \
(4) (5)(6)
DFS order (starting from 0):
0 β 1 β 4 β (backtrack) β 2 β (backtrack) β 3 β 5 β (backtrack) β 6
Visit order: 0, 1, 4, 2, 3, 5, 6
Recursive Implementation¶
// C
#define MAX_V 100
int adj[MAX_V][MAX_V];
int visited[MAX_V];
int V;
void dfs(int v) {
visited[v] = 1;
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (adj[v][i] && !visited[i]) {
dfs(i);
}
}
}
// C++
class Graph {
private:
int V;
vector<vector<int>> adj;
public:
Graph(int v) : V(v), adj(v) {}
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfs(int start) {
vector<bool> visited(V, false);
dfsUtil(start, visited);
}
private:
void dfsUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
dfsUtil(neighbor, visited);
}
}
}
};
# Python
def dfs_recursive(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited)
return visited
Iterative Implementation (Stack)¶
// C++
void dfsIterative(int start) {
vector<bool> visited(V, false);
stack<int> st;
st.push(start);
while (!st.empty()) {
int v = st.top();
st.pop();
if (visited[v]) continue;
visited[v] = true;
cout << v << " ";
// Push in reverse to maintain order
for (auto it = adj[v].rbegin(); it != adj[v].rend(); it++) {
if (!visited[*it]) {
st.push(*it);
}
}
}
}
# Python
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
v = stack.pop()
if v in visited:
continue
visited.add(v)
print(v, end=' ')
# Add in reverse to maintain order
for neighbor in reversed(graph[v]):
if neighbor not in visited:
stack.append(neighbor)
return visited
4. Breadth First Search (BFS)¶
Concept¶
BFS: Visit all adjacent vertices of current vertex first
β Implemented with queue
(0)
/ | \
(1)(2)(3)
/ / \
(4) (5)(6)
BFS order (starting from 0):
Level 0: 0
Level 1: 1, 2, 3
Level 2: 4, 5, 6
Visit order: 0, 1, 2, 3, 4, 5, 6
Implementation¶
// C
#define MAX_V 100
int adj[MAX_V][MAX_V];
int visited[MAX_V];
int V;
void bfs(int start) {
int queue[MAX_V];
int front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front < rear) {
int v = queue[front++];
printf("%d ", v);
for (int i = 0; i < V; i++) {
if (adj[v][i] && !visited[i]) {
visited[i] = 1;
queue[rear++] = i;
}
}
}
}
// C++
void bfs(int start) {
vector<bool> visited(V, false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
cout << v << " ";
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
# Python
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
v = queue.popleft()
print(v, end=' ')
for neighbor in graph[v]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
Shortest Path with BFS¶
// C++ - Shortest distance in unweighted graph
vector<int> shortestPath(int start) {
vector<int> dist(V, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
for (int neighbor : adj[v]) {
if (dist[neighbor] == -1) {
dist[neighbor] = dist[v] + 1;
q.push(neighbor);
}
}
}
return dist;
}
# Python
def shortest_path(graph, start):
dist = {start: 0}
queue = deque([start])
while queue:
v = queue.popleft()
for neighbor in graph[v]:
if neighbor not in dist:
dist[neighbor] = dist[v] + 1
queue.append(neighbor)
return dist
5. DFS vs BFS¶
Comparison Table¶
ββββββββββββββββββ¬ββββββββββββββββββββββ¬ββββββββββββββββββββββ
β β DFS β BFS β
ββββββββββββββββββΌββββββββββββββββββββββΌββββββββββββββββββββββ€
β Data structure β Stack/Recursion β Queue β
β Memory β O(h) - height β O(w) - width β
β Complete searchβ Possible β Possible β
β Shortest path β β β β (unweighted) β
β Cycle detectionβ β β β β
β Path existence β β β β β
ββββββββββββββββββ΄ββββββββββββββββββββββ΄ββββββββββββββββββββββ
When to Use Which?¶
Use DFS:
- When all nodes must be visited
- When path characteristics need to be stored
- Backtracking problems
- Cycle detection
- Topological sort
Use BFS:
- Shortest path/minimum cost (unweighted)
- Level-order traversal
- Finding nearest first
Visual Comparison¶
(1)
/ | \
(2)(3)(4)
/ \ / \
(5)(6)(7)(8)
DFS (Stack):
Visit order: 1 β 2 β 5 β 6 β 3 β 4 β 7 β 8
Depth first: Explore one branch completely
BFS (Queue):
Visit order: 1 β 2 β 3 β 4 β 5 β 6 β 7 β 8
Breadth first: Explore same level first
6. Graph Applications¶
6.1 Finding Connected Components¶
// C++
int countConnectedComponents() {
vector<bool> visited(V, false);
int count = 0;
for (int i = 0; i < V; i++) {
if (!visited[i]) {
dfs(i, visited); // or bfs
count++;
}
}
return count;
}
# Python
def count_connected_components(graph, n):
visited = set()
count = 0
for i in range(n):
if i not in visited:
dfs_recursive(graph, i, visited)
count += 1
return count
6.2 Cycle Detection (Undirected Graph)¶
// C++
bool hasCycleDFS(int v, int parent, vector<bool>& visited) {
visited[v] = true;
for (int neighbor : adj[v]) {
if (!visited[neighbor]) {
if (hasCycleDFS(neighbor, v, visited)) {
return true;
}
} else if (neighbor != parent) {
// Visited but not parent = cycle
return true;
}
}
return false;
}
bool hasCycle() {
vector<bool> visited(V, false);
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (hasCycleDFS(i, -1, visited)) {
return true;
}
}
}
return false;
}
# Python
def has_cycle(graph, n):
visited = set()
def dfs(v, parent):
visited.add(v)
for neighbor in graph[v]:
if neighbor not in visited:
if dfs(neighbor, v):
return True
elif neighbor != parent:
return True
return False
for i in range(n):
if i not in visited:
if dfs(i, -1):
return True
return False
6.3 Bipartite Graph Check¶
Bipartite graph: Vertices can be divided into two groups,
no edges within the same group
(1)β(2) (1) (2)
β Γ β β β β
(3)β(4) (3) (4)
Coloring method: Adjacent vertices must have different colors
// C++
bool isBipartite() {
vector<int> color(V, -1); // -1: unvisited, 0/1: color
for (int i = 0; i < V; i++) {
if (color[i] == -1) {
queue<int> q;
q.push(i);
color[i] = 0;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int neighbor : adj[v]) {
if (color[neighbor] == -1) {
color[neighbor] = 1 - color[v];
q.push(neighbor);
} else if (color[neighbor] == color[v]) {
return false; // Adjacent with same color
}
}
}
}
}
return true;
}
# Python
from collections import deque
def is_bipartite(graph, n):
color = [-1] * n
for start in range(n):
if color[start] == -1:
queue = deque([start])
color[start] = 0
while queue:
v = queue.popleft()
for neighbor in graph[v]:
if color[neighbor] == -1:
color[neighbor] = 1 - color[v]
queue.append(neighbor)
elif color[neighbor] == color[v]:
return False
return True
6.4 2D Grid Traversal¶
Treating grid as a graph:
- Each cell = vertex
- Up/down/left/right = edges
Used for maze solving, counting islands, etc.
// C++ - Number of Islands
int numIslands(vector<vector<char>>& grid) {
int m = grid.size();
int n = grid[0].size();
int count = 0;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
function<void(int, int)> dfs = [&](int x, int y) {
if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != '1') {
return;
}
grid[x][y] = '0'; // Mark visited
for (int i = 0; i < 4; i++) {
dfs(x + dx[i], y + dy[i]);
}
};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == '1') {
dfs(i, j);
count++;
}
}
}
return count;
}
# Python
def num_islands(grid):
if not grid:
return 0
m, n = len(grid), len(grid[0])
count = 0
def dfs(x, y):
if x < 0 or x >= m or y < 0 or y >= n or grid[x][y] != '1':
return
grid[x][y] = '0' # Mark visited
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
dfs(i, j)
count += 1
return count
7. Practice Problems¶
Problem 1: Path Existence Check¶
Check if a path exists between two vertices.
Solution Code
def has_path(graph, start, end):
visited = set()
stack = [start]
while stack:
v = stack.pop()
if v == end:
return True
if v in visited:
continue
visited.add(v)
for neighbor in graph[v]:
if neighbor not in visited:
stack.append(neighbor)
return False
Problem 2: Find All Paths¶
Find all paths between two vertices.
Solution Code
def find_all_paths(graph, start, end, path=None):
if path is None:
path = []
path = path + [start]
if start == end:
return [path]
paths = []
for neighbor in graph[start]:
if neighbor not in path: # Prevent cycles
new_paths = find_all_paths(graph, neighbor, end, path)
paths.extend(new_paths)
return paths
Recommended Problems¶
| Difficulty | Problem | Platform | Type |
|---|---|---|---|
| β | DFS and BFS | BOJ | Basic traversal |
| β | Connected Components | BOJ | Components |
| ββ | Number of Islands | LeetCode | Grid DFS |
| ββ | Maze Exploration | BOJ | BFS shortest |
| ββ | Is Graph Bipartite? | LeetCode | Bipartite |
| βββ | Complex Numbering | BOJ | Grid traversal |
Template Summary¶
DFS Template¶
# Recursive
def dfs(graph, v, visited):
visited.add(v)
for neighbor in graph[v]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Iterative
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
v = stack.pop()
if v not in visited:
visited.add(v)
for neighbor in graph[v]:
stack.append(neighbor)
BFS Template¶
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
v = queue.popleft()
for neighbor in graph[v]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
2D Grid Traversal¶
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def is_valid(x, y, m, n):
return 0 <= x < m and 0 <= y < n
Next Steps¶
- 13_Topological_Sort.md - Topological Sort
References¶
- Graph Visualization
- BFS/DFS Tutorial
- Introduction to Algorithms (CLRS) - Chapter 22