Graph
• A graph is a non-linear data structure consisting of nodes or vertices
connected by edges.
• Each node may contain a value, and each edge may have a weight or
label.
• G (V , E)
F
C
A
B
D E G
Terminologies in Graph data structure
• Vertex (V): Also known as a node, it represents a
single point in the graph. F
• Edge (E): A connection between two vertices. C
• Adjacent Vertices: Two vertices are adjacent if A
they are connected by an edge. B
• Neighbor Vertices: Vertices that are adjacent to D E G
a given vertex.
• Degree of a Vertex: The number of edges
incident on a vertex.
• Weighted Edge: An edge with a weight or label
associated with it.
• Unweighted Edge: An edge without a weight or
label associated with it
• Directed Edge: An edge with direction,
represented by an arrow.
• Undirected Edge: An edge without direction.
F
• Path: A sequence of vertices and edges between
two vertices. C
• Cycle: A path that starts and ends at the same A
B
vertex.
• Simple Path: A path with no repeated vertices. D E G
• Connected Graph: A graph where there is a path
between every pair of vertices.
• Disconnected Graph: A graph where there is no
path between some pairs of vertices.
• Subgraph: A graph that is a subset of another
graph.
• Tree: A connected graph with no cycles.
• Forest: A disconnected graph with no
cycles.
• Isolated Vertex: A vertex with no edges F
incident on it. C
• Pendant Vertex: A vertex with only one A
edge incident on it. B
• Graph Isomorphism: Two graphs are D E G
isomorphic if they have the same
structure.
Graph Representations
• Adjacency Matrix
• Adjacency List
Adjacency Matrix Graph Representation
B
A B C D
A A 1 1 1
B 1 1
C
C 1 1
D 1
D
• The adjacency matrix above represents an undirected Graph, so the values '1'
only tells us where the edges are. Also, the values in the adjacency matrix is
symmetrical because the edges go both ways (undirected Graph).
3 B
A B C D
A
2 1 A 3 2
B
4 C
C 1
D D 4
Adjacency List Graph Representation
A
0 A 3 1 2 null
C 1 B 0 2 null
2 C 1 0 null
D 3 D 0 null
3 B
0 A 1, 3 2, 2 null
A
1 1 B null
2
2 C 1, 1 null
4 C
3 D 0, 4 null
D
Graph Traversal
The two most common ways a Graph can be traversed are:
• Depth First Search (DFS)
• Breadth First Search (BFS)
Depth First Search Traversal
• DFS use Stack Data Structure
Algorithm Steps
1. Create a stack to store nodes.
2. Push the starting node onto the stack.
3. Mark the starting node as visited.
4. While the stack is not empty:
- Pop the top node from the stack.
- Visit the node.
- Push all unvisited neighbors of the node onto the stack.
- Mark the neighbors as visited.
F
A
B
D E G
Result: D,A,C,B,F,E,G
Breadth First Search Traversal
• DFS use Queue DS
Algorithm Steps
1. Create an empty queue.
2. Enqueue the starting node.
3. Mark the starting node as visited
4. While the queue is not empty:
- Dequeue a node.
- Visit the node.
- Enqueue all unvisited neighbors of the node.
- Mark the neighbors as visited.
F
A
B
D E G
Result: D,A,C,E,B,F,G