What is a Graph and How is it Represented
💡 Concept Name
Graph – A non-linear data structure that consists of vertices (nodes) and edges (connections) used to represent networks, relationships, or paths.
📘 Quick Intro
Graphs model pairwise relations between objects. Common examples include social networks, road maps, or dependency trees. Graphs can be directed or undirected, weighted or unweighted.
🧠 Analogy / Short Story
Think of a city map: each location is a node (vertex), and the roads between them are edges. Some roads are one-way (directed), others go both ways (undirected). We use graphs to model such structures.
🔧 Technical Explanation
- 🔹 A graph G = (V, E) where V = vertices, E = edges
-
🎯 Types:
- Directed vs Undirected
- Weighted vs Unweighted
- Cyclic vs Acyclic
-
🗂️ Representations:
- Adjacency Matrix: 2D array of size V×V
- Adjacency List: Array of lists
- ⚙️ Used in BFS, DFS, Dijkstra, Prim, Kruskal, and other algorithms
🎯 Purpose & Use Case
- ✅ Model relationships in social networks
- ✅ Network routing (routers, switches)
- ✅ Game AI and pathfinding (like A*)
- ✅ Scheduling and dependency resolution
- ✅ Web page ranking and crawl (e.g., Google’s PageRank)
💻 Real Code Example
// Adjacency List Representation
class Graph
{
int V;
List<int>[] adj;
public Graph(int vertices)
{
V = vertices;
adj = new List<int>[V];
for (int i = 0; i < V; i++)
adj[i] = new List<int>();
}
public void AddEdge(int src, int dest)
{
adj[src].Add(dest);
adj[dest].Add(src); // remove for directed graph
}
public void PrintGraph()
{
for (int i = 0; i < V; i++)
{
Console.Write($""Vertex {i}: "");
foreach (var edge in adj[i])
Console.Write(edge + "" "");
Console.WriteLine();
}
}
}
// Usage
var g = new Graph(4);
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 2);
g.AddEdge(2, 3);
g.PrintGraph();
❓ Interview Q&A
Q1: What is a graph in data structures?
A: A collection of nodes (vertices) connected by edges.
Q2: What are the types of graphs?
A: Directed, undirected, weighted, unweighted, cyclic, and acyclic graphs.
Q3: What is a directed graph?
A: A graph where edges have a direction from one vertex to another.
Q4: What is an undirected graph?
A: A graph where edges have no direction, connecting two vertices bidirectionally.
Q5: What is a weighted graph?
A: A graph where edges carry weights or costs.
Q6: What is a cycle in a graph?
A: A path where the start and end vertices are the same.
Q7: What is an acyclic graph?
A: A graph with no cycles.
Q8: How are graphs represented in memory?
A: Using adjacency lists or adjacency matrices.
Q9: What are common applications of graphs?
A: Social networks, routing algorithms, dependency resolution, and recommendation systems.
Q10: Can graphs be disconnected?
A: Yes, if not all vertices are reachable from each other.
📝 MCQs
Q1. What is a graph?
- Array
- Nodes connected by edges
- Tree
- List
Q2. Which is a directed graph?
- Edges have no direction
- Edges have direction
- No edges
- Undirected edges
Q3. What is an undirected graph?
- Edges have direction
- Edges connect vertices bidirectionally
- No edges
- Single vertex
Q4. What is a weighted graph?
- Edges have no weights
- Edges have weights
- Vertices have weights
- No weights
Q5. What defines a cycle in a graph?
- No repeated vertices
- Path starting and ending at same vertex
- Path with no edges
- Disconnected graph
Q6. What is an acyclic graph?
- Graph with cycles
- Graph without cycles
- Graph with weights
- Disconnected graph
Q7. How are graphs represented?
- Array only
- Adjacency list or matrix
- Linked list
- Queue
Q8. Where are graphs used?
- Sorting
- Social networks and routing
- Math only
- Text processing
Q9. Can graphs be disconnected?
- No
- Yes
- Sometimes
- Depends on edges
Q10. What is a vertex in a graph?
- An edge
- A node
- A path
- A cycle
💡 Bonus Insight
Graphs are everywhere—from social networks to compiler optimizations. Knowing how to model a problem as a graph often leads to elegant and efficient algorithmic solutions.
📄 PDF Download
Need a handy summary for your notes? Download this topic as a PDF!