MHB How to determine whether a graph is connected or not?

  • Thread starter Thread starter yakin
  • Start date Start date
  • Tags Tags
    Graph
AI Thread Summary
To determine if a graph is connected, one can use standard search algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS). Start the search from any node and track the visited nodes throughout the process. After the search completes, check for any unvisited nodes; if any exist, the graph is not connected. If all nodes are visited, the graph is confirmed to be connected. This method provides a practical approach to assessing graph connectivity.
yakin
Messages
42
Reaction score
0
How to determine whether a graph is connected or not?
 
Physics news on Phys.org
If you mean an algorithm, you can just use a standard search (BFS, DFS) starting from any point in the graph, keeping track of visited nodes. Once your search ends, check if there are any nodes that were not visited - if so, the graph is not connected, otherwise it is connected (can you prove this rigorously?).
 

Similar threads

MHB Graph: showing that diameter is greater than average pairwise distance
Replies
4
Views
3K
I Number of edges in a tree digraph
Replies
5
Views
2K
MHB Are Events in Random Graphs from G(n, 1/2) Independent?
Replies
1
Views
2K
MHB How many edges does the graph have?
Replies
4
Views
2K
MHB Graph Grammer Function For Two Exotic Graphs Question please.
Replies
4
Views
2K
MHB Determine the diameter of the graph
Replies
10
Views
2K
MHB Bipartite Graphs: Does $\alpha(G) =|U|$?
Replies
1
Views
2K
I Proof involving functional graphs and the injective property
Replies
3
Views
1K
MHB Minimum Degree of a Random Graph (Probabilistic Method)
Replies
1
Views
2K
MHB Understanding Two Graph Theory Problems
Replies
2
Views
2K

Hot Threads

Recent Insights

Back
Top