Please enable JavaScript.
Coggle requires JavaScript to display documents.
Graphs, As to the structure of a BFS forest of an undirected graph, it can…
Graphs
we have the following inequality for the number of edges |E| possible in an undirected graph with |V| vertices and no loops:
0 ≤ |E| ≤ |V |(|V | − 1)/2.
Graphs for computer algorithms are usually represented in one of two ways: the adjacency matrix and adjacency lists.
The adjacency matrix of a graph with n vertices is an n × n boolean matrix with one row and one column for each of the graph’s vertices.
The adjacency lists of a graph or a digraph is a collection of linked lists, one for each vertex, that contain all the vertices adjacent to the list’s vertex.
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.
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.
Depth-First Search
Starts a graph’s traversal at an arbitrary vertex by marking it as visited. On each iteration, the algorithm proceeds to an unvisited vertex that
is adjacent to the one it is currently in. This
process continues until a vertex with no adjacent unvisited vertices is encountered.
In examples, break ties will follow the alphabetical order of the vertices
If unvisited vertices still remain, the depth-first
search must be restarted at any one of them
It is convenient to use a stack to trace the operation of depth-first search. We push a vertex onto the stack when the vertex is reached for the first time and we pop a vertex off the stack when it becomes a dead end.
It is also very useful to construct the so-called depth-first search forest. The starting vertex of the traversal serves as the root of the first tree in such a forest 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.
This algorithm is quite efficient since it takes just the time proportional to the size of the data structure used for representing the graph in question.
:check: For the adjacency
matrix the traversal time is in Θ(|V|^2)
:check: For the adjacency list
representation it's in Θ(|V |+|E|)
Breadth-First Search
Is a traversal for the cautious. It proceeds in
a concentric manner by visiting first all the vertices that are adjacent to a starting vertex, then all unvisited vertices two edges apart from it, and so on, until all the vertices in the same connected component as the starting vertex are visited.
If there still remain unvisited vertices, the algorithm has to be restarted at an arbitrary vertex of another connected component of the graph.
It is convenient to use a queue. 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.
It is useful to accompany a BFS traversal by constructing the so-called breadth-first search forest.
The traversal’s starting vertex
serves as the root of the first tree in such a forest. Whenever a new unvisited vertex is reached for the first time, the vertex is attached as a child to the vertex it is being reached from with an edge called a tree edge.
Breadth-first search has the efficiency
:check: For the adjacency matrix representation :Θ(|V|^2)
:check: For the adjacency list representation
Θ(|V |+|E|)
Topological Sorting
There are only two notable differences between undirected and directed graphs in representing them:
:one: the adjacency matrix of a directed graph does not have to be symmetric.
:two: an edge in a directed graph has just one (not two) corresponding nodes in the digraph’s adjacency lists.
for topological sorting to be possible, a
digraph in question must be a dag( a DFS forest of a digraph that has no back edges).
two efficient algorithms that both verify whether a digraph is a dag:
:one: perform a DFS traversal and note the order in which vertices become dead-ends.
:two: repeatedly, identify in a remaining digraph a source, which is a vertex with no incoming edges, and delete it along with all the edges outgoing from it.
Note that the solution obtained by the source-removal algorithm is different from the one obtained by the DFS-based algorithm.
As to the structure of a BFS forest of an undirected graph, it can also have two kinds of edges: tree edges(are the ones used to reach previously unvisited vertices)
and cross edges(connect vertices to those visited before).
Unlike back edges in a DFS tree, they connect vertices either on the same or adjacent levels of a BFS tree.
BFS can be used to check connectivity and acyclicity of a graph, essentially in the same manner as DFS can. It is not applicable, however, for several less straightforward applications such as finding articulation points.
Advantages of using BSF rather than DFS: BFS can be used for finding a path with the fewest number of edges between two given vertices.
-
