Circles and Connectivity in Graphs
(Page 1 of 4 )
Search and you will find. At least this is what everybody says whenever you are lost and you do not know what to do. This is as true in life as it is in graph theory. Today we're going to search for some answers concerning strong connectivity and circles inside graphs. When all is said and done, we'll find another way to use graphs to solve some complex algorithm-related problems. This is the fifth part of a multi-part series.
Some wise mathematicians once embarked on a search to resolve certain problems and ultimately found the solution. This article is part of a series I am writing about these graphs, presenting various ways to use them and certain algorithms. This is a continuation of the article I wrote on the depth-first search algorithm.
I will try to explain how we can reuse searches to solve complex problems. If you missed the previous part I strongly recommend that you read it, as it contains information that will be necessary for you to comprehend this article. We have much ground to cover, so let us begun.
I already defined connectivity inside a graph during the introductory article to this saga entitled “An Insight into Graphs.” Connectivity can be illustrated in a graph which contains no directed edges; between any two vertexes, there exists a road. If a graph is not in the described state, we can talk about the components of it (sub graphs) that will satisfy this criteria.
Strong connectivity means the same as ordinary connectivity, but we translate everything to a graph with directed edges. If you read the previous article, it is easy to deduce that calculating the number of connected components in a graph is the same as counting the number of times we call the DFS search.
Every call will inform us of another connective sub-graph. However, when we go to graphs with directed edges, the problem becomes a little more complicated. Before we take a closer look at this difficulty, we first need to learn how to find the base circle system inside a graph.
Next: Circles and the Base Circle System >>
More Code Examples Articles
More By Gabor Bernat
/ 2 
