🧩 What is a Graph?
A graph is a powerful non-linear data structure used to represent relationships between objects. It consists of a set of vertices (nodes) and a set of edges (connections) that link pairs of vertices.
Graphs are used to model real-world systems such as:
- Social networks
- Transportation systems
- Computer networks
- Web page links
Formally, a graph is defined as:
G = (V, E)
Where:
- V → Set of vertices
- E → Set of edges
🧠 Key Terminology in Graphs
- Vertex (Node) → Basic unit of a graph
- Edge → Connection between vertices
- Degree → Number of edges connected to a vertex
- Path → Sequence of vertices connected by edges
- Cycle → Path that starts and ends at the same vertex
- Connected Graph → Every vertex is reachable
- Disconnected Graph → Some vertices are isolated
- Weighted Graph → Edges have weights/costs
- Unweighted Graph → No weights on edges
🔗 Types of Graphs
🔹 1. Undirected Graph
Edges have no direction:
A — B
🔹 2. Directed Graph (Digraph)
Edges have direction:
A → B
🔹 3. Weighted Graph
Edges carry weights.
🔹 4. Unweighted Graph
All edges are equal.
🔹 5. Cyclic Graph
Contains cycles.
🔹 6. Acyclic Graph
No cycles present.
🔹 7. Complete Graph
Every vertex connects to every other vertex.
🔹 8. Bipartite Graph
Vertices divided into two sets.
🔹 9. Sparse vs Dense Graph
- Sparse → Few edges
- Dense → Many edges
🧱 Graph Representation
🔹 1. Adjacency Matrix
2D matrix representation.
🔹 2. Adjacency List
Stores neighbors of each node.
⚙️ Graph Operations
🔹 1. Traversal
DFS (Depth First Search)
- Uses stack
- Explores deep
BFS (Breadth First Search)
- Uses queue
- Explores level by level
🔹 2. Searching
Finding a node or path.
🔹 3. Insertion & Deletion
Adding/removing vertices or edges.
🧮 Graph Algorithms
🔹 1. Dijkstra’s Algorithm
Finds shortest path in weighted graphs.
🔹 2. Bellman-Ford Algorithm
Handles negative weights.
🔹 3. Floyd-Warshall Algorithm
All-pairs shortest path.
🔹 4. Kruskal’s Algorithm
Minimum spanning tree.
🔹 5. Prim’s Algorithm
Another MST algorithm.
🔹 6. Topological Sorting
Used in DAGs.
🧮 Time Complexity Overview
| Algorithm | Complexity |
|---|---|
| BFS | O(V + E) |
| DFS | O(V + E) |
| Dijkstra | O((V+E) log V) |
| Kruskal | O(E log E) |
⚡ Advantages of Graphs
- Flexible structure
- Models real-world relationships
- Supports complex algorithms
- Scalable
⚠️ Disadvantages of Graphs
- Complex implementation
- High memory usage
- Difficult debugging
🧠 Advanced Graph Concepts
🔹 1. Strongly Connected Components
🔹 2. Network Flow
🔹 3. Graph Coloring
🔹 4. Eulerian & Hamiltonian Paths
🔬 Applications of Graphs
🌐 1. Social Networks
🗺️ 2. GPS Navigation
🌍 3. Internet & Networking
🧠 4. Artificial Intelligence
🧬 5. Bioinformatics
🔁 Graph vs Tree
| Feature | Graph | Tree |
|---|---|---|
| Cycles | Allowed | Not allowed |
| Connectivity | Not necessary | Always connected |
| Structure | General | Hierarchical |
🧪 Memory Representation
Graph stored as:
- Matrix
- List
- Edge list
🚀 Real-World Importance
Graphs are essential in:
- Machine learning
- Networking
- Logistics
- Game development
- Data science
🧾 Conclusion
Graphs are among the most powerful and flexible data structures in computer science. They allow representation of complex relationships and are the foundation of many advanced algorithms.
Mastering graphs is crucial for solving real-world problems, especially in areas like AI, networking, and optimization.