Undirected Graph

No arrows for the edges.

Definition, notation:

A graph $G$ is pair $(V,E)$:

• V is a finite set, whose elements are called vertices
• E is a finite set, whose elements are unordered pairs of distinct vertices, and are called edges. Convention: n is the number of vertices, m is the number of edges.

Data structures

• adjacency list: an array $A[\mathrm{1..}n]$ s.t. $A[v]$ is the linked list of all edges connected to $v$. $2m$ list cells, total size $\Theta (n+m)$, but testing if an edge exists is not $O(1)$.
  • (Each edge creates two cells. that is why it’s 2m).
• adjacency matrix: a $(0,1)$ matrix $M$ of size $n\times n$, with $M[v,w]=1$ iff $v,w$ is an edge. size $\Theta (n^2)$, but testing if an edge exists is $O(1)$
  • 0 if v,w is not an edge, and 1 if v,w is an edge

Which one is better?

It depends. If you have a graph that is not full, that has a few edge, the number of edge can be linear, so choosing the list would give you $\Theta (n)$ instead of $\Theta (n^2)$.

Choose the matrix if there is a dense amount of edges.

Can you compute BFS on an undirected graph to get the connected components?

Yes, you can use BFS (Breadth-First Search) to compute the connected components of an undirected graph. Here’s how you can do it: