Algorithmic: the Spirit of Computing - Assignment Example

The two principal types of algorithms that do such traversals are the depth-first search (DFS) and the breath-first search (BFS). They have also proved out to be useful in the investigation of various key properties of a graph. A depth-first search begins by visiting the graph’s vertices at an arbitrary vertex by marking it as already been visited. The algorithm then at each iteration proceeds to an unvisited vertex, which is adjacent to the current one. The process then prolongs until upon encountering a vertex that has no adjacent vertices, unvisited.

A breadth-first search begins in a concentric manner by initially visiting all the vertices adjacent to the initiating vertex followed by all unvisited vertices that are two edges apart and so on unless it visits all the vertices in the same connected component as the starting vertex. Their contrasting characteristics are, while DFS is a traversal for the brave, BFS is for the cautious. While DFS uses a discipline of the stack, the latter uses that of the queue, which means the former has a LIFO approach and the latter has the FIFO.

The number of vertex orderings for DFS are two whereas for BFS it's one. The edge types in undirected graphs for DFS are tree and back edges whereas for the BFS the types are tree and cross edges. Important basic applications for both include checking connectivity and acyclicity of graph, however, the former has a sophisticated application of finding articulation point of a graph whereas the latter is useful in finding a path with the fewest number of edges between two given vertices (Levitin, 2005).