Type of graphs: undirected, directed (indegree, outdegree)
Degree: number of edges incident to it.
Spanning tree: a subgraph that contains all of that graph’s vertices and is a single tree; spaning forest: union of spanning trees of its connected components.
Properties of a tree:
- V-1 number of edges, acyclic, connected;
- Removing any edge disconnects it, adding any edge creates a cycle,
- Exactly one simple path connects each pair of vertices.
Density: a graph is considered sparse when there are relatively few possible edges present. The number of edges is within a small constant factor of V.
Bipartite: a graph whose vertices we can divide into two sets such that all edges connect a vertex in one set with a vertex in the other set.
Time complexity calculations: sum of degrees of all vertices = 2E (# of edges).
Transitive Closure: Given a directed graph, find out if a vertex j is reachable from another vertex i for all vertex pairs (i, j) in the given graph. Here reachable mean that there is a path from vertex i to j. The reach-ability matrix is called the transitive closure of a graph.
It is usually dense, thus we can use an adjacency array to represent it.
Another example: a V-vertex directed cycle which has V directed edge, has a transitive closure as a complete digraph with V² directed edges.
Algorithms: BFS, DFS, UF, Topological Sort (Digraph), Strong Connectivity (Kosaraju’s Algo).
Reference: The textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne
