Graph - Spanning Tree
Overview
Before we proceed with Spanning Tree, we need to be sure that we know what Connected Graph is. If you already know - that's great but if you forgot about it, please - go to the Graph Types page and check it out again.
Now that we know what a Connected Graph is, we can dive into the concept of Spanning Tree. In simple words - it's the same as Connected Graph but with the minimum possible edges and no cycles (acyclic graph is a graph that doesn't have paths that allows to cycles).
It's very clear from the animation - first, we have the following graph:
G = {V, E}
V = {0, 1, 2, 3}
E = {(0, 1), (1, 2), (2, 3), (3,0)}
To transform it to a Spanning Tree, we need to see if there's edges that we can remove without disconnecting the nodes (maintaining the connectivity property of the graph - having a path from each node to any node).
So, we have various choices but in the example, we take out the edge that connects 1 and 2 vertices directly (E = {(0, 1), (2, 3), (3,0)}). Without it, we can still travel from 1 to 2, just not directly.
In other words, we still have a Connected Graph that's now also an Acyclic Graph and a Spanning Tree.
As already mentioned, we can have many different Spanning Trees within a Connected Graph, it's rarely a single choice so be aware of that.
Now that we know what a Spanning Tree is, let's learn Minimum Spanning Tree. It's the same concept as Spanning Tree but applied to a Weighted Connected Graph.
You can see in the second part of the animation that we have the same graph but with weighted edges. In order to extract a Minimum Spanning Tree from it, our goals is to remove edge/s that will result in the Spanning Tree with the least possible sum of edge weights.
In this case - we remove the edge (0,3) with weight '4' because the others have the sum of 6 (3 + 2 + 1). If we remove any other edge, we will end up with a higher sum. For instance, removing edge (0, 1) with weight 3, will result in a Spanning Tree with summed weight of 7 (2, 1, 4) - this would not be the Minimum Spanning Tree.
And... why do we even need Spanning Trees? Optimization!
Imagine that there are 5 different roads that lead to a town. But tree of those roads take a long time to drive on and everyone avoids them so they are staying empty. It could make sense to optimize the infrastructure by closing them and use the land for something else (urban planner specialist would know better about this topic though!).
The conclusion - Spanning Trees optimize and also organize the connections between nodes which reduces redundancy, complexity, used resources and overall improves the system.
Code
class Graph:
def __init__(self):
self.vertices = []
self.edges = []
def add_vertex(self, vertex):
self.vertices.append(vertex)
self.edges.append([0] * len(self.vertices))
for i in range(len(self.vertices) - 1):
self.edges[i].append(0)
def add_edge(self, vertex1, vertex2):
index1 = self.vertices.index(vertex1)
index2 = self.vertices.index(vertex2)
self.edges[index1][index2] = 1
self.edges[index2][index1] = 1
# If this function looks confusing, don't worry. We will take a closer look at it in next sections
def depth_first_search_traverse(self, start_vertex, visited, spanning_tree):
start_idx = self.vertices.index(start_vertex)
visited[start_idx] = True
spanning_tree.add_vertex(start_vertex)
for i in range(len(self.vertices)):
if self.edges[start_idx][i] == 1 and not visited[i]:
self.depth_first_search_traverse(self.vertices[i], visited, spanning_tree)
spanning_tree.add_edge(start_vertex, self.vertices[i])
def find_spanning_tree(self):
start_vertex = self.vertices[0]
visited = [False] * len(self.vertices)
spanning_tree = Graph()
self.depth_first_search_traverse(start_vertex, visited, spanning_tree)
return spanning_tree
# Example usage:
graph = Graph()
# Add vertices
graph.add_vertex(0)
graph.add_vertex(1)
graph.add_vertex(2)
graph.add_vertex(3)
# Add edges
graph.add_edge(0, 1)
graph.add_edge(1, 2)
graph.add_edge(2, 3)
graph.add_edge(3, 0)
# Find spanning tree
spanning_tree = graph.find_spanning_tree()
print("Spanning Tree:")
print(spanning_tree.vertices)
print(spanning_tree.edges)
class Graph {
constructor() {
this.vertices = [];
this.edges = [];
}
addVertex(vertex) {
this.vertices.push(vertex);
this.edges.push(new Array(this.vertices.length).fill(0));
for (let i = 0; i < this.vertices.length - 1; i++) {
this.edges[i].push(0);
}
}
addEdge(vertex1, vertex2) {
const index1 = this.vertices.indexOf(vertex1);
const index2 = this.vertices.indexOf(vertex2);
this.edges[index1][index2] = 1;
this.edges[index2][index1] = 1;
}
// If this function looks confusing, don't worry. We will take a closer look at it in next sections
depthFirstSearchTraverse(startVertex, visited, spanningTree) {
const startIdx = this.vertices.indexOf(startVertex);
visited[startIdx] = true;
spanningTree.addVertex(startVertex);
for (let i = 0; i < this.vertices.length; i++) {
if (this.edges[startIdx][i] === 1 && !visited[i]) {
this.depthFirstSearchTraverse(this.vertices[i], visited, spanningTree);
spanningTree.addEdge(startVertex, this.vertices[i]);
}
}
}
findSpanningTree() {
const startVertex = this.vertices[0]; // Pick the first vertex as the starting point
const visited = new Array(this.vertices.length).fill(false);
const spanningTree = new Graph();
this.depthFirstSearchTraverse(startVertex, visited, spanningTree);
return spanningTree;
}
}
// Example usage:
const graph = new Graph();
// Add vertices
graph.addVertex(0);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
// Add edges
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
// Find spanning tree
const spanningTree = graph.findSpanningTree();
console.log("Spanning Tree:");
console.log(spanningTree);
import java.util.*;
class Graph {
protected List<Integer> vertices;
protected int[][] edges;
public Graph() {
vertices = new ArrayList<>();
edges = new int[0][0];
}
public void addVertex(int vertex) {
vertices.add(vertex);
int[][] newEdges = new int[vertices.size()][vertices.size()];
for (int i = 0; i < vertices.size() - 1; i++) {
for (int j = 0; j < vertices.size() - 1; j++) {
newEdges[i][j] = edges[i][j];
}
}
edges = newEdges;
}
public void addEdge(int vertex1, int vertex2) {
int index1 = vertices.indexOf(vertex1);
int index2 = vertices.indexOf(vertex2);
edges[index1][index2] = 1;
edges[index2][index1] = 1;
}
// If this function looks confusing, don't worry. We will take a closer look at it in next sections
private void depthFirstSearchTraverse(int startVertex, boolean[] visited, Graph spanningTree) {
visited[startVertex] = true;
spanningTree.addVertex(vertices.get(startVertex));
for (int i = 0; i < vertices.size(); i++) {
if (edges[startVertex][i] == 1 && !visited[i]) {
depthFirstSearchTraverse(i, visited, spanningTree);
spanningTree.addEdge(vertices.get(startVertex), vertices.get(i));
}
}
}
public Graph findSpanningTree() {
int startVertex = vertices.get(0);
boolean[] visited = new boolean[vertices.size()];
Graph spanningTree = new Graph();
depthFirstSearchTraverse(vertices.indexOf(startVertex), visited, spanningTree);
return spanningTree;
}
}
public class Main {
public static void main(String[] args) {
Graph graph = new Graph();
// Add vertices
graph.addVertex(0);
graph.addVertex(1);
graph.addVertex(2);
graph.addVertex(3);
// Add edges
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 0);
// Find spanning tree
Graph spanningTree = graph.findSpanningTree();
System.out.println("Spanning Tree:");
System.out.println(spanningTree.vertices);
for (int[] row : spanningTree.edges) {
System.out.println(Arrays.toString(row));
}
}
}
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 4
typedef struct {
int vertices[MAX_VERTICES];
int edges[MAX_VERTICES][MAX_VERTICES];
int numVertices;
} Graph;
void addVertex(Graph* graph, int vertex) {
graph->vertices[graph->numVertices] = vertex;
for (int i = 0; i < graph->numVertices; i++) {
graph->edges[i][graph->numVertices] = 0;
graph->edges[graph->numVertices][i] = 0;
}
graph->numVertices++;
}
void addEdge(Graph* graph, int vertex1, int vertex2) {
int index1 = -1, index2 = -1;
for (int i = 0; i < graph->numVertices; i++) {
if (graph->vertices[i] == vertex1) {
index1 = i;
}
if (graph->vertices[i] == vertex2) {
index2 = i;
}
}
graph->edges[index1][index2] = 1;
graph->edges[index2][index1] = 1;
}
// If this function looks confusing, don't worry. We will take a closer look at it in next sections
void depthFirstSearchTraverse(Graph* graph, int startVertex, bool* visited, Graph* spanningTree) {
int startIdx = -1;
for (int i = 0; i < graph->numVertices; i++) {
if (graph->vertices[i] == startVertex) {
startIdx = i;
break;
}
}
visited[startIdx] = true;
addVertex(spanningTree, startVertex);
for (int i = 0; i < graph->numVertices; i++) {
if (graph->edges[startIdx][i] == 1 && !visited[i]) {
depthFirstSearchTraverse(graph, graph->vertices[i], visited, spanningTree);
addEdge(spanningTree, startVertex, graph->vertices[i]);
}
}
}
Graph findSpanningTree(Graph* graph) {
int startVertex = graph->vertices[0];
bool visited[MAX_VERTICES] = {false};
Graph spanningTree;
spanningTree.numVertices = 0;
depthFirstSearchTraverse(graph, startVertex, visited, &spanningTree);
return spanningTree;
}
int main() {
Graph graph;
graph.numVertices = 0;
// Add vertices
addVertex(&graph, 0);
addVertex(&graph, 1);
addVertex(&graph, 2);
addVertex(&graph, 3);
// Add edges
addEdge(&graph, 0, 1);
addEdge(&graph, 1, 2);
addEdge(&graph, 2, 3);
addEdge(&graph, 3, 0);
// Find spanning tree
Graph spanningTree = findSpanningTree(&graph);
printf("Spanning Tree:\n");
for (int i = 0; i < spanningTree.numVertices; i++) {
printf("%d ", spanningTree.vertices[i]);
}
printf("\n");
for (int i = 0; i < spanningTree.numVertices; i++) {
for (int j = 0; j < spanningTree.numVertices; j++) {
printf("%d ", spanningTree.edges[i][j]);
}
printf("\n");
}
return 0;
}
<?php
class Graph {
private $vertices = [];
private $edges = [];
public function addVertex($vertex) {
$this->vertices[] = $vertex;
$this->edges[] = array_fill(0, count($this->vertices), 0);
for ($i = 0; $i < count($this->vertices) - 1; $i++) {
array_push($this->edges[$i], 0);
}
}
public function addEdge($vertex1, $vertex2) {
$index1 = array_search($vertex1, $this->vertices);
$index2 = array_search($vertex2, $this->vertices);
$this->edges[$index1][$index2] = 1;
$this->edges[$index2][$index1] = 1;
}
// If this function looks confusing, don't worry. We will take a closer look at it in next sections
private function depthFirstSearchTraverse($startVertex, &$visited, &$spanningTree) {
$startIdx = array_search($startVertex, $this->vertices);
$visited[$startIdx] = true;
$spanningTree->addVertex($startVertex);
for ($i = 0; $i < count($this->vertices); $i++) {
if ($this->edges[$startIdx][$i] === 1 && !$visited[$i]) {
$this->depthFirstSearchTraverse($this->vertices[$i], $visited, $spanningTree);
$spanningTree->addEdge($startVertex, $this->vertices[$i]);
}
}
}
public function findSpanningTree() {
$startVertex = $this->vertices[0];
$visited = array_fill(0, count($this->vertices), false);
$spanningTree = new Graph();
$this->depthFirstSearchTraverse($startVertex, $visited, $spanningTree);
return $spanningTree;
}
}
// Example usage:
$graph = new Graph();
// Add vertices
$graph->addVertex(0);
$graph->addVertex(1);
$graph->addVertex(2);
$graph->addVertex(3);
// Add edges
$graph->addEdge(0, 1);
$graph->addEdge(1, 2);
$graph->addEdge(2, 3);
$graph->addEdge(3, 0);
// Find spanning tree
$spanningTree = $graph->findSpanningTree();
echo "Spanning Tree:\n";
var_export($spanningTree);
?>