Graph Data Structures: Connectedness, Density, and Trees
Classified in Computers
Written on in 
English with a size of 41.84 KB
Connected and Disconnected Graphs
A graph is connected if any two vertices of the graph are connected by a path. Conversely, a graph is disconnected if at least two vertices are not connected by a path.
If a graph G is disconnected, then every maximal connected subgraph of G is called a connected component of graph G.
Dense and Sparse Graphs
A dense graph is a graph in which the number of edges is close to the maximal possible number of edges. 
A sparse graph is a graph in which the number of edges is close to the minimal possible number of edges. A sparse graph can be a disconnected graph.
Key Characteristics and Comparison
- Informally, a graph with relatively few edges is sparse, and a graph with many edges is dense.
- Sparse graphs are sparsely connected (e.g., trees). Usually, the number of edges is in O(n) where n is the number of vertices. Therefore, adjacency lists are often preferred for sparse graphs due to their space efficiency.
- Dense graphs are densely connected. Here, the number of edges is usually O(n2). Therefore, an adjacency matrix is often preferred for dense graphs, especially for O(1) edge query time.
- To illustrate the storage difference, consider a graph with 1000 vertices:
- An adjacency matrix always requires 10002 = 1,000,000 values to be stored, regardless of density.
- If the graph is minimally connected (i.e., a tree with 999 edges), an adjacency list requires storing approximately 1000 (for vertices) + 2 * 999 (for edges in an undirected graph) = 2,998 values.
- If the graph is fully connected (499,500 edges), an adjacency list requires storing approximately 1000 (for vertices) + 2 * 499,500 (for edges) = 1,000,000 values.
Graph Representation: Operations Complexity
| Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query Edge | |
|---|---|---|---|---|---|---|
| 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) |
Trees
A tree is defined as a connected acyclic graph. In other words, it is a connected graph that contains no cycles.
- The edges of a tree are known as branches. The elements of trees are called nodes. Nodes without child nodes are called leaf nodes.
- A tree with 'n' vertices always has 'n-1' edges. If it has one more edge than 'n-1', this extra edge would necessarily form a cycle with two existing vertices, thus violating the acyclic property of a tree.