Definitions
- graph a data structure formed by a set of vertices and edges connecting those vertices.
- directed graph a graph whose edges have directions.
- path a sequence of vertices connected by edges. The length of a path is the number of its edges.
- cycle a path which has at least one edge and whose first and last vertices are the same vertice.
- acyclic graph a graph without any cycle.
- connected graph a graph where there is a path between every pair of vertices in the graph
- strongly connected vertices vertices are mutually reachable from each other
- tree an acyclic connected graph.
- spanning tree of a graph a tree with all the vertices of the graph
- forest a disjoint set of trees
Representations
There are two common representations of a graph:
- Adjacency-list: Each vertex is associated with an array of its adjacent vertices. This can be implemented either by making a vertex manage its own array or the graph to manage the arrays of all vertices via a two dimensional array.
- Adjacency-matrix: The graph maintains a matrix where the entry
(u,v)has positive value if verticesuandvare adjacent to each other.
The former representation is more flexible as it allows custom data in the edges and is more memory-efficient than the latter as it only requires O(V + E) memory whereas the latter needs O(V^2) memory. This memory efficiency comes from the fact that in the former representation memory is only allocated to existent edges. The advantages of the latter representation is that it is simpler to implement and it supports checking if an edge exists between any two vertices in only O(1) time. Therefore, it depends on the problem context to decide which representation is more appropriate.
Breadth-first search (BFS)
A graph search is an algorithm used to visit the vertices of a graph by following the graph edges in a particular order.
BFS is a graph search algorithm that first tries to visit all the vertices at the same distance from a given source vertex and then continues to visit the other nodes at farther distances. In other words, given a source vertex s, this algorithm visits all the vertices at distance k from s and then those at distance k + 1 and so on. Due to this traversing strategy, the paths between s and all its reachable vertices found by BFS is also the shortest paths between them.
This algorithm takes O(V + E) time in the worst case.
Depth-first search (DFS)
DFS is also a graph search algorithm but differs from BFS in the way it follows the graph edges. In contrast to BFS, this algorithm does not try to visit all the nodes at the same distance from a given source vertex, but instead it follows the edges leading to the farthest nodes from the source vertex that have not been discovered as soon as it sees any such edge. In other words, at each distance k from s, this algorithm visits only one node and then follows the edges going out from that node to go farther from s. When there is no such edge, it backtracks to the farthest node from s that has not been visited and then repeats the process.
Like BFS, this algorithm takes O(V + E) time in the worst case.
Topological sort
A topological sort of a directed acylic graph is a linear ordering of the graph vertices such that, if there is an edge from u to v, then u must come before v in the ordering. Topological sort only exists in acyclic graphs because it is not possible to define the linear ordering of the vertices in a graph with cycles. For example, if there is a path from u to v and also one from v to u, it is not possible to determine which one comes before the other.
A topological sort can be found by using DFS. This possibility is due to the characteristic of DFS which is that it finishes visiting a vertex only when it finishes visiting all the adjacent vertices of that vertex. Thus, if there is an edge from u to v, v must be finished before u. Therefore, if we reverse the order in which the vertices are finished during DFS, we get the topological sort.
Since topological sort is found by using DFS, it takes O(V + E) time to find a topological sort.
Source code
References
[1] Introduction to algorithms
[2] Algorithms