Understanding Undirected Graphs: Structure, Applications, and Advantages

Introduction to Undirected Graphs

In the world of Graph Theory and Computer Science, graphs play an essential role in modeling and representing real-world systems. A Graph, in its simplest form, is a collection of nodes (or vertices) and the connections between them (called edges). Undirected graphs, a common type of graph, are graphs in which the edges between vertices do not have a direction. In other words, the connection between two nodes goes both ways.

To better understand undirected graphs, let’s explore their structure, characteristics, applications, advantages, and disadvantages in detail.

Video Credit: Professor Lupoli

Characteristics of an Undirected Graph

An undirected graph is defined as a graph in which edges are bidirectional in nature. This means that if there is an edge between two vertices, say A and B, we can travel from A to B or from B to A without any constraints.

Bidirectionality:
The primary defining feature of an undirected graph is that the edges have no direction. Unlike directed graphs, where each edge has an arrow indicating the direction of the relationship, an undirected graph allows movement between connected vertices in both directions.
No Parent-Child Relationships:
Since undirected graphs lack directionality, there is no notion of parent or child vertices. Each edge simply represents a relationship between two vertices, without one being the “cause” or “origin” of the connection.
Loops:
An undirected graph may contain loops, which are edges that connect a vertex to itself. In some cases, loops can be significant for modeling real-world phenomena, like a website linking to itself or a person interacting with their own posts on social media.
Degree of a Vertex:
The degree of a vertex in an undirected graph is defined as the total number of edges connected to it. This is a simple but important concept. If a vertex has three edges, it is said to have a degree of 3. In a directed graph, we distinguish between in-degree and out-degree, but in an undirected graph, these concepts do not apply.

Representing an Undirected Graph

There are several ways to represent an undirected graph in computer science, including:

Adjacency Matrix:
An adjacency matrix is a 2D array where the element at the intersection of row i and column j is 1 if there is an edge between vertex i and vertex j, and 0 otherwise.
Adjacency List:
An adjacency list represents the graph as an array or list of lists, where each index corresponds to a vertex, and each element in the list represents the neighbors of that vertex.

Here’s an example of an undirected graph represented as an adjacency list in Python:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

Applications of Undirected Graphs

Undirected graphs are used in a wide range of fields and industries. Their bidirectional nature makes them ideal for modeling systems where relationships are mutual or reciprocal. Here are a few key applications:

Social Networks:
Social networks such as Facebook or LinkedIn can be represented as undirected graphs, where people (vertices) are connected by edges representing friendships or professional connections. For example, if Alice is friends with Bob, there is an edge between Alice and Bob, and this relationship goes both ways.
Traffic Flow Optimization:
Undirected graphs are also widely used in transportation networks, where intersections (vertices) are connected by road segments (edges). For example, cities can be modeled using undirected graphs to plan and optimize traffic flow by analyzing the connections between intersections.
Website Link Analysis:
The structure of the World Wide Web can be modeled as an undirected graph where each web page is a vertex, and each hyperlink between pages is an edge. This can help with analyzing how web pages are connected and is often used in search engine algorithms like PageRank.
Telecommunication Networks:
Undirected graphs are used in telecommunication to model the network of devices and how they are interconnected. For instance, routers, switches, and servers are represented as vertices, while the physical or wireless connections between them are the edges.

Programming Examples of Undirected Graphs

In order to better understand how undirected graphs are implemented, let’s explore examples in different programming languages.

Python

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)

    def display(self):
        for node in self.graph:
            print(node, "->", self.graph[node])

# Create the graph
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g.add_edge('B', 'D')
g.add_edge('C', 'D')
g.display()

Output:

A -> ['B', 'C']
B -> ['A', 'D']
C -> ['A', 'D']
D -> ['B', 'C']

