基于邻接表从文本文件构建无向图：代码实现与优化咨询

问题背景 #

需要从以下格式的文本文件构建无向图：

0 5
4 3
0 1
9 12
6 4
5 4
0 2
11 12

现有代码存在逻辑错误，无法正确构建无向图，以下是修复方案与实现说明。

现有代码的核心问题 #

• Node类构造函数未正确初始化顶点值，默认构造函数的this.vertex = vertex;完全无效
• file_to_array仅将每个整数单独创建为节点，未处理边的关联关系，完全没体现图的结构
• Graph类的vertices被定义为static，会导致多个Graph实例共享同一顶点集合，不符合面向对象设计
• Node类的邻居链表直接暴露，存在被意外修改的风险，缺乏封装性

修复后的完整实现 #

1. 完善Node类 #

public class Node {
    private final int vertex;
    private final LinkedList<Node> neighbors;

    // 带参数的构造函数，正确初始化顶点值
    public Node(int vertex) {
        this.vertex = vertex;
        this.neighbors = new LinkedList<>();
    }

    // 给当前节点添加邻居（无向图需双向添加）
    public void addNeighbor(Node neighbor) {
        // 避免重复添加同一邻居
        if (!neighbors.contains(neighbor)) {
            neighbors.add(neighbor);
        }
    }

    // 获取顶点值
    public int getVertex() {
        return vertex;
    }

    // 获取邻居列表（返回副本避免外部修改内部结构）
    public List<Node> getNeighbors() {
        return new LinkedList<>(neighbors);
    }
}

2. 重构Graph类 #

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;

public class Graph {
    private String filename;
    private final ArrayList<Node> vertices;

    public Graph() {
        this.vertices = new ArrayList<>();
    }

    public Graph(String filename) {
        this.filename = filename;
        this.vertices = new ArrayList<>();
        buildGraphFromFile();
    }

    public String getFilename() {
        return filename;
    }

    public void setFilename(String filename) {
        this.filename = filename;
    }

    // 根据顶点值查找已存在的节点，不存在则创建并加入顶点集合
    private Node getOrCreateNode(int vertexValue) {
        for (Node node : vertices) {
            if (node.getVertex() == vertexValue) {
                return node;
            }
        }
        Node newNode = new Node(vertexValue);
        vertices.add(newNode);
        return newNode;
    }

    // 从文件构建无向图的核心方法
    public void buildGraphFromFile() {
        if (filename == null || filename.isEmpty()) {
            System.err.println("文件名未设置");
            return;
        }
        File file = new File(filename);
        // 使用try-with-resources自动关闭Scanner，避免资源泄漏
        try (Scanner scan = new Scanner(file)) {
            // 每次读取两个整数，代表一条无向边的两个顶点
            while (scan.hasNextInt()) {
                int u = scan.nextInt();
                int v = scan.nextInt();
                // 获取或创建两个顶点对应的Node实例
                Node nodeU = getOrCreateNode(u);
                Node nodeV = getOrCreateNode(v);
                // 无向图特性：互相添加为邻居
                nodeU.addNeighbor(nodeV);
                nodeV.addNeighbor(nodeU);
            }
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }
    }

    // 打印图的结构，用于验证构建结果
    public void printGraph() {
        for (Node node : vertices) {
            System.out.print("顶点 " + node.getVertex() + " 的邻居：");
            for (Node neighbor : node.getNeighbors()) {
                System.out.print(neighbor.getVertex() + " ");
            }
            System.out.println();
        }
    }

    // 测试示例
    public static void main(String[] args) {
        Graph graph = new Graph("graph.txt"); // 替换为你的文件路径
        graph.printGraph();
    }
}

关键实现说明 #

• getOrCreateNode方法：确保每个顶点值对应唯一的Node实例，避免重复创建节点
• 无向边处理：读取每条边的两个顶点后，互相添加为邻居，符合无向图的双向关联特性
• 封装性：Node类的内部字段全部私有化，仅提供必要的访问方法，保证数据安全
• 资源管理：使用try-with-resources语法自动关闭IO资源，避免内存泄漏

内容的提问来源于stack exchange，提问作者RadaRada