Graphs cs320

What is an undirected graph?

A graph where edges do not have direction; each edge (u, v) is bidirectional.

What is a directed graph?

A graph where each edge (u, v) has a direction, from u to v.

What are nodes and edges?

Nodes (vertices) are the entities in the graph; edges represent connections between nodes.

What are n and m in a graph?

n = number of nodes; m = number of edges.

What is an adjacency matrix?

An n x n matrix where A[u][v] = 1 if there is an edge from u to v.

What is an adjacency list?

An array of lists, where each index stores the neighbors of a node.

Which graph representation is more space-efficient?

Adjacency list, especially for sparse graphs.

What is a path in a graph?

A sequence of nodes where each consecutive pair is connected by an edge.

What is a cycle in a graph?

A path where the first and last nodes are the same, and all other nodes are distinct.

What is a connected graph?

A graph where there is a path between every pair of nodes.

What is a tree in graph theory?

A connected undirected graph with no cycles.

How many edges does a tree with n nodes have?

n - 1

What is breadth-first search (BFS)?

A traversal method that explores neighbors layer by layer using a queue.

What is depth-first search (DFS)?

A traversal method that explores deeply along branches before backtracking, usually with a stack.

What is the time complexity of BFS or DFS (adjacency list)?

O(m + n)

What is a connected component?

A set of nodes such that each is reachable from the others.

How to find all connected components in a graph?

Repeatedly run BFS or DFS on unvisited nodes.

What is a bipartite graph?

A graph that can be 2-colored such that no edge connects same-colored nodes.

What prevents a graph from being bipartite?

An odd-length cycle.

What is a strongly connected directed graph?

Every node is reachable from every other node.

How to test strong connectivity?

Run BFS from a node in both original and reversed graph. If all nodes are reached, it's strongly connected.

What is a DAG?

A directed acyclic graph—contains no directed cycles.

What is topological ordering?

An ordering of nodes where each directed edge (u, v) has u before v.

Does every DAG have a topological ordering?

Yes.

What is a source in a DAG?

A node with no incoming edges.

What is a sink in a DAG?

A node with no outgoing edges.

What is the time complexity of topological sorting via in-degrees?

O(m + n)