Data Structure & Algorithm- Graph Algorithms - Introduce

Trong thế giới thực, nhiều vấn đề được biểu diễn dưới dạng các đối tượng và các kết nối giữa chúng. Ví dụ: trong bản đồ đường bộ Việt Nam, chúng ta có thể quan tâm đến các câu hỏi như: “Cách nhanh nhất để đi từ Cần Thơ đến TPHCM là gì?” hoặc “Tuyến đường ngắn nhất đi từ Cần Thơ đến TPHCM?” Để trả lời những câu hỏi này, chúng tôi cần thông tin về các kết nối (tuyến đường) giữa các đối tượng (thành phố). Đồ thị (graph) là cấu trúc dữ liệu được sử dụng để giải quyết các loại vấn đề này.

1. Định nghĩa đồ thị

Đồ thị là một cặp (V,E) trong đó V là tập hợp các nút hay còn gọi là các đỉnh (vertices) và E là tập hợp các cạnh (edges) nối giữa hai đỉnh với nhau.

Môt số định nghĩa trong đồ thị:

Cạnh có hướng (Directed edge): Đỉnh được sắp xếp theo thứ tự (u, v), trong đó đỉnh u là gốc và đỉnh v là đích. Ví dụ: giao thông đường một chiều

Cạnh vô hướng (Undirected edge): Đỉnh không được sắp xếp theo thứ tự (u, v). Ví dụ: tuyến đường sắt.

Đồ thị có hướng (Directed graph): Tât cả các cạnh đều là cạnh có hướng. Ví dụ: tuyến đường mạng.

Đồ thị vô hướng (Undirected graph): Tất cả các cạnh đều là cạnh vô hướng. Ví dụ: đường hàng không.

Bậc của một đỉnh là số cạnh của đỉnh đó.
Đường đi trong đồ thị là một dãy các đỉnh kề nhau mà không có đỉnh lặp lại.
Chu trình là đường đi có đỉnh đầu và đỉnh cuối trùng nhau, không có đỉnh hoặc cạnh lặp lại.
Đồ thị liên thông là đồ thị có đường đi từ mọi đỉnh đến mọi đỉnh khác.
Đồ thị tuần hoàn có hướng là đồ thị có hướng nhưng không có chu trình.
Đồ thị có trọng số là đồ thị mà trên mỗi cạnh được gán giá trị để biểu diễn khoảng cách hoặc chi phí.

2. Ứng dụng của đồ thị

Biểu diễn mối quan hệ giữa các linh kiện trong mạch điện tử.
Mạng máy tính: mạng cục bộ, internet, web.
Mạng lưới giao thông: đường bộ, đường hàng không.
Cơ sở dữ liệu: Để biểu diễn sơ đồ ER (mối quan hệ thực thể) trong cơ sở dữ liệu, để biểu thị sự phục thuộc của các bảng trong cơ sở dữ liệu.

3. Biểu diễn đồ thị

Sử dụng ma trận liền kề

Trong phương pháp này, chúng ta sử dụng một ma trận có kích thước V x V. Các giá trị của ma trận là boolean. Giả sử ma trận là A. Giá trị A[u, v] được đặt thành 1 nếu có một cạnh từ đỉnh u đến đỉnh v và 0 nếu ngược lại. Ma trận liền kề biểu thị cho đồ thị dưới dạng như sau:

Cài đặt ma trận liền kề:

class Graph {
    private boolean matrix[][];
    private int vertexCount;

    public Graph(int numVertex) {
        this.vertexCount = numVertex;
        matrix = new boolean[numVertex][numVertex];
    }

    public void addEdge(int u, int v) {
        if (u >= 0 && u < vertexCount && v >= 0 && v < vertexCount) {
            matrix[u][v] = true;
            matrix[v][u] = true;
        }
    }

    public void removeEdge(int u, int v) {
        if (u >= 0 && u < vertexCount && v >= 0 && v < vertexCount) {
            matrix[u][v] = false;
            matrix[v][u] = false;
        }
    }

    public boolean isEdge(int v, int u) {
        if (u >= 0 && u < vertexCount && v >= 0 && v < vertexCount) {
            return matrix[u][v];
        }
        return false;
    }
}

Sử dụng danh sách liền kề

Trong cách biểu diễn này, đối với mỗi đỉnh v chúng ta sử dụng một danh sách liên kết và các nút trong danh sách liên kết đại diện cạnh kết nối giữa đỉnh v và các đỉnh khác. Tổng số danh sách liên kết bằng số đỉnh của đồ thị.

Xem xét ví dụ tương tự như ví dụ ma trận liền kề ở trên, biểu diễn danh sách liền kề có thể được đưa ra như hình trên. Vì đỉnh A có cạnh của B và D nên chúng ta đã thêm chúng vào danh sách liền kề của A. Tương tự với cách đỉnh khác.

import java.util.ArrayList;

class Graph {
    static void addEdge(ArrayList<ArrayList<Integer>> adj, int s, int d) {
        adj.get(s).add(d);
        adj.get(d).add(s);
    }

    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer>>(V);
        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<Integer>());
        // Add edges
        addEdge(adj, 0, 1);
        addEdge(adj, 0, 2);
        addEdge(adj, 0, 3);
        addEdge(adj, 1, 2);

        printGraph(adj);
    }

    static void printGraph(ArrayList<ArrayList<Integer>> adj) {
        for (int i = 0; i < adj.size(); i++) {
            System.out.println("\nVertex " + i + ":");
            for (int j = 0; j < adj.get(i).size(); j++) {
                System.out.print(" -> " + adj.get(i).get(j));
            }
            System.out.println();
        }
    }
}