Đồ thị (Graphs) trong Cấu trúc Dữ liệu Phi tuyến tính: A đến Z

Chào mừng bạn đến với bài viết thứ 8 trong series về cấu trúc dữ liệu và giải thuật.

Trong bài viết này, chúng ta sẽ khám phá một cấu trúc dữ liệu mạnh mẽ: Đồ thị (Graphs).

Đồ thị được sử dụng rộng rãi để mô hình hóa các mối quan hệ phức tạp trong thế giới thực.

Ví dụ, mạng xã hội, bản đồ đường đi, và thậm chí cả các mạch điện tử có thể được biểu diễn bằng đồ thị.

1. Giới thiệu về Đồ thị (Graphs)

Đồ thị là một cấu trúc dữ liệu phi tuyến tính bao gồm các đỉnh (vertices) và các cạnh (edges).

Đỉnh (Vertex): Một nút trong đồ thị. Đỉnh đại diện cho một đối tượng.

Cạnh (Edge): Một kết nối giữa hai đỉnh. Cạnh đại diện cho một mối quan hệ giữa hai đối tượng.

Một đồ thị có thể là có hướng (directed) hoặc vô hướng (undirected).

Trong đồ thị có hướng, các cạnh có hướng cụ thể từ một đỉnh đến một đỉnh khác.

Trong đồ thị vô hướng, các cạnh không có hướng cụ thể và biểu thị một mối quan hệ hai chiều.

2. Các cách biểu diễn Đồ thị

Có hai cách biểu diễn đồ thị phổ biến:

2.1. Ma trận kề (Adjacency Matrix)

Ma trận kề là một ma trận hai chiều, trong đó hàng và cột đại diện cho các đỉnh của đồ thị.

Giá trị tại vị trí (i, j) của ma trận cho biết có cạnh nối giữa đỉnh i và đỉnh j hay không.

Nếu có cạnh, giá trị thường là 1 (hoặc trọng số của cạnh nếu đồ thị có trọng số).

Nếu không có cạnh, giá trị thường là 0.

Ví dụ:

// Biểu diễn đồ thị bằng ma trận kề
int[][] adjacencyMatrix = {
  {0, 1, 0, 0},
  {1, 0, 1, 1},
  {0, 1, 0, 0},
  {0, 1, 0, 0}
};

Ưu điểm của ma trận kề:

• Dễ dàng kiểm tra sự tồn tại của một cạnh giữa hai đỉnh.

Nhược điểm của ma trận kề:

• Tốn nhiều bộ nhớ, đặc biệt đối với các đồ thị thưa thớt (ít cạnh).
• Khó khăn trong việc duyệt các đỉnh kề của một đỉnh.

2.2. Danh sách kề (Adjacency List)

Danh sách kề sử dụng một danh sách (hoặc mảng) để lưu trữ các đỉnh của đồ thị.

Mỗi đỉnh trong danh sách này lại trỏ đến một danh sách khác, chứa các đỉnh kề của nó.

Điều này cho phép biểu diễn đồ thị một cách hiệu quả, đặc biệt đối với các đồ thị thưa thớt.

Ví dụ:

// Biểu diễn đồ thị bằng danh sách kề
import java.util.ArrayList;
import java.util.List;

public class Graph {
    private List> adjacencyList;

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

    public void addEdge(int source, int destination) {
        adjacencyList.get(source).add(destination);
        adjacencyList.get(destination).add(source); // Nếu là đồ thị vô hướng
    }

    public List getNeighbors(int vertex) {
        return adjacencyList.get(vertex);
    }

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

        System.out.println("Các đỉnh kề của đỉnh 1: " + graph.getNeighbors(1));
    }
}

Ưu điểm của danh sách kề:

• Tiết kiệm bộ nhớ hơn so với ma trận kề đối với đồ thị thưa thớt.
• Dễ dàng duyệt các đỉnh kề của một đỉnh.

Nhược điểm của danh sách kề:

• Khó khăn hơn trong việc kiểm tra sự tồn tại của một cạnh giữa hai đỉnh.

3. Các thuật toán tìm kiếm quan trọng

