![]() ![]() The implementation below uses the stack data-structure to build-up and return a set of vertices that are accessible within the subjects connected component. Explore each adjacent vertex that is not included in the visited set.Mark the current vertex as being visited.This property allows the algorithm to be implemented succinctly in both iterative and recursive forms.īelow is a listing of the actions performed upon each visit to a node. The first algorithm I will be discussing is Depth-First search which as the name hints at, explores possible vertices (from a supplied root) down each branch before backtracking. This has been purposely included to provide the algorithms with the option to return multiple paths between two desired nodes. Looking at the graph depiction below you will also notice the inclusion of a cycle, by the adjacent connections between ‘F’ and ‘C/E’. ![]() I have opted to implement an adjacency list which stores each node in a dictionary along with a set containing their adjacent nodes.Īs the graph is undirected each edge is stored in both incident nodes adjacent sets. There are two popular options for representing a graph, the first being an adjacency matrix (effective with dense graphs) and second an adjacency list (effective with sparse graphs). The resulting graph is undirected with no assigned edge weightings, as length will be evaluated based on the number of path edges traversed. ![]() So as to clearly discuss each algorithm I have crafted a connected graph with six vertices and six incident edges.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |