그림 의 기본 구조
(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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.