Short Notes: Graphs

 Page 1


1 Graphs in Programming and Data Structures
1.1 Introduction to Graphs
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges.
Graphs model relationships between entities and are used in applications like social net-
works, routing, and scheduling.
1.2 Basic Terminology
• Vertex: A node in the graph.
• Edge: A connection between two vertices.
• Directed Graph (Digraph): Edges have direction (e.g., from vertex A to B).
• Undirected Graph: Edges are bidirectional.
• Weighted Graph: Edges have weights (e.g., distances or costs).
• Path: A sequence of vertices connected by edges.
• Cycle: A path where the start and end vertices are the same.
1.3 Representation of Graphs
• AdjacencyMatrix: A2DarraywhereM[i][j]representsanedge(orweight)from
vertex i to j. Suitable for dense graphs; space complexity: O(V
2
).
• Adjacency List: An array of lists where each list stores the neighbors of a vertex.
Suitable for sparse graphs; space complexity: O(V +E).
• EdgeList: Alistofedges,eachcontainingsource,destination,andoptionalweight.
Used for algorithms like Kruskals.
1.4 Basic Operations
• Add Vertex: Add a new node to the graph.
• Add Edge: Connect two vertices, with an optional weight.
• Remove Vertex/Edge: Delete a node or edge, updating connections.
• Traversal: Visit all vertices using Depth-First Search (DFS) or Breadth-First
Search (BFS).
1.5 Graph Traversal
• Depth-First Search (DFS): Explores as far as possible along each branch before
backtracking. Uses stack (explicit or recursive). Time: O(V +E).
• Breadth-FirstSearch(BFS):Exploresallneighborsatthecurrentdepthbefore
moving deeper. Uses queue. Time: O(V +E).
1.6 Key Algorithms
• Floyd-Warshall Algorithm: Finds shortest paths between all pairs of vertices in
a weighted graph. Time: O(V
3
). Handles negative weights but not negative cycles.
• TopologicalSorting: Ordersverticesinadirectedacyclicgraph(DAG)suchthat
if there is an edge from u to v, u appears before v. Uses DFS or Kahns algorithm.
Time: O(V +E).
1
Page 2


1 Graphs in Programming and Data Structures
1.1 Introduction to Graphs
A graph is a non-linear data structure consisting of vertices (nodes) connected by edges.
Graphs model relationships between entities and are used in applications like social net-
works, routing, and scheduling.
1.2 Basic Terminology
• Vertex: A node in the graph.
• Edge: A connection between two vertices.
• Directed Graph (Digraph): Edges have direction (e.g., from vertex A to B).
• Undirected Graph: Edges are bidirectional.
• Weighted Graph: Edges have weights (e.g., distances or costs).
• Path: A sequence of vertices connected by edges.
• Cycle: A path where the start and end vertices are the same.
1.3 Representation of Graphs
• AdjacencyMatrix: A2DarraywhereM[i][j]representsanedge(orweight)from
vertex i to j. Suitable for dense graphs; space complexity: O(V
2
).
• Adjacency List: An array of lists where each list stores the neighbors of a vertex.
Suitable for sparse graphs; space complexity: O(V +E).
• EdgeList: Alistofedges,eachcontainingsource,destination,andoptionalweight.
Used for algorithms like Kruskals.
1.4 Basic Operations
• Add Vertex: Add a new node to the graph.
• Add Edge: Connect two vertices, with an optional weight.
• Remove Vertex/Edge: Delete a node or edge, updating connections.
• Traversal: Visit all vertices using Depth-First Search (DFS) or Breadth-First
Search (BFS).
1.5 Graph Traversal
• Depth-First Search (DFS): Explores as far as possible along each branch before
backtracking. Uses stack (explicit or recursive). Time: O(V +E).
• Breadth-FirstSearch(BFS):Exploresallneighborsatthecurrentdepthbefore
moving deeper. Uses queue. Time: O(V +E).
1.6 Key Algorithms
• Floyd-Warshall Algorithm: Finds shortest paths between all pairs of vertices in
a weighted graph. Time: O(V
3
). Handles negative weights but not negative cycles.
• TopologicalSorting: Ordersverticesinadirectedacyclicgraph(DAG)suchthat
if there is an edge from u to v, u appears before v. Uses DFS or Kahns algorithm.
Time: O(V +E).
1
• Spanning Tree: A subgraph connecting all vertices with no cycles. Minimum
Spanning Tree (MST) is computed using:
– Kruskals Algorithm: Selects edges in increasing weight order, avoiding cycles.
Time: O(E logE).
– Prims Algorithm: Growsthetreefromastartingvertex,addingtheminimum-
weight edge. Time: O(V
2
) or O(E logV ) with a priority queue.
Applications of Graphs
• Networks: Model computer networks, social networks, or road maps.
• ShortestPath: Navigationsystems(e.g.,DijkstrasorFloyd-Warshallforrouting).
• DependencyResolution: Taskschedulingorbuildsystems(topologicalsorting).
• MST: Network design (e.g., minimizing cable length in telecom).
• Graph Coloring: Scheduling problems or resource allocation.
Advantages and Disadvantages
• Advantages:
– Flexible for modeling complex relationships.
– E?cient for problems like shortest paths or connectivity.
– Supports various algorithms for optimization.
• Disadvantages:
– High memory usage for dense graphs (adjacency matrix).
– Complex implementation for certain algorithms (e.g., Floyd-Warshall).
– Some algorithms are computationally expensive (e.g., O(V
3
)).
Short Questions and Answers
1. What is a graph? A data structure with vertices connected by edges, modeling
relationships.
2. How does DFS di?er from BFS? DFS explores deeply along a branch using a
stack, while BFS explores level-by-level using a queue.
3. What is the purpose of topological sorting? To order vertices in a DAG such
that dependencies are respected.
4. What is a minimum spanning tree? A subgraph connecting all vertices with
minimum total edge weight and no cycles.
2