Graphs

Problems on Graph Data Structure and popular algorithms associated with Graphs

SDE Sheet problems on Graphs

Sheet Link

Day 23

Completion Status	Problems on Graphs	Explanation	Solution
🔃	Clone a graph	Brute, Better & Optimal Approaches	Java Soultion
🔃	DFS	Brute, Better & Optimal Approaches	Java Soultion
🔃	BFS	Brute, Better & Optimal Approaches	Java Soultion
🔃	Detect A cycle in Undirected Graph using BFS	Brute, Better & Optimal Approaches	Java Soultion
🔃	Detect A cycle in Undirected Graph using DFS	Brute, Better & Optimal Approaches	Java Soultion
🔃	Detect A cycle in a Directed Graph using DFS	Brute, Better & Optimal Approaches	Java Soultion
🔃	Detect A cycle in a Directed Graph using BFS	Brute, Better & Optimal Approaches	Java Soultion
🔃	Topological Sort	Brute, Better & Optimal Approaches	Java Soultion
🔃	Number of islands (Do in Grid and Graph both)	Brute, Better & Optimal Approaches	Java Soultion
🔃	Bipartite Check using BFS	Brute, Better & Optimal Approaches	Java Soultion
🔃	Bipartite Check using DFS	Brute, Better & Optimal Approaches	Java Soultion

Day 24

Completion Status	Problems on Graphs	Explanation	Solution
🔃	Strongly Connected Component (using KosaRaju’s algo)	Brute, Better & Optimal Approaches	Java Soultion
🔃	Dijkstra’s Algorithm	Brute, Better & Optimal Approaches	Java Soultion
🔃	Bellman-Ford Algo	Brute, Better & Optimal Approaches	Java Soultion
🔃	Floyd Warshall Algorithm	Brute, Better & Optimal Approaches	Java Soultion
🔃	MST using Prim’s Algo	Brute, Better & Optimal Approaches	Java Soultion
🔃	MST using Kruskal’s Algo	Brute, Better & Optimal Approaches	Java Soultion

---

Tasks

• Theoretical concepts
  • What is a graph?
  • Types of graph
  • Degree in a graph
  • Path in a graph
• Problems
• Patterns

---

What is a Graph?

• Graph is a data structure
• Graph has two components, namely:
  • Node/vertex
  • Edge

---

Types of graph

• There are two types of graphs:
  • Undirected graphs
  • Directed graphs
• Consider 2 nodes v1 and v2:
  • There are two edges v1v2 and v2v1 in an undirected graph
  • There is only one edge v1v2 in a directed graph

Undirected cyclic graph

• A cycle is a path through which we can come back to the starting position
• If there's a cycle in an Undirected graph we can call it as an Undirected cyclic graph

Undirected acyclic graph

• When there's not a cycle we can call it as an Undirected acyclic graph

Directed cyclic graph

• A cycle is a path through which we can come back to the starting position
• If there's a cycle in an Undirected graph we can call it as an Undirected cyclic graph

Directed acyclic graph (DAG)

• When there's not a cycle we can call it as an Undirected acyclic graph

Undirected Weighted graphs

• Thw edges in this graph have weights

Directed Weighted graphs

• Thw edges in this graph have weights

---

Degrees in a graph

• Degrees in a graph
  • Degree of a vertex is the number of incoming and outgoing edges to the vertex in a graph
  • The Degree(v2) = 2 in the above undirected graph
  • The InDegree(v2) = 1 in the above directed graph
  • The OutDegree(v2) = 1 in the above directed graph

• Property of Degree in an undirected graph
  • Total degree of nodes = 2 * Edges
  • The total number of degree of all the nodes is equal to twice of the number of all the edges in an undirected graph

---

Path in a graph

• Path in an undirected graph
  • The sequence of nodes/vertex such that none of the nodes are visited twice
  • Examples:
    • v2 v3 v1
    • v2 v1
    • v3 v2

• Path in a directed graph
  • The sequence of directed nodes/vertex such that none of the nodes are visited twice
  • Examples:
    • v1 v2 v3
    • v1 v3
    • v2 v3

---