Using Strongly Connected Component Algo to check if a vertex is reachable
antz
I would like to see if a given vertex, say V0, can be reachable by all other vertices in a graph G.
I know I can just traverse through each vertex in the graph and do BFS/DFS to see if V0 is reachable.
However, this seems to be very inefficient.
I was wondering if i do SCC algo on the graph and if v0 is part of all scc, then I can safely conclude that v0 is reachable by all vertices? This would be great because the cost of SCC is only O(V+E) with Tarjan's and checking to see if v0 is part of scc would also cost linear time.
I would think this makes sense because SCC means vertices are reachable. Any confirmation to this logic?
or any efficient approach to this?
Evgeny Kluev
V0 may not belong to SCC, but still be reachable by all other vertices. For example, vertex d on diagram is reachable by all other vertices, but the only non-trivial SCC contains vertices a, b, c and does not contain vertex d.
To check if V0 is reachable by all other vertices, you can reverse direction of every edge (in linear time), then use BFS/DFS, starting from V0, to check if every other vertex is reachable from V0 (also in linear time).
Collected from the Internet
Please contact [email protected] to delete if infringement.
edited at
- Prev: Python Pandas Merge Three Dataframes Based on Row Value
- Next: Select dataframe index derived from comparing a dataframe column and a list
Related
TOP Ranking
- 1
Can't pre-populate phone number and message body in SMS link on iPhones when SMS app is not running in the background
- 2
pump.io port in URL
- 3
Failed to listen on localhost:8000 (reason: Cannot assign requested address)
- 4
Spring Boot JPA PostgreSQL Web App - Internal Authentication Error
- 5
How to import an asset in swift using Bundle.main.path() in a react-native native module
- 6
Loopback Error: connect ECONNREFUSED 127.0.0.1:3306 (MAMP)
- 7
BigQuery - concatenate ignoring NULL
- 8
Modbus Python Schneider PM5300
- 9
Make a B+ Tree concurrent thread safe
- 10
What is the exact difference between “ use_all_dns_ips” and "resolve_canonical_bootstrap_servers_only” in client.dns.lookup options?
- 11
Svchost high CPU from Microsoft.BingWeather app errors
- 12
3D Touch Peek Swipe Like Mail
- 13
Printing Int array and String array in one
- 14
java.lang.NullPointerException: Cannot read the array length because "<local3>" is null
- 15
UWP access denied
- 16
Emulator wrong screen resolution in Android Studio 1.3
- 17
Google Chrome Translate Page Does Not Work
- 18
Apache rewrite or susbstitute rule for bugzilla HTTP 301 redirect
- 19
Can a 32-bit antivirus program protect you from 64-bit threats
- 20
Is there an option for a Simulink Scope to display the layout in single column?
- 21
Unable to use switch toggle for dark mode in material-ui
Comments