Graph Representations and Traversal Algorithms
Learn about representing graphs using adjacency matrices and adjacency lists, understand the space and time complexities of different representations, and explore traversal algorithms like Breadth-First-Search (BFS) in graph theory.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 12: Breadth-First-Search (BFS)
Graph Representations Graphs can be given by adjacency matrix or adjacency list. The adjacency matrix of a graph has value ai,j = 1 if vertices i and j share an edge; 0 otherwise. For a weighted graph, ai,j = wi,j, the weight of the edge. The adjacency list of a graph G = (V,E) is an array Adj[1..|V|] of lists, where Adj[v] is a list of all vertices adjacent to vertex v. adjacency matrix adjacency list 1 1 2 0 1 0 0 0 3 2 2 1 5 3 1 0 1 0 1 A = 0 1 0 0 1 2 3 5 0 0 0 0 1 4 5 5 4 0 1 1 1 0 5 3 2 4
Graph Representations Graphs can be given by adjacency matrix or adjacency list. The adjacency matrix of a graph has value ai,j = 1 if vertices i and j share an edge; 0 otherwise. For a weighted graph, ai,j = wi,j, the weight of the edge. The adjacency list of a graph G = (V,E) is an array Adj[1..|V|] of lists, where Adj[v] is a list of all vertices adjacent to vertex v. adjacency matrix adjacency list 1 1 2 0 1 0 0 0 3 2 2 1 5 3 1 0 1 0 1 A = 0 1 0 0 1 2 3 5 0 0 0 0 1 4 5 5 4 0 1 1 1 0 5 3 2 4 For graphs with n nodes and m edges, adjacency matrices take (n2) space and adjacency list takes (m) space.
Graph Representations Graphs can be given by adjacency matrix or adjacency list. The adjacency matrix of a graph has value ai,j = 1 if vertices i and j share an edge; 0 otherwise. For a weighted graph, ai,j = wi,j, the weight of the edge. The adjacency list of a graph G = (V,E) is an array Adj[1..|V|] of lists, where Adj[v] is a list of all vertices adjacent to vertex v. Check if [v, w] is an edge: Adjacency Matrix: O(1) time Adjacency List: O(deg(v)) time adjacency matrix adjacency list 1 1 2 0 1 0 0 0 3 2 2 1 5 3 1 0 1 0 1 Traverse all edges on a vertex v: Adjacency Matrix: O(n) time Adjacency List: O(1) per edge A = 0 1 0 0 1 2 3 5 0 0 0 0 1 4 5 5 4 0 1 1 1 0 5 3 2 4 For graphs with n nodes and m edges, adjacency matrices take (n2) space and adjacency list takes (m) space.
Traversing a Graph Two basic methods: Breadth-First-Search and Depth-First-Search
Traversing a Graph Two basic methods: Breadth-First-Search and Depth-First-Search Breadth-First-Search (BFS). Starting from a vertex s, traverse the graph vertices level by level.
Traversing a Graph Two basic methods: Breadth-First-Search and Depth-First-Search Breadth-First-Search (BFS). Starting from a vertex s, traverse the graph vertices level by level. BFS(G, s) \\ Q is a queue 1. for (each vertex v) color[v] = white; 2. color[s] = gray; 3. enqueue(Q, s); 4. while (Q is not empty) w = dequeue(Q); for (each edge [w, v]) if (color[v] == white) color[v] = gray; enqueue(Q, v); color[w] = black.
Traversing a Graph Two basic methods: Breadth-First-Search and Depth-First-Search Breadth-First-Search (BFS). Starting from a vertex s, traverse the graph vertices level by level. BFS(G, s) \\ Q is a queue 1. for (each vertex v) color[v] = white; 2. color[s] = gray; 3. enqueue(Q, s); 4. while (Q is not empty) w = dequeue(Q); for (each edge [w, v]) if (color[v] == white) color[v] = gray; enqueue(Q, v); color[w] = black. 3 4 5 8 7 2 1 6
