Graphs

Question 1

What is a graph in data structures?

Answer 1

A graph is a non-linear data structure consisting of a set of vertices (nodes) and a set of edges that connect pairs of vertices.

Question 2

What are the two main types of graphs?

Answer 2

Directed graphs (digraphs) and undirected graphs.

Question 3

What is a directed graph?

Answer 3

A graph in which edges have a direction, indicating a one-way relationship from one vertex to another.

Question 4

What is an undirected graph?

Answer 4

A graph where edges do not have direction; connections between vertices are bidirectional.

Question 5

What is a weighted graph?

Answer 5

A graph where each edge is assigned a numerical value or weight, often representing cost, distance, or time.

Question 6

What is an unweighted graph?

Answer 6

A graph where all edges are treated equally, with no associated weight.

Question 7

What is an adjacency matrix?

Answer 7

A 2D array used to represent a graph, where each cell (i, j) indicates whether an edge exists (and possibly its weight) between vertex i and vertex j.

Question 8

What is an adjacency list?

Answer 8

A collection of lists or arrays where each vertex stores a list of its neighboring vertices.

Question 9

When is an adjacency list preferred over an adjacency matrix?

Answer 9

When the graph is sparse (contains relatively few edges), since it saves space.

Question 10

What is a sparse graph?

Answer 10

A graph where the number of edges is much less than the maximum possible, typically closer to O(V) than O(V²).

Question 11

What is a dense graph?

Answer 11

A graph where the number of edges is close to the maximum number of possible edges, near O(V²).

Question 12

What is a cycle in a graph?

Answer 12

A path of edges and vertices in which a vertex is reachable from itself without repeating any edges.

Question 13

What is an acyclic graph?

Answer 13

A graph with no cycles.

Question 14

What is a DAG?

Answer 14

A Directed Acyclic Graph, meaning it has directed edges and no cycles.

Question 15

What is a path in a graph?

Answer 15

A sequence of vertices connected by a series of edges.

Question 16

What is a connected graph?

Answer 16

An undirected graph where there is a path between every pair of vertices.

Question 17

What is a strongly connected graph?

Answer 17

A directed graph in which there is a path from every vertex to every other vertex.

Question 18

What is a weakly connected graph?

Answer 18

A directed graph that becomes connected if all its edges are treated as undirected.

Question 19

What is a tree in graph theory?

Answer 19

An undirected graph that is connected and acyclic.

Question 20

How is a tree related to graphs?

Answer 20

A tree is a special case of an undirected graph with no cycles and exactly V - 1 edges.

Question 21

What is the degree of a vertex in an undirected graph?

Answer 21

The number of edges connected to the vertex.

Question 22

What is the in-degree of a vertex in a directed graph?

Answer 22

The number of edges coming into the vertex.

Question 23

What is the out-degree of a vertex in a directed graph?

Answer 23

The number of edges going out from the vertex.

Question 24

What is a self-loop in a graph?

Answer 24

An edge that connects a vertex to itself.

Question 25

What is a multigraph?

Answer 25

A graph that may contain multiple edges (parallel edges) between the same pair of vertices.

Question 26

What is a simple graph?

Answer 26

A graph with no self-loops and no more than one edge between any pair of vertices.

Question 27

What is graph traversal?

Answer 27

The process of visiting each vertex in a graph, usually using either BFS or DFS.

Question 28

What is Breadth-First Search (BFS)?

Answer 28

A graph traversal algorithm that explores vertices in layers, using a queue to visit neighbors level by level.

Question 29

What is Depth-First Search (DFS)?

Answer 29

A graph traversal algorithm that explores as far as possible along each branch before backtracking, using a stack or recursion.

Question 30

What data structure does BFS use?

Answer 30

A queue.

Question 31

What data structure does DFS typically use?

Answer 31

A stack or the program’s call stack through recursion.

Question 32

What is the time complexity of BFS or DFS using an adjacency list?

Answer 32

O(V + E), where V is the number of vertices and E is the number of edges.

Question 33

What is the time complexity of BFS or DFS using an adjacency matrix?

Answer 33

O(V²), since all vertex pairs must be checked.

Question 34

What is topological sorting in a graph?

Answer 34

A linear ordering of vertices such that for every directed edge u → v, vertex u appears before v.

Question 35

What kind of graph supports topological sort?

Answer 35

A Directed Acyclic Graph (DAG).

Question 36

What is Dijkstra’s algorithm used for?

Answer 36

Finding the shortest paths from a single source vertex to all other vertices in a graph with non-negative edge weights.

Question 37

What is Bellman-Ford algorithm used for?

Answer 37

Finding shortest paths from a source vertex in a graph that may contain negative edge weights.

Question 38

What is Floyd-Warshall algorithm used for?

Answer 38

Computing shortest paths between all pairs of vertices in a weighted graph.

Question 39

What is Prim’s algorithm used for?

Answer 39

Constructing a Minimum Spanning Tree (MST) from a connected, weighted, undirected graph.

Question 40

What is Kruskal’s algorithm used for?

Answer 40

Constructing a Minimum Spanning Tree by sorting all edges and adding them in order, avoiding cycles.

Question 41

What is a Minimum Spanning Tree (MST)?

Answer 41

A subset of edges that connects all the vertices with the minimum possible total edge weight and no cycles.

Question 42

Can a directed graph have an MST?

Answer 42

No, MSTs are only defined for undirected graphs.

Question 43

What is a bipartite graph?

Answer 43

A graph whose vertices can be divided into two sets such that no two vertices within the same set are adjacent.

Question 44

How can you check if a graph is bipartite?

Answer 44

Using BFS or DFS to try to 2-color the graph without conflicts.

Question 45

What is the shortest path problem?

Answer 45

The problem of finding the path with the smallest total weight between two vertices.

Question 46

What is a key difference between BFS and DFS for shortest path?

Answer 46

BFS finds the shortest path in unweighted graphs; DFS does not guarantee shortest paths.

Question 47

What is a bridge in a graph?

Answer 47

An edge whose removal increases the number of connected components in the graph.

Question 48

What is an articulation point?

Answer 48

A vertex whose removal increases the number of connected components in the graph.

Question 49

What is the graph coloring problem?

Answer 49

The problem of assigning colors to vertices so that no two adjacent vertices share the same color.

Question 50

What is the chromatic number of a graph?

Answer 50

The minimum number of colors needed to color the graph under the graph coloring constraint.