데이터 구조 트리와 그래프의 차이점은 무엇입니까?

데이터 구조 트리와 그래프의 차이점은 무엇입니까?

---

학문적으로, 데이터 구조 트리와 그래프의 근본적인 차이점은 무엇입니까? 트리 기반 검색과 그래프 기반 검색은 어떻습니까?

---

트리는 단지 제한된 형태의 그래프입니다.

나무는 방향 (부모 / 자식 관계)을 가지며주기를 포함하지 않습니다. 방향성 비순환 그래프 (또는 DAG) 범주에 적합합니다. 따라서 트리는 하위가 하나의 부모 만 가질 수있는 제한이있는 DAG입니다.

중요한 것은 Trees는 재귀 데이터 구조가 아닙니다. 위의 제한 때문에 재귀 데이터 구조로 구현할 수 없습니다. 그러나 일반적으로 재귀 적이 지 않은 DAG 구현도 사용할 수 있습니다. 내가 선호하는 트리 구현은 중앙 집중식 맵 표현이며 비재 귀적입니다.

그래프는 일반적으로 검색 호흡 우선 또는 깊이 우선입니다. Tree도 마찬가지입니다.

---

설명하는 대신 그림으로 표시하는 것을 선호합니다.

실시간으로 나무

실제 사용 그래프

예,지도는 그래프 데이터 구조로 시각화 될 수 있습니다.

이런 모습을 보면 인생이 더 쉬워집니다. 트리는 각 노드에 부모가 하나만 있다는 것을 알고있는 장소에서 사용됩니다. 그러나 그래프에는 여러 개의 선행 작업이있을 수 있습니다 (일반적으로 부모라는 용어는 그래프에 사용되지 않음).

실제로는 그래프를 사용하여 거의 모든 것을 나타낼 수 있습니다. 예를 들어지도를 사용했습니다. 각 도시를 노드로 간주하면 여러 지점에서 도달 할 수 있습니다. 이 노드로 이어지는 포인트를 선행 작업이라고하며이 노드로 이어지는 포인트를 후속 작업이라고합니다.

전기 회로도, 주택 계획, 컴퓨터 네트워크 또는 하천 시스템은 그래프의 몇 가지 예입니다. 많은 실제 사례가 그래프로 간주 될 수 있습니다.

기술 다이어그램은 다음과 같습니다

나무 :

그래프 :

아래 링크를 참조하십시오. 그것들은 나무와 그래프에 관한 거의 모든 질문에 대답 할 것입니다.

참고 문헌 :

1. http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-graphs/#_Toc362296541

2. http://www.community-of-knowledge.de/beitrag/data-trees-as-a-means-of-presenting-complex-data-analysis/

3. 위키 백과

---

트리에서 각 노드 (루트 노드 제외)에는 정확히 하나의 선행 노드와 하나 또는 두 개의 후속 노드가 있습니다. 주문, 주문, 주문 및 폭 우선 순회를 사용하여 순회 할 수 있습니다. 트리는주기가없는 DAG (Directed Acyclic Graph)라고하는 특수한 종류의 그래프입니다. 트리는 계층 적 모델입니다.

그래프에서 각 노드에는 하나 이상의 선행 노드 및 후속 노드가 있습니다. 그래프는 DFS (Depth First Search) 및 BFS (Breadth First Search) 알고리즘을 사용하여 순회합니다. 그래프는주기를 가지므로 트리보다 복잡합니다. 그래프는 네트워크 모델입니다. 유향 그래프와 무향 그래프의 두 종류의 그래프가 있습니다.

---

트리는 특별한 형태의 그래프, 즉 최소 연결 그래프이며 두 정점 사이에 하나의 경로 만 있습니다.

그래프 에는 둘 이상의 경로가있을 수 있습니다. 즉, 그래프는 노드간에 단방향 또는 양방향 경로 (에지)를 가질 수 있습니다.

또한 자세한 내용을 볼 수 있습니다 : http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

---

다른 답변은 유용하지만 각 속성이 누락되었습니다.

그래프

^{무향 그래프, 이미지 출처 : Wikipedia}

^{직접 그래프, 이미지 소스 : Wikipedia}

• 정점 세트 (또는 노드)와 그 일부 또는 전부를 연결하는 모서리 세트로 구성
• 모든 모서리는 동일한 모서리에 의해 아직 연결되지 않은 두 개의 정점을 연결할 수 있습니다 (유향 그래프의 경우 동일한 방향으로)
• Doesn't have to be connected (the edges don't have to connect all vertices together): a single graph can consist of a few disconnected sets of vertices

• Could be directed or undirected (which would apply to all edges in the graph)
  As per Wikipedia:

  For example, if the vertices represent people at a party, and there is an edge between two people if they shake hands, then this graph is undirected because any person A can shake hands with a person B only if B also shakes hands with A. In contrast, if any edge from a person A to a person B corresponds to A admiring B, then this graph is directed, because admiration is not necessarily reciprocated.

Tree

^{Image source: Wikipedia}

• A type of graph
• Vertices are more commonly called "nodes"
• Edges are directed and represent an "is child of" (or "is parent of") relationship
• Each node (except the root node) has exactly one parent (and zero or more children)
• Has exactly one "root" node (if the tree has at least one node), which is a node without a parent
• Has to be connected
• Is acyclic, meaning it has no cycles: "a cycle is a path [AKA sequence] of edges and vertices wherein a vertex is reachable from itself"

There is some overlap in the above properties. Specifically, the last two properties are implied by the rest of the properties. But all of them are worth noting nonetheless.

---

Trees are obvious: they're recursive data structures consisting of nodes with children.

Map (aka dictionary) are key/value pairs. Give a map a key and it will return the associated value.

Maps can be implemented using trees, I hope you don't find that confusing.

UPDATE: Confusing "graph" for "map" is very confusing.

Graphs are more complex than trees. Trees imply recursive parent/child relationships. There are natural ways to traverse a tree: depth-first, breadth-first, level-order, etc.

Graphs can have uni-directional or bi-directional paths between nodes, be cyclic or acyclic, etc. I would consider graphs to be more complex.

I think a cursory search in any decent data structures text (e.g. "Algorithms Design Manual") would give more and better information than any number of SO answers. I would recommend that you not take the passive route and start doing some research for yourself.

---

In mathematics, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.[1] Typically, a graph is depicted in diagrammatic form as a set of dots for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

---

one root node in tree and only one parent for one child. However, there is no concept of root node. Another difference is, tree is hierarchical model but graph is network model.

---

A tree is a digraph such that:

a) with edge directions removed, it is connected and acyclic

1. You can remove either the assumption that it is acyclic
2. 유한 한 경우 연결되어 있다는 가정을 제거 할 수도 있습니다.

b) 하나의 뿌리를 제외한 모든 정점이 1

c) 뿌리는 0도이다

1. 노드가 극소수 인 경우 루트가 0이라고 가정하거나 루트 이외의 노드가 1 도라는 가정을 제거 할 수 있습니다.

참조 : http://www.cs.cornell.edu/courses/cs2800/2016sp/lectures/lec27-29-graphtheory.pdf

참고 URL : https://stackoverflow.com/questions/7423401/whats-the-difference-between-the-data-structure-tree-and-graph