# Algorithms

Classified in Language

Written at on English with a size of 41.41 KB.

Tweet |

### Connected and Disconnected Graph: A graph is connected if any two vertices of the graph are connected by a path and a graph is disconnected if at least two vertices of the graph are not connected by a path. If a graph G is unconnected, then every maximal connected subgraph of G is called a connected component of the graph G.

**Dense graph** is a **graph** in which the **number** of edges is close to the maximal number of edges.

**Sparse graph** is a graph in which the number of edges is close to the minimal number of edges. Sparse graph can be a disconnected graph.

- Informally, a graph with relatively few edges is
*sparse*, and a graph with many edges is*dense*. - Sparse graphs are sparsely connected (eg: Trees). Usually the number of edges is in O(n) where n is the number of vertices. Therefore adjacency lists are preferred since they require constant space for every edge.
- Dense graphs are densely connected. Here number of edges is usually O(n^2). Therefore adjacency matrix is preferred.
- To give a comparison, let us assume graph has 1000 vertices. Irrespective of whether the graph is dense or sparse, adjacency matrix requires 1000^2 = 1,000,000 values to be stored.
- If the graph is minimally connected (i.E. It is a tree), the adjacency list requires storing 2,997 values. If the graph is fully connected it requires storing 3,000,000 values.

## Storage Add Vertex Add Edge Remove Vertex Remove Edge Query

Adjacency list O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)

Adjacency matrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)

## Tree: A connected acyclic graph is called a tree. In other words, a connected graph with no cycles is called a tree.

## The edges of a tree are known as branches. Elements of trees are called their nodes. The nodes without child nodes are called leaf nodes.

- A tree with ‘n’ vertices has ‘n-1’ edges. If it has one more edge extra than ‘n-1’, then the extra edge should obviously has to pair up with two vertices which leads to form a cycle. Then, it becomes a cyclic graph which is a violation for the tree graph.