Как описать отношение в графах

Как описать отношение в графах

Отношения в графах описываются при помощи рёбер (edges), которые соединяют вершины (nodes/vertices). Вот основные способы описания этих отношений.

Основные компоненты графа

Вершина (Vertex/Node) - объект или сущность Ребро (Edge) - связь или отношение между вершинами Вес (Weight) - стоимость или значение отношения

1. Представление графа через класс Node

public class Node<T> {
    private T value;
    private List<Node<T>> neighbors;
    
    public Node(T value) {
        this.value = value;
        this.neighbors = new ArrayList<>();
    }
    
    public void addNeighbor(Node<T> neighbor) {
        neighbors.add(neighbor);
    }
    
    public List<Node<T>> getNeighbors() {
        return neighbors;
    }
    
    public T getValue() {
        return value;
    }
}

2. Граф с использованием матрицы смежности

public class GraphMatrix {
    private int[][] adjacencyMatrix;
    private int vertexCount;
    
    public GraphMatrix(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjacencyMatrix = new int[vertexCount][vertexCount];
    }
    
    // Добавить ребро между вершинами
    public void addEdge(int from, int to) {
        adjacencyMatrix[from][to] = 1;  // Ориентированный граф
        adjacencyMatrix[to][from] = 1;  // Неориентированный граф
    }
    
    // Добавить ребро с весом
    public void addWeightedEdge(int from, int to, int weight) {
        adjacencyMatrix[from][to] = weight;
    }
    
    // Проверить наличие ребра
    public boolean hasEdge(int from, int to) {
        return adjacencyMatrix[from][to] != 0;
    }
    
    // Получить соседей вершины
    public List<Integer> getNeighbors(int vertex) {
        List<Integer> neighbors = new ArrayList<>();
        for (int i = 0; i < vertexCount; i++) {
            if (adjacencyMatrix[vertex][i] != 0) {
                neighbors.add(i);
            }
        }
        return neighbors;
    }
}

3. Граф с использованием списка смежности

public class GraphList<T> {
    private Map<T, List<T>> adjacencyList;
    
    public GraphList() {
        this.adjacencyList = new HashMap<>();
    }
    
    // Добавить вершину
    public void addVertex(T vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }
    
    // Добавить ребро
    public void addEdge(T from, T to) {
        adjacencyList.putIfAbsent(from, new ArrayList<>());
        adjacencyList.putIfAbsent(to, new ArrayList<>());
        adjacencyList.get(from).add(to);
    }
    
    // Добавить неориентированное ребро
    public void addUndirectedEdge(T from, T to) {
        addEdge(from, to);
        addEdge(to, from);
    }
    
    // Получить соседей вершины
    public List<T> getNeighbors(T vertex) {
        return adjacencyList.getOrDefault(vertex, new ArrayList<>());
    }
    
    // Получить все вершины
    public Set<T> getVertices() {
        return adjacencyList.keySet();
    }
}

4. Граф с взвешенными рёбрами

public class Edge<T> {
    private T from;
    private T to;
    private int weight;
    
    public Edge(T from, T to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }
    
    public T getFrom() { return from; }
    public T getTo() { return to; }
    public int getWeight() { return weight; }
}

public class WeightedGraph<T> {
    private Map<T, List<Edge<T>>> adjacencyList;
    
    public WeightedGraph() {
        this.adjacencyList = new HashMap<>();
    }
    
    public void addVertex(T vertex) {
        adjacencyList.putIfAbsent(vertex, new ArrayList<>());
    }
    
    public void addEdge(T from, T to, int weight) {
        adjacencyList.putIfAbsent(from, new ArrayList<>());
        adjacencyList.putIfAbsent(to, new ArrayList<>());
        adjacencyList.get(from).add(new Edge<>(from, to, weight));
    }
    
    public List<Edge<T>> getEdges(T vertex) {
        return adjacencyList.getOrDefault(vertex, new ArrayList<>());
    }
}

5. Граф через отношение Entity-Relationship

public class Person {
    private String id;
    private String name;
    private List<Person> friends;  // Отношение "знает"
    private List<Person> follows;  // Отношение "подписан на"
    
    public Person(String id, String name) {
        this.id = id;
        this.name = name;
        this.friends = new ArrayList<>();
        this.follows = new ArrayList<>();
    }
    
    public void addFriend(Person person) {
        friends.add(person);
    }
    
    public void follow(Person person) {
        follows.add(person);
    }
    
    public List<Person> getFriends() { return friends; }
    public List<Person> getFollowing() { return follows; }
}

6. Обход графа - DFS (Depth-First Search)

public class GraphTraversal<T> {
    public void dfs(T start, Set<T> visited, Map<T, List<T>> graph) {
        if (visited.contains(start)) return;
        
        visited.add(start);
        System.out.println(start);
        
        for (T neighbor : graph.getOrDefault(start, new ArrayList<>())) {
            dfs(neighbor, visited, graph);
        }
    }
    
    public void dfsFull(Map<T, List<T>> graph) {
        Set<T> visited = new HashSet<>();
        for (T vertex : graph.keySet()) {
            if (!visited.contains(vertex)) {
                dfs(vertex, visited, graph);
            }
        }
    }
}

7. Обход графа - BFS (Breadth-First Search)

public class BfsTraversal<T> {
    public void bfs(T start, Map<T, List<T>> graph) {
        Set<T> visited = new HashSet<>();
        Queue<T> queue = new LinkedList<>();
        
        queue.add(start);
        visited.add(start);
        
        while (!queue.isEmpty()) {
            T vertex = queue.poll();
            System.out.println(vertex);
            
            for (T neighbor : graph.getOrDefault(vertex, new ArrayList<>())) {
                if (!visited.contains(neighbor)) {
                    queue.add(neighbor);
                    visited.add(neighbor);
                }
            }
        }
    }
}

8. Типы отношений в графах

public enum RelationType {
    PARENT_CHILD,      // Иерархия
    FRIEND,            // Социальная сеть
    DEPENDENCY,        // Зависимость в проекте
    KNOWS,             // Знакомство
    WORKS_WITH,        // Сотрудничество
    DEPENDS_ON,        // Прямая зависимость
    CONTAINS           // Содержание
}

public class Relationship<T> {
    private T from;
    private T to;
    private RelationType type;
    private int strength;  // Сила отношения 0-100
    
    public Relationship(T from, T to, RelationType type, int strength) {
        this.from = from;
        this.to = to;
        this.type = type;
        this.strength = strength;
    }
}

9. Пример использования

public class Main {
    public static void main(String[] args) {
        GraphList<String> graph = new GraphList<>();
        
        // Добавляем вершины и рёбра
        graph.addUndirectedEdge("Alice", "Bob");
        graph.addUndirectedEdge("Alice", "Charlie");
        graph.addUndirectedEdge("Bob", "Diana");
        graph.addUndirectedEdge("Charlie", "Diana");
        
        // Получаем соседей
        System.out.println("Alice's friends: " + graph.getNeighbors("Alice"));
        
        // BFS обход
        BfsTraversal<String> bfs = new BfsTraversal<>();
        System.out.println("BFS from Alice:");
        bfs.bfs("Alice", graph.adjacencyList);
    }
}

Рекомендации

Для малых графов используйте матрицу смежности (быстрые проверки наличия ребер). Для больших разреженных графов используйте список смежности (экономия памяти). Для взвешенных графов используйте класс Edge. Для сложных отношений создавайте специализированные классы Relationship. При работе с отношениями в БД используйте оптимистичные блокировки и правильные индексы.