Graphs are an important data structure in computer science and are used to model many real-world scenarios. Here are some common interview questions related to graphs:
Graph
A graph is a collection of vertices (or nodes) and edges that connect them.
The components of a graph are:
- Vertex: a node in a graph
- Edge: a connection between two vertices
- Weight: a value associated with an edge, used to represent the cost or distance between two vertices
- Directed/Undirected: a property of an edge that indicates whether the connection is one-way or two-way
- Cycle: a path in a graph that starts and ends at the same vertex
Different ways to represent a graph
There are three common ways to represent a graph:
- Adjacency matrix: a two-dimensional array that stores a boolean value indicating whether there is an edge between two vertices
- Adjacency list: a list of lists that stores the neighbors of each vertex
- Edge list: a list of edges that stores the source vertex, destination vertex, and weight of each edge
Graph traversal algorithms:
- Breadth-first search (BFS): a traversal algorithm that explores all the vertices at the same level before moving on to the next level. BFS is used to find the shortest path between two vertices and to check if a graph is bipartite (i.e., can be colored with two colors such that no two adjacent vertices have the same color).
- Depth-first search (DFS): a traversal algorithm that explores as far as possible along each branch before backtracking. DFS is used to detect cycles in a graph and to find connected components.
Dijkstra’s algorithm
Dijkstra’s algorithm is a shortest path algorithm that finds the shortest path between a source vertex and all other vertices in a weighted graph. The algorithm works by maintaining a priority queue of vertices sorted by their distance from the source vertex. The algorithm visits each vertex in order of increasing distance and updates the distance to its neighbors. Dijkstra’s algorithm is used to find the shortest path between two points in a road network or to solve the minimum cost flow problem in transportation.
Kruskal’s algorithm
Kruskal’s algorithm is a minimum spanning tree algorithm that finds the minimum weight set of edges that connects all the vertices in an undirected graph. The algorithm works by sorting the edges by weight and adding them to the spanning tree if they do not form a cycle. Kruskal’s algorithm is used to find the minimum cost network of roads, electrical wires, or other connections.
