Java Program Implement Graph Data Structure (Adjacency List)

Graph Data Structure คืออะไร?

Graph ประกอบด้วย Vertices (Nodes) และ Edges (Connections) ใช้แทนความสัมพันธ์ระหว่างวัตถุ

ประเภท Graph

• Directed (Digraph) - Edge มีทิศทาง (A → B)
• Undirected - Edge ไม่มีทิศทาง (A ↔ B)
• Weighted - Edge มีน้ำหนัก/ค่าใช้จ่าย
• Unweighted - Edge ไม่มีน้ำหนัก

Graph Representations

Implementation: Adjacency List ด้วย HashMap

ใช้ HashMap<Vertex, List<Vertex>> - ยืดหยุ่น รองรับ Vertex ใดๆ

Edge Class

class Edge {
    int source;
    int destination;
    
    Edge(int source, int destination) {
        this.source = source;
        this.destination = destination;
    }
}

Graph Class (Edge List Representation)

public class Graph {
    int vertices;
    int edges;
    Edge[] edgeArray;
    
    Graph(int vertices, int edges) {
        this.vertices = vertices;
        this.edges = edges;
        this.edgeArray = new Edge[edges];
        for (int i = 0; i < edges; i++) {
            edgeArray[i] = new Edge(0, 0);
        }
    }
}

ตัวอย่างที่ 1: Edge List (จาก Source)

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 verticesCount = 5;
        int edgesCount = 8;
        Graph graph = new Graph(verticesCount, edgesCount);
        
        System.out.println("A graph object is defined.");
        
        // กำหนด Edges
        graph.edge[0] = new Edge(); graph.edge[0].source = 1; graph.edge[0].destination = 2;
        graph.edge[1] = new Edge(); graph.edge[1].source = 1; graph.edge[1].destination = 3;
        graph.edge[2] = new Edge(); graph.edge[2].source = 1; graph.edge[2].destination = 4;
        graph.edge[3] = new Edge(); graph.edge[3].source = 2; graph.edge[3].destination = 4;
        graph.edge[4] = new Edge(); graph.edge[4].source = 2; graph.edge[4].destination = 5;
        graph.edge[5] = new Edge(); graph.edge[5].source = 3; graph.edge[5].destination = 4;
        graph.edge[6] = new Edge(); graph.edge[6].source = 3; graph.edge[6].destination = 5;
        graph.edge[7] = new Edge(); graph.edge[7].source = 4; graph.edge[7].destination = 5;
        
        System.out.println("The connections between the edges of the Graph are: ");
        for (int i = 0; i < edgesCount; i++) {
            System.out.println(graph.edge[i].source + " - " + graph.edge[i].destination);
        }
    }
}

ผลลัพธ์

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

ตัวอย่างที่ 2: OOP Style (แยกเมธอด)

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 connectEdges(Graph g) {
        g.edge[0] = new Edge(); g.edge[0].source = 1; g.edge[0].destination = 2;
        g.edge[1] = new Edge(); g.edge[1].source = 1; g.edge[1].destination = 3;
        g.edge[2] = new Edge(); g.edge[2].source = 1; g.edge[2].destination = 4;
        g.edge[3] = new Edge(); g.edge[3].source = 2; g.edge[3].destination = 4;
        g.edge[4] = new Edge(); g.edge[4].source = 2; g.edge[4].destination = 5;
        g.edge[5] = new Edge(); g.edge[5].source = 3; g.edge[5].destination = 4;
        g.edge[6] = new Edge(); g.edge[6].source = 3; g.edge[6].destination = 5;
        g.edge[7] = new Edge(); g.edge[7].source = 4; g.edge[7].destination = 5;
    }
    
    static void print(Graph g, int edgesCount) {
        System.out.println("The connections between the edges of the Graph are: ");
        for (int i = 0; i < edgesCount; i++) {
            System.out.println(g.edge[i].source + " - " + g.edge[i].destination);
        }
    }
    
    public static void main(String[] args) {
        int v = 5, e = 8;
        Graph graph = new Graph(v, e);
        System.out.println("A graph object is defined.");
        connectEdges(graph);
        print(graph, e);
    }
}

Adjacency List Implementation (Modern, Recommended)

import java.util.*;

public class GraphAdjList {
    // Adjacency List: Vertex -> List of Neighbors
    private Map> adjList = new HashMap<>();
    private boolean directed;
    
    public GraphAdjList(boolean directed) {
        this.directed = directed;
    }
    
    public void addVertex(int v) {
        adjList.putIfAbsent(v, new ArrayList<>());
    }
    
    public void addEdge(int src, int dest) {
        addVertex(src);
        addVertex(dest);
        adjList.get(src).add(dest);
        if (!directed) {
            adjList.get(dest).add(src);
        }
    }
    
    public void printGraph() {
        for (Map.Entry> entry : adjList.entrySet()) {
            System.out.print(entry.getKey() + " -> ");
            System.out.println(entry.getValue());
        }
    }
    
    // BFS Traversal
    public void bfs(int start) {
        Set visited = new HashSet<>();
        Queue queue = new LinkedList<>();
        visited.add(start);
        queue.offer(start);
        
        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");
            for (int neighbor : adjList.getOrDefault(v, Collections.emptyList())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.offer(neighbor);
                }
            }
        }
    }
    
    // DFS Traversal
    public void dfs(int start) {
        Set visited = new HashSet<>();
        dfsRecursive(start, visited);
    }
    
    private void dfsRecursive(int v, Set visited) {
        visited.add(v);
        System.out.print(v + " ");
        for (int neighbor : adjList.getOrDefault(v, Collections.emptyList())) {
            if (!visited.contains(neighbor)) {
                dfsRecursive(neighbor, visited);
            }
        }
    }
    
    public static void main(String[] args) {
        GraphAdjList graph = new GraphAdjList(false); // Undirected
        graph.addEdge(1, 2);
        graph.addEdge(1, 3);
        graph.addEdge(2, 4);
        graph.addEdge(3, 4);
        graph.addEdge(4, 5);
        
        graph.printGraph();
        // 1 -> [2, 3]
        // 2 -> [1, 4]
        // 3 -> [1, 4]
        // 4 -> [2, 3, 5]
        // 5 -> [4]
        
        System.out.print("\nBFS: "); graph.bfs(1); // 1 2 3 4 5
        System.out.print("\nDFS: "); graph.dfs(1); // 1 2 4 5 3
    }
}

Weighted Graph (มีน้ำหนัก)

class WeightedEdge {
    int dest;
    double weight;
    WeightedEdge(int dest, double weight) {
        this.dest = dest; this.weight = weight;
    }
}

// Adjacency List สำหรับ Weighted Graph
Map> weightedGraph = new HashMap<>();
weightedGraph.computeIfAbsent(1, k -> new ArrayList<>()).add(new WeightedEdge(2, 10.5));
weightedGraph.computeIfAbsent(2, k -> new ArrayList<>()).add(new WeightedEdge(3, 5.0));

สรุป

• Graph = Vertices + Edges (Directed/Undirected, Weighted/Unweighted)
• Representations: Adjacency Matrix (Dense), Adjacency List (Sparse - แนะนำ), Edge List
• Java: ใช้ HashMap<V, List<V>> สำหรับ Adjacency List
• Traversals: BFS (Queue), DFS (Stack/Recursion)
• Algorithms: Dijkstra (Shortest Path), Topological Sort, MST (Kruskal/Prim)