Please enable JavaScript.

Coggle requires JavaScript to display documents.

Graphs, Topological sorting, Depth-First Search, Breadth-First Search -…

- - - - If a pair of vertices (u, v) is not the same as the pair (v, u), we say that the edge (u, v) is directed from the vertex u, called the edge’s tail, to the vertex v,
        called the edge’s head.
        
        We also say that the edge (u, v) leaves u and enters v. A graph whose every edge is directed is is called directed. Directed graphs are also called digraphs.
- - - - Whether we are dealing with a dense or sparse graph may influence how we choose to represent the graph and, consequently, the running time of an algorithm being designed or used.
- - - - If a graph is sparse, the adjacency list representation may use less space than the corresponding adjacency matrix despite the extra storage consumed by pointers of the linked lists;
        
        the situation is exactly opposite for dense graphs. In general, which of the two representations is more convenient depends on the nature of the problem, on the algorithm used for solving it, and, possibly, on the type of input graph (sparse or dense).
- - - - Adjacency lists for a weighted graph have to include in their nodes not only the name of an adjacent vertex but also the weight of the corresponding edge.
- - - - In the case of a directed graph, we are usually interested in directed paths. A directed path is a sequence of vertices in which every consecutive pair of the vertices is connected by an edge directed from the vertex listed first to the vertex listed next.
- - - - Formally, a connected component is a maximal (not expandable by including another vertex and an edge) connected subgraph2 of a given graph.
        
        Graphs with several connected components do happen in real-world applications. A graph representing the Interstate highway system of the United States would be an example.
        
        It is important to know for many applications whether or not a graph under consideration has cycles. A cycle is a path of a positive length that starts and ends at the same vertex and does not traverse the same edge more than once.
- - - - At a dead end, the algorithm backs up one edge to the vertex it came from and tries to continue visiting unvisited vertices from there.
        
        The algorithm eventually halts after backing up to the starting vertex, with the latter being a dead end.
        
        By then, all the vertices in the same connected component as the starting vertex have been visited. If unvisited vertices still remain, the depth-first search must be restarted at any one of them.
- - - - Whenever a new unvisited vertex is reached for the first time, it is attached as a child to the vertex from which it is being reached.
        
        Such an edge is called a tree edge because the set of all such edges forms a forest. The algorithm may also encounter an edge leading to a previously
        visited vertex other than its immediate predecessor (i.e., its parent in the tree).
        
        Such an edge is called a back edge because it connects a vertex to its ancestor, other than the parent, in the depth-first search forest.
- - - - It is convenient to use a queue (note the difference from depth-first search!) to trace the operation of breadth-first search.
        
        The queue is initialized with the traversal’s starting vertex, which is marked as visited.
        
        On each iteration, the algorithm identifies all unvisited vertices that are adjacent to the front vertex, marks them as visited, and adds them to the queue; after that, the front vertex is
        removed from the queue.
- - - - If an edge leading to a previously visited vertex other than its immediate predecessor (i.e., its parent in the tree) is encountered, the edge is noted as a cross edge.