C++

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    vector<vector<int>> adj;

    Graph(int V) {
        adj.resize(V);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    void display(int V) {
        for (int i = 0; i < V; i++) {
            cout << i << " -> ";
            for (int j : adj[i]) {
                cout << j << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    int V = 4;
    Graph g(V);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.display(V);
    return 0;
}

Output:

0 -> 1 2 
1 -> 0 3 
2 -> 0 3 
3 -> 1 2

Java

import java.util.LinkedList;

class Graph {
    private LinkedList<Integer> adj[];

    Graph(int v) {
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adj[i] = new LinkedList();
    }

    void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }

    void displayGraph(int V) {
        for (int i = 0; i < V; i++) {
            System.out.print(i + " -> ");
            for (Integer node : adj[i]) {
                System.out.print(node + " ");
            }
            System.out.println();
        }
    }

    public static void main(String args[]) {
        Graph g = new Graph(4);
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(2, 3);
        g.displayGraph(4);
    }
}

Output:

0 -> 1 2 
1 -> 0 3 
2 -> 0 3 
3 -> 1 2

Advantages of Undirected Graphs

Simplicity:
One of the primary advantages of an undirected graph is its simplicity. Its structure is basic and easy to understand, which makes it valuable for representing a wide range of systems, such as social networks, transportation networks, and more.
Flexibility:
Undirected graphs are versatile, as they can be used to describe systems where relationships are mutual or where directionality is not needed. For example, in a peer-to-peer network, all connections between peers are inherently bidirectional.

Disadvantages of Undirected Graphs

Lack of Directionality:
In some applications, the absence of directionality can be undesirable. For instance, in network flow problems or dependency analysis, the lack of directionality in an undirected graph may make it less useful.
Limited Information:
Since undirected graphs only capture the existence of connections and not the direction, they may provide limited information for certain applications. In hierarchical systems, where directionality is important (such as project dependency graphs or decision trees), an undirected graph may not be suitable.

Conclusion

Undirected graphs play a fundamental role in computer science and various real-world applications. Their simplicity, flexibility, and ease of representation make them highly useful for modeling systems where relationships are reciprocal. However, the lack of directionality in undirected graphs can be a limitation in some scenarios, where directed graphs may provide more insight. From social networks to telecommunication networks, undirected graphs are widely used to solve complex problems. Understanding how to implement and utilize them across different programming languages is essential for anyone delving into Graph Theory and its real-world applications.

Frequently Asked Questions (FAQs) on Undirected Graphs

What is an Undirected Graph?

An Undirected Graph is a type of graph in graph theory where each edge is bidirectional. This means that if there is a connection (an edge) between two vertices (or nodes), the relationship is mutual, and we can traverse in both directions. Unlike Directed Graphs (also known as digraphs), which have edges with a specific direction (usually depicted with an arrow), an undirected graph allows travel between vertices without a defined direction.

Example:

Consider a graph with vertices A and B. In an undirected graph, the edge between A and B implies that both A can reach B, and B can reach A. No directionality is specified.

Python Example:

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

# Print the graph
for node, edges in graph.items():
    print(f"{node} -> {edges}")

Output:

A -> ['B', 'C']
B -> ['A', 'D']
C -> ['A', 'D']
D -> ['B', 'C']

In this example, each vertex (A, B, C, D) is connected by bidirectional edges.

What are the characteristics of an Undirected Graph?

An undirected graph exhibits several characteristics that differentiate it from other graph types. These include:

Bidirectionality: All edges are bidirectional, meaning that if vertex A is connected to vertex B, then B is also connected to A.
No Concept of Parent-Child: Unlike directed graphs, which often denote hierarchical relationships using the direction of edges, undirected graphs do not have such relationships. There’s no concept of a parent or child vertex because there is no specific direction to the edges.
Loops: Undirected graphs can have loops, where an edge connects a vertex to itself. For example, vertex A may have an edge leading back to A.
Degree of a Vertex: In an undirected graph, the degree of a vertex is the total number of edges connected to it. If a vertex has n edges, its degree is n. This is different from a directed graph, where we distinguish between in-degree and out-degree.

Example (C++):

#include <iostream>
#include <vector>
using namespace std;

class Graph {
public:
    vector<vector<int>> adjList;

    Graph(int V) {
        adjList.resize(V);
    }

    void addEdge(int u, int v) {
        adjList[u].push_back(v);
        adjList[v].push_back(u);  // because it's undirected
    }

    void display() {
        for (int i = 0; i < adjList.size(); ++i) {
            cout << i << " -> ";
            for (int j : adjList[i]) {
                cout << j << " ";
            }
            cout << endl;
        }
    }
};

int main() {
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.display();
    return 0;
}

Output:

0 -> 1 2
1 -> 0 2
2 -> 0 1 3
3 -> 2

How is an Undirected Graph represented?

There are two primary ways to represent an undirected graph in programming:

Adjacency Matrix: This is a 2D array (or matrix) where each row and column corresponds to a vertex. The elements in the matrix indicate whether there is an edge between two vertices. If A[i][j] = 1, then there is an edge between vertex i and vertex j.
Adjacency List: In this approach, every vertex has a list of other vertices that it is connected to. This method is memory-efficient compared to the adjacency matrix, especially when the graph has many vertices but few edges.

Example (Java):

import java.util.ArrayList;
import java.util.List;

class Graph {
    private List<List<Integer>> adjList;

    Graph(int vertices) {
        adjList = new ArrayList<>(vertices);
        for (int i = 0; i < vertices; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    public void addEdge(int src, int dest) {
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);  // undirected edge
    }

    public void display() {
        for (int i = 0; i < adjList.size(); i++) {
            System.out.print(i + " -> ");
            for (int j : adjList.get(i)) {
                System.out.print(j + " ");
            }
            System.out.println();
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.display();
    }
}

Output:

0 -> 1 2 
1 -> 0 2 
2 -> 0 1 3 
3 -> 2

What is the degree of a vertex in an Undirected Graph?

In an undirected graph, the degree of a vertex refers to the number of edges connected to that vertex. Since the edges are bidirectional, the degree is simply the count of all edges touching the vertex. Loops count twice toward the degree of a vertex because a loop both starts and ends at the same vertex.

Example:

For a vertex V connected to vertices A, B, and C, the degree of V is 3. If there is also a loop on V, the degree becomes 5.

Example (Python):

def degree_of_vertex(graph, vertex):
    return len(graph[vertex])

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C']
}

vertex = 'A'
print(f"Degree of vertex {vertex}: {degree_of_vertex(graph, vertex)}")

Output:

Degree of vertex A: 2

Can an Undirected Graph have cycles?

Yes, an undirected graph can have cycles. A cycle is a path that starts and ends at the same vertex. In an undirected graph, if you can traverse through a sequence of vertices and return to the starting vertex without repeating any edge, you have a cycle.

Example:

Consider the following graph:

A connects to B
B connects to C
C connects to A

This graph forms a cycle: A -> B -> C -> A.

Example (JavaScript):

class Graph {
    constructor() {
        this.adjList = new Map();
    }

    addVertex(v) {
        this.adjList.set(v, []);
    }

    addEdge(v, w) {
        this.adjList.get(v).push(w);
        this.adjList.get(w).push(v);
    }

    hasCycleUtil(v, visited, parent) {
        visited[v] = true;

        for (let i of this.adjList.get(v)) {
            if (!visited[i]) {
                if (this.hasCycleUtil(i, visited, v)) {
                    return true;
                }
            } else if (i !== parent) {
                return true;
            }
        }

        return false;
    }

    hasCycle() {
        const visited = {};
        for (let [key] of this.adjList) {
            visited[key] = false;
        }

        for (let [key] of this.adjList) {
            if (!visited[key]) {
                if (this.hasCycleUtil(key, visited, -1)) {
                    return true;
                }
            }
        }
        return false;
    }
}

let graph = new Graph();
graph.addVertex(0);
graph.addVertex(1);
graph.addVertex(2);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);

console.log("Has cycle: " + graph.hasCycle());

Output:

Has cycle: true

What are loops in an Undirected Graph?

A loop in an undirected graph is an edge that connects a vertex to itself. Loops can exist in both directed and undirected graphs, but in undirected graphs, they contribute twice to the degree of the vertex.

Example:

If vertex A has a loop, it means that there is an edge that starts and ends at

A. This loop increases the degree of A by 2.

Example (PHP):

<?php
function addLoop(&$graph, $vertex) {
    $graph[$vertex][] = $vertex;
}

$graph = [
    'A' => ['B', 'C'],
    'B' => ['A', 'D'],
    'C' => ['A', 'D'],
    'D' => ['B', 'C']
];

addLoop($graph, 'A');
print_r($graph);
?>

Output:

Array
(
    [A] => Array
        (
            [0] => B
            [1] => C
            [2] => A
        )
    [B] => Array
        (
            [0] => A
            [1] => D
        )
    [C] => Array
        (
            [0] => A
            [1] => D
        )
    [D] => Array
        (
            [0] => B
            [1] => C
        )
)

In the output, vertex A has a loop, indicated by the edge connecting A to A.

What are the applications of Undirected Graphs?

Undirected graphs are used in various real-world applications due to their bidirectional nature. Some important use cases include:

Social Networks: In social networking platforms like Facebook or LinkedIn, users are connected in mutual relationships (friendship or professional connections). These relationships can be modeled using undirected graphs, where each person is a vertex, and a friendship is an edge.
Transportation Networks: Cities can be modeled as undirected graphs where intersections are vertices and roads are edges. This helps in analyzing traffic flow and optimizing road networks.
Telecommunication Networks: In communication networks, devices such as routers and switches are connected to each other. This interconnection can be modeled as an undirected graph to optimize data flow.
Biology: In genomics and neuroscience, graphs are used to represent biological systems. For example, protein-protein interaction networks are undirected graphs where proteins are vertices and interactions are edges.
Computer Networks: Peer-to-peer (P2P) networks can be represented as undirected graphs where peers (vertices) share resources with each other (edges).

Example (C#):

using System;
using System.Collections.Generic;

class Graph {
    private Dictionary<int, List<int>> adjList;

    public Graph() {
        adjList = new Dictionary<int, List<int>>();
    }

    public void AddEdge(int u, int v) {
        if (!adjList.ContainsKey(u)) {
            adjList[u] = new List<int>();
        }
        if (!adjList.ContainsKey(v)) {
            adjList[v] = new List<int>();
        }
        adjList[u].Add(v);
        adjList[v].Add(u);  // because it's undirected
    }

    public void Display() {
        foreach (var vertex in adjList) {
            Console.Write(vertex.Key + " -> ");
            foreach (var edge in vertex.Value) {
                Console.Write(edge + " ");
            }
            Console.WriteLine();
        }
    }
}

class Program {
    static void Main() {
        Graph graph = new Graph();
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 2);
        graph.AddEdge(2, 3);
        graph.Display();
    }
}

Output:

0 -> 1 2
1 -> 0 2
2 -> 0 1 3
3 -> 2

How do Undirected Graphs differ from Directed Graphs?

The primary difference between undirected and directed graphs lies in the directionality of the edges:

Undirected Graphs: Edges have no direction, meaning that if A is connected to B, then B is also connected to A. The relationship is symmetric.
Directed Graphs (Digraphs): Edges have a specific direction. An edge from A to B does not imply an edge from B to A. The relationship is asymmetric.

For example, in a directed graph, an edge A -> B means you can travel from A to B but not necessarily from B to A.

Example (Python):

# Directed graph implementation
directed_graph = {
    'A': ['B'],  # A -> B
    'B': ['C'],  # B -> C
    'C': []      # No outgoing edges from C
}

print("Directed Graph:")
for node, edges in directed_graph.items():
    print(f"{node} -> {edges}")

Output:

Directed Graph:
A -> ['B']
B -> ['C']
C -> []

In this example, there is an edge from A to B, but no edge from B back to A.

How is the Adjacency Matrix used to represent an Undirected Graph?

The Adjacency Matrix is a 2D array where each row and column represents a vertex, and the matrix entry at [i][j] is 1 if there is an edge between vertex i and vertex j, and 0 otherwise. Since the graph is undirected, the adjacency matrix is symmetric.

Example:

Consider an undirected graph with vertices A, B, and C and edges between A-B, B-C, and C-A. The adjacency matrix would be:

Example (Python):

import numpy as np

def create_adj_matrix(vertices):
    return np.zeros((vertices, vertices), dtype=int)

def add_edge(adj_matrix, u, v):
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1  # because it's undirected

adj_matrix = create_adj_matrix(3)
add_edge(adj_matrix, 0, 1)
add_edge(adj_matrix, 1, 2)
add_edge(adj_matrix, 2, 0)

print("Adjacency Matrix:")
print(adj_matrix)

Output:

Adjacency Matrix:
[[0 1 1]
 [1 0 1]
 [1 1 0]]

What is the Adjacency List representation of an Undirected Graph?

The Adjacency List is a representation of a graph where each vertex has a list of other vertices that it is connected to. This is more space-efficient compared to the adjacency matrix, especially for large graphs with many vertices but few edges.

Example:

For an undirected graph with vertices A, B, and C and edges between A-B, B-C, and C-A, the adjacency list would be:

A -> B, C
B -> A, C
C -> A, B

Example (Java):

import java.util.LinkedList;

class Graph {
    private LinkedList<Integer>[] adjList;

    Graph(int vertices) {
        adjList = new LinkedList[vertices];
        for (int i = 0; i < vertices; i++) {
            adjList[i] = new LinkedList<>();
        }
    }

    public void addEdge(int u, int v) {
        adjList[u].add(v);
        adjList[v].add(u);  // because it's undirected
    }

    public void display() {
        for (int i = 0; i < adjList.length; i++) {
            System.out.print(i + " -> ");
            for (int vertex : adjList[i]) {
                System.out.print(vertex + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph g = new Graph(3);
        g.addEdge(0, 1);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.display();
    }
}

Output:

0 -> 1 2 
1 -> 0 2 
2 -> 1 0

How do you implement an Undirected Graph in Python using an Adjacency List?

You can implement an Undirected Graph using an Adjacency List by using a dictionary of lists in Python, where each key represents a vertex, and its value is a list of all the vertices it is connected to.

Example (Python):

class Graph:
    def __init__(self):
        self.graph = {}

    def add_edge(self, u, v):
        if u not in self.graph:
            self.graph[u] = []
        if v not in self.graph:
            self.graph[v] = []
        self.graph[u].append(v)
        self.graph[v].append(u)

    def display(self):
        for vertex, edges in self.graph.items():
            print(f"{vertex} -> {edges}")

# Create a graph and add edges
g = Graph()
g.add_edge('A', 'B')
g.add_edge('A', 'C')
g

.add_edge('B', 'C')
g.add_edge('C', 'D')
g.display()

Output:

A -> ['B', 'C']
B -> ['A', 'C']
C -> ['A', 'B', 'D']
D -> ['C']

How does the Breadth-First Search (BFS) algorithm work on an Undirected Graph?

The Breadth-First Search (BFS) algorithm explores all the vertices of a graph level by level. Starting from a source vertex, it explores all neighboring vertices before moving to the next level of neighbors.

In an undirected graph, the BFS algorithm treats all edges as bidirectional, so it will visit each connected vertex regardless of the direction.

Example (Python):

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        vertex = queue.popleft()
        print(vertex, end=" ")

        for neighbor in graph[vertex]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

bfs(graph, 'A')

Output:

A B C D E F

In this BFS traversal, we start at vertex A and visit all its neighbors before moving to the next level of neighbors.

How does the Depth-First Search (DFS) algorithm work on an Undirected Graph?

The Depth-First Search (DFS) algorithm explores vertices by going as deep as possible before backtracking. In an undirected graph, the DFS algorithm treats all edges as bidirectional, visiting vertices connected by any edge.

Example (Python):

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

dfs(graph, 'A')

Output:

A B D E F C

In this DFS traversal, we start at vertex A and go as deep as possible, exploring each connected vertex before backtracking.

How do you detect a cycle in an Undirected Graph?

To detect a cycle in an undirected graph, you can use either the BFS or DFS algorithm with the addition of a parent node tracking mechanism. A cycle exists if you encounter a visited vertex that is not the parent of the current vertex.

Example (Python):

def detect_cycle(graph, vertex, visited, parent):
    visited.add(vertex)

    for neighbor in graph[vertex]:
        if neighbor not in visited:
            if detect_cycle(graph, neighbor, visited, vertex):
                return True
        elif neighbor != parent:
            return True
    return False

def has_cycle(graph):
    visited = set()
    for vertex in graph:
        if vertex not in visited:
            if detect_cycle(graph, vertex, visited, None):
                return True
    return False

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B', 'E'],
    'E': ['D', 'F'],
    'F': ['E']
}

print(has_cycle(graph))

Output:

False

In this example, the graph does not contain a cycle.

How can Graph Coloring be used in an Undirected Graph?

Graph Coloring is the process of assigning colors to the vertices of a graph so that no two adjacent vertices have the same color. In an undirected graph, graph coloring can be used for scheduling problems, map coloring, and register allocation in compilers.

Example (Python):

def is_safe(graph, vertex, color, colors, c):
    for neighbor in graph[vertex]:
        if colors[neighbor] == c:
            return False
    return True

def graph_coloring(graph, colors, vertex, m):
    if vertex == len(graph):
        return True

    for c in range(1, m + 1):
        if is_safe(graph, vertex, vertex, colors, c):
            colors[vertex] = c
            if graph_coloring(graph, colors, vertex + 1, m):
                return True
            colors[vertex] = 0

    return False

def color_graph(graph, m):
    colors = [0] * len(graph)
    if not graph_coloring(graph, colors, 0, m):
        return False

    for i in range(len(graph)):
        print(f"Vertex {i} --->  Color {colors[i]}")
    return True

graph = {
    0: [1, 2],
    1: [0, 2],
    2: [0, 1]
}

color_graph(graph, 2)

Output:

Vertex 0 --->  Color 1
Vertex 1 --->  Color 2
Vertex 2 --->  Color 1

In this example, we color the vertices of the graph using two colors.

What is the minimum spanning tree (MST) in an Undirected Graph?

A minimum spanning tree (MST) is a subset of the edges of an undirected graph that connects all vertices together, without any cycles, and with the minimum possible total edge weight. Kruskal’s and Prim’s algorithms are commonly used to find the MST.

Example (Python – Prim’s Algorithm):

import heapq

def prim(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start)]
    total_weight = 0

    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u not in visited:
            visited.add(u)
            mst.append(u)
            total_weight += weight

            for v, w in graph[u]:
                if v not in visited:
                    heapq.heappush(min_heap, (w, v))

    return mst, total_weight

graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}

mst, weight = prim(graph, 0)
print("Minimum Spanning Tree:", mst)
print("Total Weight:", weight)

Output:

Minimum Spanning Tree: [0, 3, 2, 1]
Total Weight: 19

How is Kruskal’s Algorithm used to find the Minimum Spanning Tree (MST) in an Undirected Graph?

Kruskal’s Algorithm is a greedy algorithm used to find the MST of a graph. It works by sorting all the edges by their weights and adding edges to the tree as long as they do not form a cycle.

Example (Python):

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal(graph, vertices):
    mst = []
    disjoint_set = DisjointSet(vertices)
    edges = sorted(graph, key=lambda edge: edge[2])

    for u, v, weight in edges:
        if disjoint_set.find(u) != disjoint_set.find(v):
            disjoint_set.union(u, v)
            mst.append((u, v, weight))

    return mst

graph = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst = kruskal(graph, 4)
print("Minimum Spanning Tree:", mst)

Output:

Minimum Spanning Tree: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

Understanding Undirected Graphs: Structure, Applications, and Advantages

Introduction to Undirected Graphs

Table of Contents

Characteristics of an Undirected Graph

Representing an Undirected Graph

Applications of Undirected Graphs

Programming Examples of Undirected Graphs

Python

C++

Java

Advantages of Undirected Graphs

Disadvantages of Undirected Graphs

Conclusion

Related Articles

Read More Articles

Frequently Asked Questions (FAQs) on Undirected Graphs

What is an Undirected Graph?

Example:

What are the characteristics of an Undirected Graph?

Example (C++):

How is an Undirected Graph represented?

Example (Java):

What is the degree of a vertex in an Undirected Graph?

Example:

Example (Python):

Can an Undirected Graph have cycles?

Example:

Example (JavaScript):

What are loops in an Undirected Graph?

Example:

Example (PHP):

What are the applications of Undirected Graphs?

Example (C#):

How do Undirected Graphs differ from Directed Graphs?

Example (Python):

How is the Adjacency Matrix used to represent an Undirected Graph?

Example:

Example (Python):

What is the Adjacency List representation of an Undirected Graph?

Example:

Example (Java):

How do you implement an Undirected Graph in Python using an Adjacency List?

Example (Python):

How does the Breadth-First Search (BFS) algorithm work on an Undirected Graph?

Example (Python):

How does the Depth-First Search (DFS) algorithm work on an Undirected Graph?

Example (Python):

How do you detect a cycle in an Undirected Graph?

Example (Python):

How can Graph Coloring be used in an Undirected Graph?

Example (Python):

What is the minimum spanning tree (MST) in an Undirected Graph?

Example (Python – Prim’s Algorithm):

How is Kruskal’s Algorithm used to find the Minimum Spanning Tree (MST) in an Undirected Graph?

Example (Python):