Graphs Flashcards
What is a graph?
A graph is a structure containing vertices (V) and edges (E) connection the vertices.
G = (V,E)
How can graphs be represented?
Graphs can be represented as
- adjacency lists or
- adjacency matrix
What are the advantages of adjacency lists / matrices over each other?
Adjacency-list representations provide a compact way to represent sparse graphs - those for which |E| is much less than |V|². Also we can adapt adjacency lists to represent weighted graphs. We simply store the weight w(u,v) of the edge (u,v) with vertex v in u’s adjacency list. Memory -> O(V + E)
Adjacency-matrix representations, however, are preferred when the graph is dense - |E| is close to |V|² or when we need to be able to tell quickly if there is an edge connection two given vertices. It provides a quick way to determine whether a given edge (u,v) is present in the graph instead of having to search for v in the adjacency list Adj[u]. However, this has the cost of using asymptotically more memory O(V²).
What is the breadth-first search?
Given a graph G = (V,E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to “discover” every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. For any vertex v reachable from s, the simple path in the breadth-first tree from s to v corresponds to a “shortest-path” from s to v in G, that is, a path containing the smallest number of edges.
What is the running time of breadth-first search?
Each vertex is visited (queued) exactly once, and each vertex’ adjacency list is scanned exactly once, so the running time is O(V + E) (linear time)
What is the depth-first search?
Depth-first search explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it.
Once all of v’s edges have been explored, the search “backtracks” to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex.
If any undiscovered vertices remain, then depth-first search selects one of them as a new source, and it repeats the search from that source. The algorithm repeats this entire process until it has discovered every vertex.
What is the running time of depth-first search?
Each vertex is visited once, and each vertex’ adjacency list is scanned exactly once, so the running time is O(V + E) (linear time)
Which of BFS or DFS should be used to find the shortest path in unweighted graphs?
Only BFS can be used to find the shortest path
How can the edges in a depth-first search graph be classified?
There are 4 edge types in terms of the depth-first forest G_pi produced by a depth-first search on G:
- Tree edges are edges in the depth-first forest G_pi. Edge (u,v) is a tree edge if v was first discovered by exploring edge (u,v)
- Back edges are those edges (u,v) connection a vertex u to an ancestor v in a depth-first tree. We consider self-loops, which may occur in directed graphs, to be back edges
- Forward edges are those nontree edges (u,v) connecting a vertex u to a descendant v in a depth-first tree
- Cross edges are all other edges. They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees.
What is a topological sort of a graph?
A topological sort of a dag (directed acyclic graph) G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible)
What are strongly connected components?
A strongly connected component of a directed graph G = (V,E) is a maximal set of vertices C such that for every pair of vertices u and v in C, we have bot u ~> v and v ~> u; that is, vertices u and v are reachable from each other.
How can strongly connected components be found?
First, we are calculating the transpose of G, in which the directions of the edges in G are reversed.
Then, run the DFS(G) to compute finishing times u.f for each vertex u and then call DFS(G’), but in the main loop of DFS, consider the vertices in order of decreasing u.f.
Output the vertices of each tree in the depth-first forest formed by DFS(G’) as a separate strongly connected component
What is a minimum spanning tree?
A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.
Can shortest path algorithms contain cycles?
No, because if we would remove the cycle from the path we would still have the same source and destination with a lower path weigt.
What is the Bellman-Ford algorithm?
The Bellman-Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all the other vertices in a weighted graph. It is slower than Dijkstra’s algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.
It can detect and report negative cycles, in which case a finite solution cannot be found.
