Data Structures: What is the difference between a graph and a tree

Charts and trees are both the most common nonlinear data structures, so what are the differences between them? The following article will explain the difference between charts and trees. I hope it will be helpful to everyone.

Chart

The chart is composed of two sets V and E, where V is finite is a non-empty vertex set, and E is a finite non-empty edge set. It has the following properties:

1. A vertex represents a node in the graph and can be connected to any number of other vertices using edges.

2. Two adjacent vertices are connected by an edge. The edge can be bidirectional or directional; the edge can also be weighted.

3. Any graph can be expressed as: G = {V, E}.

For example:

Then: G = {{V1, V2, V3, V4, V5}, {E1, E2, E3, E4, E5 , E6, E7}}

Tree

The tree is a finite set K containing n (n>0) nodes and has the following properties :

1. There is a designated node at the top of the tree, which is called the root of the tree.

2. The remaining data items are divided into disjoint subsets, called subtrees.

3. The height of the tree expands toward the bottom.

4. The tree must be connected, which means there must be a path from one root to all other nodes.

5. It does not contain any loops.

6. The tree has n-1 edges.

For example:

Difference between chart and tree

Graph

1. Each node in the graph can have any number of edges, and the edges can be one-way or two-way.

2. There is no concept of a root node named root in the graph.

3. Graphs can have loops and self-loops

4. In a graph, there is no predefined number of edges, it depends on the graph.

5. The graph is the network model structure.

Tree

1. A regular tree consists of nodes with any number of child nodes; but in the case of a binary tree, each node can have up to two child nodes. There is only one edge between any two nodes.

2. There is a unique node named root in the tree.

3. The tree cannot have loops or self-loops

4. The tree can have n-1 edges.

5. The tree is a hierarchical structure.

The above is the entire content of this article, I hope it will be helpful to everyone's study. For more exciting content, you can pay attention to the relevant tutorial columns of the PHP Chinese website! ! !

The above is the detailed content of Data Structures: What is the difference between a graph and a tree. For more information, please follow other related articles on the PHP Chinese website!