Chương trình Java triển khai cấu trúc dữ liệu Graph (Đồ thị)

Trong bài viết này, chúng ta sẽ hiểu cách triển khai cấu trúc dữ liệu Graph (Đồ thị). Chúng ta triển khai đồ thị trong Java sử dụng collection HashMap. Các phần tử HashMap ở dạng cặp key-value. Chúng ta có thể biểu diễn danh sách kề (adjacency list) của đồ thị trong HashMap.

Minh họa dưới đây:

Giả sử đầu vào là:

Number of Vertices: 5 Number of edges: 5

Đầu ra mong muốn:

The connections between the nodes of the Graph are: 1 - 2 1 - 3 1 - 4 2 - 4 2 - 5 3 - 4 3 - 5 4 - 5

Thuật toán

Bước 1 - BẮT ĐẦU 
Bước 2 - Khai báo object Graph graph_object, hai int trong class 'Edge' là source và destination, hai int trong 'main' là vertices_count, edges_count 
Bước 3 - Định nghĩa giá trị 
Bước 4 - Khởi tạo giá trị cho vertices và edges 
Bước 5 - Tạo instance mới của class đã định nghĩa 
Bước 6 - Khởi tạo instance với giá trị liên quan 
Bước 7 - Duyệt instance bằng 'for' loop, hiển thị output 
Bước 8 - Hiển thị kết quả 
Bước 9 - DỪNG

Ví dụ 1

Gom thao tác dưới 'main'.

public class Graph { 
    class Edge { 
        int source, destination; 
    } 
    int vertices, edges; 
    Edge[] edge; 
    
    Graph(int vertices, int edges) { 
        this.vertices = vertices; 
        this.edges = edges; 
        edge = new Edge[edges]; 
        for(int i = 0; i < edges; i++) { 
            edge[i] = new Edge(); 
        } 
    } 
    
    public static void main(String[] args) { 
        int vertices_count = 5; 
        int edges_count = 8; 
        Graph graph_object = new Graph(vertices_count, edges_count); 
        System.out.println("A graph object is defined."); 
        graph_object.edge[0].source = 1; 
        graph_object.edge[0].destination = 2; 
        graph_object.edge[1].source = 1; 
        graph_object.edge[1].destination = 3; 
        graph_object.edge[2].source = 1; 
        graph_object.edge[2].destination = 4; 
        graph_object.edge[3].source = 2; 
        graph_object.edge[3].destination = 4; 
        graph_object.edge[4].source = 2; 
        graph_object.edge[4].destination = 5; 
        graph_object.edge[5].source = 3; 
        graph_object.edge[5].destination = 4; 
        graph_object.edge[6].source = 3; 
        graph_object.edge[6].destination = 5; 
        graph_object.edge[7].source = 4; 
        graph_object.edge[7].destination = 5; 
        System.out.println("The connections between the edges of the Graph are: "); 
        for(int i = 0; i < edges_count; i++) { 
            System.out.println(graph_object.edge[i].source + " - " + graph_object.edge[i].destination); 
        } 
    } 
}

Kết quả

A graph object is defined. 
The connections between the edges of the Graph are: 
1 - 2 
1 - 3 
1 - 4 
2 - 4 
2 - 5 
3 - 4 
3 - 5 
4 - 5

Ví dụ 2

Đóng gói thao tác vào hàm thể hiện lập trình hướng đối tượng.

public class Graph { 
    class Edge { 
        int source, destination; 
    } 
    int vertices, edges; 
    Edge[] edge; 
    
    Graph(int vertices, int edges) { 
        this.vertices = vertices; 
        this.edges = edges; 
        edge = new Edge[edges]; 
        for(int i = 0; i < edges; i++) { 
            edge[i] = new Edge(); 
        } 
    } 
    
    static void print(Graph graph_object, int edges_count){ 
        System.out.println("The connections between the edges of the Graph are: "); 
        for(int i = 0; i < edges_count; i++) { 
            System.out.println(graph_object.edge[i].source + " - " + graph_object.edge[i].destination); 
        } 
    } 
    
    static void connect_edges(Graph graph_object){ 
        graph_object.edge[0].source = 1; 
        graph_object.edge[0].destination = 2; 
        graph_object.edge[1].source = 1; 
        graph_object.edge[1].destination = 3; 
        graph_object.edge[2].source = 1; 
        graph_object.edge[2].destination = 4; 
        graph_object.edge[3].source = 2; 
        graph_object.edge[3].destination = 4; 
        graph_object.edge[4].source = 2; 
        graph_object.edge[4].destination = 5; 
        graph_object.edge[5].source = 3; 
        graph_object.edge[5].destination = 4; 
        graph_object.edge[6].source = 3; 
        graph_object.edge[6].destination = 5; 
        graph_object.edge[7].source = 4; 
        graph_object.edge[7].destination = 5; 
    } 
    
    public static void main(String[] args) { 
        int vertices_count = 5; 
        int edges_count = 8; 
        Graph graph_object = new Graph(vertices_count, edges_count); 
        System.out.println("A graph object is defined."); 
        connect_edges(graph_object); 
        print(graph_object, edges_count); 
    } 
}

Kết quả

A graph object is defined. 
The connections between the edges of the Graph are: 
1 - 2 
1 - 3 
1 - 4 
2 - 4 
2 - 5 
3 - 4 
3 - 5 
4 - 5