Graphs Flashcards
What is a ‘graph’?
A set of vertices and edges
What does it mean for two vertices to be (adjacent)?
Two vertices are adjacent if there exists an edge connecting them.
What is a ‘Weighted Graph’?
A graph in which a values is associates w/ each edge.
What is a ‘Directed Graph’?
A graph in which every edge has a direction associated with it.
What is a ‘Dependency Graph’?
A data structure formed by a directed graph that describes the dependency of an entity in the system on the other entities of the same system.
What are the two ways in which graphs are represented?
- Adjacency Matrix
- Adjacency List
What is the runtime for determining if there is an edge between two vertices?
- Adjacency Matrix: Theta(1)
- Adjacency List: O(d)/O(V)
where d is the degree of the vertex.
What is the runtime for determining all vertices adjacent to a given vertex?
- Adjacency Matrix: Theta(V)
- Adjacency List: O(d)/O(V)
where d is the degree of the vertex.
What are the space requirements for each representation of a graph?
- Adjacency Matrix: Theta(V^2)
- Adjacency List: Theta(V+E)
When should you use an Adjacency Matrix?
- Small Graphs
- Dense Graphs
When should you use an Adjacency List?
- Large Graphs
- Sparse Graphs
What is BFS used for?
BFS is used for finding the shortest path on an unweighted graph.
What type of data structure does a BFS algorithm use?
The BFS algorithm uses a queue.
What if the count of an index in BFS is not 0?
This means that there is an unvisited layer.
What is a DFS algorithm used for.
The most fundamental algorithm used to explore nodes & Edged of a graph.
What to BFS and DFS runtimes depend on?
They both depend on how the graph is represented.
What are the runtimes for BFS?
- Adjacency Matrix: Theta (V^2)
- Adjacency List: Theta (V^2)
What are the runtimes for DFS
- Adjacency Matrix: Theta (V+E)
- Adjacency List: Theta (V+E)
Explain ‘Topological Sort’?
Topological sort takes a ‘directed’ graph and returns an array of the nodes where each node appears before all the nodes that it points to.
What type of data structure does the Topological Sort algorithm use?
A min heap priority queue.
Explain ‘Prim’s Algorithm’ and its runtime?
Prim’s Algorithm is used to construct a ‘minimum spanning tree’, which is the set of edges of the minimal cost that connects all edges.
Runtime: O(|E|lg|V|)
Explain Dijkstra’s Algorithm and its runtime?
Dijkstra’s algorithm finds a single source shortest path across the graph.
Runtime: O(|E|lg|V|)
Explain ‘Kruskal’s Algorithm’ and its runtime.
Kruskal’s algorithm sorts edges by weight and if two edges have the same weight, it puts the lower edge first.
What algorithm does Kruskal’s Algorithm depend on?
Union-find
Explain the ‘Union-find’ algorithm and its operations.
The union-find algorithm is used to detect cycles.
- makeSet(x): Creates single node trees
- union(x,y): Attaches the root of y’s subtree to the root of x’s subtree.
- find(x): Follows the pointer chain from x to the root
