Java泛型自引用的正确用法：节点与边接口的定义及实现

一、核心问题分析 #

你遇到的本质是泛型循环依赖的正确声明问题：Node需要知道对应的Edge类型，Edge也需要知道对应的Node类型，同时要保证类型安全，避免通配符带来的信息丢失。

二、正确的接口声明 #

采用双向泛型绑定，让Node和Edge的泛型参数同时包含自身和对方的具体类型，确保编译时类型校验：

import java.util.List;

// Node接口：N是自身节点类型，E是关联的边类型
public interface Node<N extends Node<N, E>, E extends Edge<N, E>> {
    List<E> getOutgoingEdges();
    List<E> getIncomingEdges();
}

// Edge接口：N是关联的节点类型，E是自身边类型
public interface Edge<N extends Node<N, E>, E extends Edge<N, E>> {
    N getSource();
    N getTarget();
    double getWeight(); // A*搜索需要边权重（距离）
}

三、具体实现类示例 #

以2D坐标节点为例，其他类型（GPS、3D）可参照此结构实现：

1. 2D节点实现 #

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Node2D implements Node<Node2D, Edge2D> {
    private final double x;
    private final double y;
    private final List<Edge2D> outgoingEdges = new ArrayList<>();
    private final List<Edge2D> incomingEdges = new ArrayList<>();

    public Node2D(double x, double y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public List<Edge2D> getOutgoingEdges() {
        return Collections.unmodifiableList(outgoingEdges);
    }

    @Override
    public List<Edge2D> getIncomingEdges() {
        return Collections.unmodifiableList(incomingEdges);
    }

    // 内部维护边的关联（避免外部随意修改）
    void addOutgoingEdge(Edge2D edge) {
        outgoingEdges.add(edge);
    }

    void addIncomingEdge(Edge2D edge) {
        incomingEdges.add(edge);
    }

    // 2D节点专属距离计算方法
    public double distanceTo(Node2D other) {
        double dx = this.x - other.x;
        double dy = this.y - other.y;
        return Math.sqrt(dx * dx + dy * dy);
    }

    // Getter方法
    public double getX() { return x; }
    public double getY() { return y; }
}

2. 对应2D节点的边实现 #

public class Edge2D implements Edge<Node2D, Edge2D> {
    private final Node2D source;
    private final Node2D target;
    private final double weight;

    public Edge2D(Node2D source, Node2D target) {
        this.source = source;
        this.target = target;
        this.weight = source.distanceTo(target); // 自动计算距离作为权重
        // 自动关联节点与边
        source.addOutgoingEdge(this);
        target.addIncomingEdge(this);
    }

    @Override
    public Node2D getSource() {
        return source;
    }

    @Override
    public Node2D getTarget() {
        return target;
    }

    @Override
    public double getWeight() {
        return weight;
    }
}

四、实例化与使用 #

完全类型安全，无警告/错误：

// 创建2D节点
Node2D nodeA = new Node2D(0, 0);
Node2D nodeB = new Node2D(3, 4);
Node2D nodeC = new Node2D(1, 1);

// 创建边（自动关联到节点）
Edge2D edgeAB = new Edge2D(nodeA, nodeB);
Edge2D edgeAC = new Edge2D(nodeA, nodeC);
Edge2D edgeCB = new Edge2D(nodeC, nodeB);

// 通用类型声明（可选）
Node<Node2D, Edge2D> genericNode = nodeA;
Edge<Node2D, Edge2D> genericEdge = edgeAB;

五、通用A*搜索实现 #

基于上述泛型接口，实现支持任意节点/边类型的A*算法，通过函数式接口适配不同节点的启发函数：

1. 启发函数接口 #

@FunctionalInterface
public interface HeuristicFunction<N extends Node<N, E>, E extends Edge<N, E>> {
    double estimate(N current, N goal);
}

2. A*搜索实现 #

import java.util.*;

public class AStarSearch<N extends Node<N, E>, E extends Edge<N, E>> {
    public List<N> findPath(N start, N goal, HeuristicFunction<N, E> heuristic) {
        // 优先级队列：按f值（g+h）排序
        PriorityQueue<NodeEntry> openSet = new PriorityQueue<>(Comparator.comparingDouble(entry -> entry.fScore));
        Map<N, Double> gScores = new HashMap<>();
        Map<N, N> cameFrom = new HashMap<>();

        gScores.put(start, 0.0);
        openSet.add(new NodeEntry(start, 0.0 + heuristic.estimate(start, goal)));

        while (!openSet.isEmpty()) {
            NodeEntry currentEntry = openSet.poll();
            N current = currentEntry.node;

            if (current.equals(goal)) {
                return reconstructPath(cameFrom, current);
            }

            for (E edge : current.getOutgoingEdges()) {
                N neighbor = edge.getTarget();
                double tentativeGScore = gScores.get(current) + edge.getWeight();

                if (tentativeGScore < gScores.getOrDefault(neighbor, Double.POSITIVE_INFINITY)) {
                    cameFrom.put(neighbor, current);
                    gScores.put(neighbor, tentativeGScore);
                    double fScore = tentativeGScore + heuristic.estimate(neighbor, goal);
                    openSet.add(new NodeEntry(neighbor, fScore));
                }
            }
        }

        return Collections.emptyList(); // 无路径返回空列表
    }

    // 重构路径
    private List<N> reconstructPath(Map<N, N> cameFrom, N current) {
        List<N> path = new ArrayList<>();
        path.add(current);
        while (cameFrom.containsKey(current)) {
            current = cameFrom.get(current);
            path.add(current);
        }
        Collections.reverse(path);
        return path;
    }

    // 内部类存储节点与f分数
    private static class NodeEntry<N extends Node<N, ?>> {
        final N node;
        final double fScore;

        NodeEntry(N node, double fScore) {
            this.node = node;
            this.fScore = fScore;
        }
    }
}

3. 使用A*搜索示例 #

// 2D节点的启发函数（欧几里得距离）
HeuristicFunction<Node2D, Edge2D> euclideanHeuristic = Node2D::distanceTo;

AStarSearch<Node2D, Edge2D> aStar = new AStarSearch<>();
List<Node2D> path = aStar.findPath(nodeA, nodeB, euclideanHeuristic);

// 输出路径
for (Node2D node : path) {
    System.out.printf("(%.2f, %.2f)%n", node.getX(), node.getY());
}

六、方案优势 #

1. 类型安全：编译时确保图中仅包含兼容的节点和边类型，避免运行时类型转换错误。
2. 扩展性：新增节点类型（如GPSNode、Node3D）只需实现对应接口，A*算法无需修改。
3. 灵活性：启发函数通过函数式接口传入，适配不同节点的距离估计逻辑。

内容的提问来源于stack exchange，提问作者thomas.schuerger