Graph -11: Check if Source to Destination Path exists in Directed Graph

preview_player
Показать описание
Solution:
- We'll achieve this via DFS approach.
- Take stack & boolean array
- Now when you start dfs from source index, it mark visited to all components to which it's connected to
- So via visted boolean array, we can identify if element is visited or not
- So at last return visited[destination_index]

Time Complexity: O(V + E)

CHECK OUT CODING SIMPLIFIED

★☆★ VIEW THE BLOG POST: ★☆★

I started my YouTube channel, Coding Simplified, during Dec of 2015.
Since then, I've published over 400+ videos.

★☆★ SUBSCRIBE TO ME ON YOUTUBE: ★☆★

★☆★ Send us mail at: ★☆★
  1. Coding Simplified
  2. Tutorial
  3. Coding
  4. Simplified
  5. check if source to destination is connected
  6. check if destination is connected via source
Рекомендации по теме
Graph -11: Check 0:11:55

Graph -11: Check if Source to Destination Path exists in Directed Graph

Graph Course 11 0:08:24

Graph Course 11 | Check if Graph is BiPartite or Not

G-11. Detect a 0:20:19

G-11. Detect a Cycle in an Undirected Graph using BFS | C++ | Java

Graph - 10: 0:13:27

Graph - 10: Find if Source to Destination is reachable in Undirected Graph

How To Analyse 0:08:36

How To Analyse XRD Data / Plot / Graph in Research Paper? Experimental Paper Skills

Graph -14: Check 0:26:28

Graph -14: Check if Directed Graph has Cycle (Using InDegree/BFS)

Graph - 12: 0:19:03

Graph - 12: Check if Undirected Graph has Cycle

Dependent and independent 0:02:00

Dependent and independent variables exercise: express the graph as an equation | Khan Academy

Terminologies and Rules 0:11:39

Terminologies and Rules of Signal Flow Graph

Connected and Strongly 0:12:05

Connected and Strongly Connected Components in a Graph #Graph Series #24

Check If path 0:06:41

Check If path Exist from Source to Destination || Graph || DSA || C++

Check If Given 0:11:42

Check If Given Graph Is Tree Or Not

Dijkstras Shortest Path 0:08:24

Dijkstras Shortest Path Algorithm Explained | With Example | Graph Theory

Graph Data Structure 0:21:33

Graph Data Structure | Part 11 | Dijkstra's Algorithm | Shortest Path in Graph Step by Step Dem...

Graph Algorithms for 2:12:19

Graph Algorithms for Technical Interviews - Full Course

2608 Shortest Cycle 0:00:41

2608 Shortest Cycle in Graph

Possible paths between 0:12:51

Possible paths between 2 vertices #Graph Algorithms #Backtracking #DFS

Supply and Demand 0:00:54

Supply and Demand Explained in One Minute

Find if Path 0:12:23

Find if Path Exists in Graph | Leetcode 1971 | Graph

Detect Cycle in 0:12:17

Detect Cycle in Undirected Graph | Using DFS | Cycle detection in Graph | DSA-One Course #77

3. Graph-theoretic Models 0:50:11

3. Graph-theoretic Models

The Formula For 0:01:24

The Formula For Economic Growth | Intellections

Electron JS in 0:01:49

Electron JS in 100 Seconds

Find If Path 0:06:48

Find If Path Exists in Graph - LeetCode 1971 - JavaScript

Комментарии
Автор

I really admire this solution, i got confused while searching on net. Neat and concise

rahulsinghai
Автор

Hi , the code you mentioned for dfs using Stack is a bit wrong, though it will work.
You are marking each node as visited, when you are in the for loop itself, so, in this way all the neighbours get visited all together for a particular node, and this way it do not go to the depth first.
You must be marking them visited as true, when you pop them out of stack, in the while loop.
I have seen this issue in many of your programs.
Correct me if i am wrong, since I also need to get this cleared, if I am wrong
Thanks

akashgarg
Автор

Thank you sir. very much informative...clear explanation.

pinkyg
Автор

If we do dfs in directed to undirected graph it will cover each and every node
Then how, by traversing into the directed graph our one element is not visited

adarshgoyal