and adjacency matrix representation
. The authors then discuss about breadth first search
method of graph traversal. A vertex is considered to be discovered the first time it is encountered during search. Given a graph and a source vertex , BFS produces a "breadth-first-tree" with root s that contains all vertices reachable from . The algorithm
discovers all the vertices at distance from before discovering any vertices at distance . When a vertex is first discovered in the course of scanning the adjacency list of an already discovered vertex , is called the predecessor or parent vertex of . The authors provide definitions for shortest path and shortest path distance. The authors then prove some properties of BFS and BFS trees. The authors then discuss about depth first search
method of graph traversal. A vertex is considered finished when its adjacency list has been examined completely. The authors describe the parenthesis structure of discovered and finished time, i.e. if the discovered time is represented with left parenthesis and finished time is represented with right parenthesis, the history of times create a well-formed expression. The authors prove some properties of DFS.The authors discuss about topological sort
of a directed acyclic graph (DAG) , which is a linear ordering of all its vertices such that if G contains an edge then appears before in the ordering. The authors then provide an algorithm to generate topological-sort of a DAG and prove that the algorithm takes time.The authors then discuss strongly connected components
of a directed graph. The strongly connected component of a directed graph is a maximal set of vertices such that for every pair of vertices and in , we have both and , i.e. vertices and are reachable from each other. The authors then prove some properties of strongly-connected-components.
No comments:
Post a Comment