I am reading Mark Weiss's book (2nd Edition) and I can't wrap my head around this thing. How is this even possible. If a graph is undirected then there must be a way to visit every node from everyone. From the image (https://algorithms.tutorialhorizon.com/check-if-given-undirected-graph-is-connected-or-not/). If I want to visit any node from 4, I can. The only way, I can't is if I remove the connection to 4. If that happens, how is this a graph (in my mind graph needs to have edges). Can graphs have "dangling vertices"?
"A connected graph is connected if and only if a depth first search starting from any node visits every other node"
145 Views Asked by harrySherlock At
1
There are 1 best solutions below
Related Questions in GRAPH-THEORY
- Algorithm for total flow through weighted directed acyclic graph
- Finding path with smallest GCD of nodes's weights in directed graph
- The plot function in the 'gRc' library gives an error (also in the demo)
- Color edges distinctly in network based on attribute value
- Make a stack of adjacency matrices from a dataframe in R
- What is an efficient algorithm to identify multi-degree email chains in a mock company network?
- Approximation Algorithms for the Longest Simple Path in a Directed Graph
- Eliminate edges in a routing graph which aren't used in the shortest path between a subset of nodes
- PageRank Algorithm on a Graph with a Sink Node
- Algorithm to cover time periods
- Prims minimum spanning
- DFS Maze generation
- Find the node with the minimum maximum distance in a graph
- Undirected connected graph - Finding edges with specific weight that belong to MST
- Why is my graph coloring code not coloring the graph correctly?
Related Questions in DEPTH-FIRST-SEARCH
- Iterative DFS algo doesn't match with recursive
- How to turn a iterative DFS into a recursive DFS?
- Determining if a graph has a cycle without using DFS
- Doing a DFS on a neo4j graph
- Recurse within binary tree's node class
- Use Recursion to get Subsets of an array. C++ and Java give me different results
- Maximum no. of nodes reachable from a given source in a Graph
- How can we perform Depth First Search on a tree on external memory in O(sort(N))?
- Recursive depth first search Integer ArrayList Java
- Modify the DFS method so that it can detect if a Graph is a Tree or not
- Finding the largest subsets of nodes in a tree subject to some constraints?
- Recursive Depth First Search (DFS) algorithm in C++
- Equivalence relation in DFS
- DFS to print all permutations of a string in python
- Finding all possible paths in graph
Related Questions in STRONGLY-CONNECTED-GRAPH
- Relationship Between Intermediate Vertices and Strongly Connected Components (SCCs) in Graphs
- How to get a list of edges in python corresponding to a set?
- Strongly connected component for the graph is giving different result for Kosaraju's Algorithm and Tarjan's Algorithm
- A graph with maximum number of strongly connected components
- How to break down Strongly Connected Components (SCC) in a graph to obtain smaller and smaller nested cycles in JavaScript?
- Difference between a directed cycle and a strongly connected component
- Let G=(V, E) directed graph. Let v be a vertex in G, find the number of vertices that take part in non-simple directed paths to v
- Generate random directed connected graph using networkx?
- Given a list of words, determine whether the words can be chained to form a circle
- Finding no. of strongly connected components - wrong answer by my code
- Neo4j find n largest connected graphs with specific node types
- Returning connected parts of a graph (dfs & graphs)
- "A connected graph is connected if and only if a depth first search starting from any node visits every other node"
- Find Strongly Connected Graph such that the difference between the maximum and minimum edges is minimum
- Strongly Connected Components
Trending Questions
- UIImageView Frame Doesn't Reflect Constraints
- Is it possible to use adb commands to click on a view by finding its ID?
- How to create a new web character symbol recognizable by html/javascript?
- Why isn't my CSS3 animation smooth in Google Chrome (but very smooth on other browsers)?
- Heap Gives Page Fault
- Connect ffmpeg to Visual Studio 2008
- Both Object- and ValueAnimator jumps when Duration is set above API LvL 24
- How to avoid default initialization of objects in std::vector?
- second argument of the command line arguments in a format other than char** argv or char* argv[]
- How to improve efficiency of algorithm which generates next lexicographic permutation?
- Navigating to the another actvity app getting crash in android
- How to read the particular message format in android and store in sqlite database?
- Resetting inventory status after order is cancelled
- Efficiently compute powers of X in SSE/AVX
- Insert into an external database using ajax and php : POST 500 (Internal Server Error)
Popular Questions
- How do I undo the most recent local commits in Git?
- How can I remove a specific item from an array in JavaScript?
- How do I delete a Git branch locally and remotely?
- Find all files containing a specific text (string) on Linux?
- How do I revert a Git repository to a previous commit?
- How do I create an HTML button that acts like a link?
- How do I check out a remote Git branch?
- How do I force "git pull" to overwrite local files?
- How do I list all files of a directory?
- How to check whether a string contains a substring in JavaScript?
- How do I redirect to another webpage?
- How can I iterate over rows in a Pandas DataFrame?
- How do I convert a String to an int in Java?
- Does Python have a string 'contains' substring method?
- How do I check if a string contains a specific word?
Yes. They can also have subgraphs, sets of vertices connected to each other but not connected to the vertices in other subgraphs. These are usually called components.
For more https://en.wikipedia.org/wiki/Component_(graph_theory)