假设有两个List:
一个存放了五个User对象,含有id,名称之类的属性;
另一个存放了四个连线关系,fromId 和 toId,这两个值取的都是user的id
A-->B-->C-->D-->E
如何能给这五个对象排序出来!!
可以使用拓扑排序
import java.util.*;
// User class
class User {
int id;
String name;
public User(int id, String name) {
this.id = id;
this.name = name;
}
}
// Edge class
class Edge {
int fromId;
int toId;
public Edge(int fromId, int toId) {
this.fromId = fromId;
this.toId = toId;
}
}
public class Main {
public static void main(String[] args) {
List<User> users = Arrays.asList(
new User(1, "A"),
new User(2, "B"),
new User(3, "C"),
new User(4, "D"),
new User(5, "E")
);
List<Edge> edges = Arrays.asList(
new Edge(1, 2),
new Edge(2, 3),
new Edge(3, 4),
new Edge(4, 5)
);
List<User> sortedUsers = topologicalSort(users, edges);
System.out.println(sortedUsers);
}
public static List<User> topologicalSort(List<User> users, List<Edge> edges) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (Edge edge : edges) {
graph.computeIfAbsent(edge.fromId, x -> new ArrayList<>()).add(edge.toId);
}
List<User> sortedUsers = new ArrayList<>();
Set<Integer> visited = new HashSet<>();
for (User user : users) {
topologicalSortUtil(graph, user.id, visited, sortedUsers);
}
return sortedUsers;
}
private static void topologicalSortUtil(Map<Integer, List<Integer>> graph, int v, Set<Integer> visited, List<User> sortedUsers) {
if (visited.contains(v)) {
return;
}
visited.add(v);