Có hai thuật toán tìm kiếm đồ thị quan trọng:

3.1. Duyệt theo chiều rộng (BFS - Breadth-First Search)

BFS duyệt đồ thị theo từng lớp, bắt đầu từ một đỉnh gốc.

Thuật toán sử dụng hàng đợi (queue) để lưu trữ các đỉnh cần duyệt.

BFS thường được sử dụng để tìm đường đi ngắn nhất trong một đồ thị không trọng số.

Ví dụ:

import java.util.*;

public class BFS {
    public static void bfs(List> adj, int startNode, int numNodes) {
        boolean[] visited = new boolean[numNodes];
        Queue queue = new LinkedList<>();

        visited[startNode] = true;
        queue.offer(startNode);

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        int numNodes = 7;
        List
       > adj = new ArrayList<>(); for (int i = 0; i < numNodes; i++) { adj.add(new ArrayList<>()); } adj.get(0).add(1); adj.get(0).add(2); adj.get(1).add(0); adj.get(1).add(3); adj.get(1).add(4); adj.get(2).add(0); adj.get(2).add(5); adj.get(2).add(6); adj.get(3).add(1); adj.get(4).add(1); adj.get(5).add(2); adj.get(6).add(2); System.out.println("BFS traversal starting from node 0:"); bfs(adj, 0, numNodes); } }

3.2. Duyệt theo chiều sâu (DFS - Depth-First Search)

DFS duyệt đồ thị bằng cách đi sâu vào một nhánh đến khi không còn đỉnh nào để duyệt.

Sau đó, thuật toán quay lui và tiếp tục duyệt các nhánh khác.

DFS thường được sử dụng để tìm đường đi giữa hai đỉnh, kiểm tra tính liên thông của đồ thị, và tìm chu trình.

Thuật toán sử dụng ngăn xếp (stack) hoặc đệ quy để thực hiện việc duyệt.

Ví dụ:

import java.util.*;

public class DFS {
    public static void dfs(List> adj, int node, boolean[] visited) {
        visited[node] = true;
        System.out.print(node + " ");

        for (int neighbor : adj.get(node)) {
            if (!visited[neighbor]) {
                dfs(adj, neighbor, visited);
            }
        }
    }

    public static void main(String[] args) {
        int numNodes = 7;
        List> adj = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            adj.add(new ArrayList<>());
        }

        adj.get(0).add(1); adj.get(0).add(2);
        adj.get(1).add(0); adj.get(1).add(3); adj.get(1).add(4);
        adj.get(2).add(0); adj.get(2).add(5); adj.get(2).add(6);
        adj.get(3).add(1);
        adj.get(4).add(1);
        adj.get(5).add(2);
        adj.get(6).add(2);

        boolean[] visited = new boolean[numNodes];
        System.out.println("DFS traversal starting from node 0:");
        dfs(adj, 0, visited);
    }
}

4. Ứng dụng của Đồ thị

Đồ thị có rất nhiều ứng dụng thực tế, bao gồm:

• Mạng xã hội: Biểu diễn các mối quan hệ giữa người dùng.
• Bản đồ đường đi: Tìm đường đi ngắn nhất giữa hai địa điểm.
• Hệ thống định vị GPS: Tính toán lộ trình di chuyển.
• Mạng máy tính: Mô hình hóa kết nối giữa các thiết bị.
• Phân tích dữ liệu: Tìm kiếm các mẫu và mối quan hệ trong dữ liệu.

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu về cấu trúc dữ liệu đồ thị, các cách biểu diễn đồ thị (ma trận kề và danh sách kề), và hai thuật toán tìm kiếm quan trọng (BFS và DFS).

Đồ thị là một công cụ mạnh mẽ để mô hình hóa các mối quan hệ phức tạp.

Hãy tiếp tục khám phá và áp dụng đồ thị vào các bài toán thực tế để nâng cao kỹ năng giải quyết vấn đề của bạn.

Hy vọng bài viết này hữu ích cho bạn. Chúc bạn thành công trên con đường chinh phục cấu trúc dữ liệu và giải thuật!