graph_questions_answers Flashcards
What is a graph in computer science? How does it differ from other data structures like trees?
A graph is a collection of nodes (vertices) connected by edges. It differs from a tree because a tree is a special type of graph with no cycles, hierarchical structure, and a unique path between nodes.
What are the different types of graphs? Explain each one briefly.
Undirected, Directed, Weighted, Unweighted.
What is the difference between a dense and a sparse graph?
Dense graphs have many edges (close to V^2), sparse graphs have few edges relative to the number of nodes.
What are the representations of graphs in computer science? Explain adjacency matrix and adjacency list.
Adjacency Matrix: 2D array representing connections. Adjacency List: Each vertex has a list of neighbors.
What is a connected graph? What is a strongly connected and weakly connected graph in the case of directed graphs?
Connected graph: A path exists between any two vertices. Strongly connected (directed): A path exists between all pairs. Weakly connected: Connected only if edges were treated as undirected.
What is a cyclic graph? How is it different from an acyclic graph?
Cyclic graph has at least one cycle, acyclic has none.
What is a bipartite graph? How can you check if a given graph is bipartite?
A bipartite graph has vertices divided into two sets where no edges connect vertices in the same set. Use BFS/DFS for checking.
What is a path in a graph? How does it differ from a simple path or a cycle?
A path is a sequence of edges connecting vertices, a simple path has no repeated vertices, and a cycle returns to the starting vertex.
What are the applications of graphs in real-world problems? Provide at least three examples.
Social networks (e.g., friends), GPS navigation, data routing in networks.
How do you perform a depth-first search (DFS) and breadth-first search (BFS) on a graph?
DFS uses a stack (or recursion), BFS uses a queue. DFS explores deeper first, BFS explores level by level.
What is Dijkstra’s algorithm? Explain how it is used to find the shortest path in a graph.
Dijkstra’s finds the shortest path from a source to all vertices with non-negative weights using a priority queue.
What is the Bellman-Ford algorithm? How does it compare with Dijkstra’s algorithm?
Bellman-Ford handles negative weights, has O(VE) time complexity, slower than Dijkstra but more flexible.
Explain Prim’s and Kruskal’s algorithms for finding the minimum spanning tree in a graph.
Prim’s adds edges greedily to grow the MST, Kruskal’s sorts edges and adds them if they don’t form a cycle.
What is topological sorting in a directed acyclic graph (DAG), and why is it important?
Linear ordering of vertices where each directed edge points from an earlier to a later vertex.
How do you detect a cycle in a directed and undirected graph?
DFS/Recursion stack to detect cycles in directed graphs. In undirected graphs, a back edge during DFS indicates a cycle.
What is the Floyd-Warshall algorithm, and how is it used to find shortest paths between all pairs of nodes?
Finds shortest paths between all pairs, has O(V^3) complexity.
What is graph coloring? Explain the significance of the chromatic number of a graph.
Assign colors to vertices so no two adjacent vertices share the same color, chromatic number is the minimum needed.
What are strongly connected components (SCCs) in a directed graph? How can Tarjan’s or Kosaraju’s algorithm be used to find them?
SCCs are maximal strongly connected subgraphs. Tarjan’s and Kosaraju’s algorithms use DFS to find SCCs.
What is the concept of a ‘cut vertex’ or ‘cut edge’ in a graph? How do you find them?
Cut vertex increases the number of connected components if removed. Cut edge disconnects the graph if removed.
What are Eulerian and Hamiltonian paths/cycles? How do you check if a graph contains one?
Eulerian path visits every edge once, Hamiltonian path visits every vertex once.
What is the time complexity of common graph algorithms like DFS, BFS, Dijkstra’s, and Bellman-Ford?
DFS/BFS: O(V + E). Dijkstra: O((V + E) log V). Bellman-Ford: O(VE). Floyd-Warshall: O(V^3).
How can graphs be used to represent and solve problems in social networks, like finding influencers or community detection?
Graphs represent social networks where nodes are people and edges are relationships. Algorithms can find influencers, communities.
What is the max-flow/min-cut theorem? How does the Ford-Fulkerson algorithm solve the maximum flow problem in a flow network?
Max-flow/min-cut theorem states max flow equals min cut capacity in a flow network. Ford-Fulkerson finds max flow.
Explain how graph partitioning can help in parallel computing. What are some common techniques for graph partitioning?
Graph partitioning divides a graph into subgraphs to minimize cut size, useful for parallelizing work.
