그림 의 기본 구조

개념:
(1) 그림 은 정점 집합 과 정점 간 의 관계 집합 으로 구 성 된 데이터 구조 이다.
Graph = (V, E) V 는 정점 의 빈 공간 집합 이다.E 는 정점 간 의 관계 가 있 는 가난 한 집합 이 고 변 집합 이 라 고도 부른다.
(2) 방향 그림 이 있 습 니 다. 정점 은 질서 가 있 습 니 다.무방 향도: 정점 은 무질서 하 다.
(3) 무 방향 변: 정점 Vi 에서 Vj 사이 의 변 에 방향 이 없 으 면 이 변 을 무 방향 변 이 라 고 부 르 고 무질서 한 짝 짓 기 (Vi, Vj) 로 표시 한다.
(4) 전혀 방향 이 없 는 그림: n 개의 정점 이 없 는 그림 에 n (n - 1) / 2 개의 변 이 있 으 면 이 그림 은 전혀 방향 이 없 는 그림 이다.
완전히 방향 도: n 개의 정점 이 있 는 방향 도 는 n (n - 1) 개의 변 이 있 고 이 그림 은 완전히 방향 도 이다.
(5) 나무의 뿌리 노드 에서 임의의 노드 까지 의 경 로 는 유일한 것 이지 만 그림 의 정점 과 정점 사이 의 경 로 는 유일한 것 이 아니다.
경로 의 길 이 는 경로 의 변 이나 호의 수 입 니 다.
(6) 그림 의 두 정점 이 모두 연결 되 어 있다 면 G 는 연결 그림 이다.
(7) 그림 은 변 이나 호의 다소 에 따라 희소 도와 조밀도 로 나 뉜 다.만약 임의의 두 정점 사이 에 완전한 그림 이 존재 한다 면, 방향 이 있 는 것 을 방향 이 있 는 그림 이 라 고 부른다.
반복 되 는 변 이나 정점 이 없 으 면 간단 한 그림 이 라 고 합 니 다.
(8) 그림 의 정점 사이 에 인접 점 이 있다.그림 의 정점 이 없 는 변 수 를 도 라 고 한다.그림 의 정점 은 입도 와 출 도로 나 뉜 다.
(9) 그림 의 변 과 호상 대 권 은 그물 이 라 고 부른다.
(10) 방향 이 있 는 연통 도 를 강 연통 도 라 고 한다.
구조 구현 코드:
점:

public class Node {
        //   
    public int value;
        //  
    public int in;
        //  
    public int out;
        //            
    public ArrayList nexts;
        //          
    public ArrayList edges;

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}

변:

public class Edge {
        //  
    public int weight;
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }

그림:

public class Graph {
        //    ，Integer   
    public HashMap nodes;
    public HashSet edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

그림 만 들 기:
생각:
그림 을 만 들 면 제목 은 보통 2 차원 배열 을 줄 것 이다. 예 를 들 어 다음 과 같다. 첫 번 째 요 소 는 from, 두 번 째 는 to, 세 번 째 요 소 는 가중치 를 나타 낸다.
[1，2，50] [2，3，100] [4，3，40]
이 2 차원 배열 을 지정 하면 그림 순환 배열 의 1 차원 을 만 들 수 있 습 니 다. 그림 에 from to 등 이 없 으 면 가입 한 다음 에 사 이 드, 입 도 출 도 등 정 보 를 넣 으 면 그림 을 만 들 수 있 습 니 다.
코드:

public static Graph createGraph(Integer[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            Integer from = matrix[i][0];
            Integer to = matrix[i][1];
            Integer weight = matrix[i][2];
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to); 
            Edge newEdge = new Edge(weight, fromNode, toNode);
            fromNode.nexts.add(toNode);
            fromNode.out++;
            toNode.in++;
            fromNode.edges.add(newEdge);
            graph.edges.add(newEdge);
        }
        return graph;
    }