Graph Theory Concepts

What is a graph in the context of computer science?

• A graph in computer science is a tool used for plotting mathematical functions.

• A graph in computer science is a type of chart used to display numerical data.

• A graph in computer science is a visual representation of data on a coordinate plane.

• A graph in computer science is a data structure consisting of nodes (vertices) connected by edges.

Explain the Breadth-First Search (BFS) algorithm.

• BFS only visits nodes on the same level

• BFS explores nodes level by level, visiting all the nodes at the current level before moving to the next level.

• BFS starts from the deepest level and moves upwards

• BFS randomly selects nodes to explore

Describe the Depth-First Search (DFS) algorithm.

• DFS explores nodes in a random order without following any specific path.

• DFS only visits nodes that are directly connected to the root node.

• DFS starts at the leaf nodes and works its way up to the root node.

• DFS starts at the root node, explores as far as possible along each branch before backtracking, and continues until all nodes are visited.

What is Topological Sorting and when is it used?

• Topological Sorting is used to shuffle a deck of cards

• Topological Sorting is used to organize files alphabetically

• Topological Sorting is used to sort numbers in ascending order

• Topological Sorting is used in scenarios where a set of tasks need to be executed in a specific order based on dependencies between them.

Define Strongly Connected Components in a graph.

• Strongly Connected Components are subgraphs where vertices have different degrees of connectivity.

• Strongly Connected Components are subgraphs where vertices are connected by edges in only one direction.

• Strongly Connected Components in a graph are subgraphs where every vertex is reachable from every other vertex within that subgraph.

• Strongly Connected Components are subgraphs where only some vertices are reachable from others.

What are the basic components of a graph?

• Vertices and Lines

• Links and Junctions

• Nodes and Edges

• Points and Connections

How does BFS differ from DFS in terms of traversal order?

• BFS explores nodes in a random order

• BFS visits nodes level by level, while DFS explores as far as possible along each branch before backtracking.

• DFS visits nodes level by level

• BFS always starts from the root node

Can a graph have cycles in a topological sort?

• Maybe

• Yes

• No

• Sometimes

Topological Order?

• B, E, A, C, D

• B, E, D, C, A

• D, E, A, C, B

• B, E, C, A, D