Các loại biểu đồ trong cấu trúc dữ liệu kèm ví dụ

A graph is a non-linear data structure that consists of vertices and edges. The vertices contain the information or data, and the edges work as a link between a pair of vertices.

Graphs can be of multiple types, depending on the position of the nodes and edges. Here are some important types of Graphs:

Đồ thị có hướng

The edges of the Directed Graph contain arrows that mean the direction. The arrow determines where the edge is pointed to or ends. Here is an example of the Directed Graph.

Đồ thị có hướng

• Chúng ta có thể đi từ Nút A đến D.
• However, we cannot go from node D to node A, as the edge points from A to D.
• Vì Đồ thị không có trọng số nên việc di chuyển từ đỉnh A đến D sẽ có chi phí tương đương với việc di chuyển từ D đến F.

Đồ thị vô hướng

An Undirected Graph contains edges without pointers. It means we can travel vice versa between two vertices. Here is a simple example of the undirected Graph.

Đồ thị vô hướng

Trong biểu đồ trên,

• We can move from A to B.
• We can also move from B to A.
• Các cạnh không chứa hướng.

It is an example of an undirected graph having a finite number of vertices and edges with no weights.

Biểu đồ có trọng số

A Graph that contains weights or costs on the edges is called a weighted Graph. The numerical value generally represents the moving cost from one vertex to another vertex. Both Directed and Undirected Graphs can have weights on their edges. Here is an example of a weighted graph (Directed).

Đồ thị có hướng có trọng số

• A to B, there is an edge, and the weight is 5, which means moving from A to B will cost us 5.
• A points to B, but in this Graph, B has no direct edge over A. So, we cannot travel from B to A.
• However, if we want to move from A to F, there are multiple paths. The paths are ADF and ABF. ADF will cost (10+11) or 21.
• Here, the path ABF will cost (5+15) or 20. Here we are adding the weight of each edge in the path.

Here is an example of an Undirected Graph with weights:

Đồ thị vô hướng có trọng số

Ở đây, cạnh có trọng lượng nhưng không có hướng. Vì vậy, có nghĩa là đi từ đỉnh A đến D sẽ tốn 10 và ngược lại.

Đồ thị hai chiều

Bi-directional and undirected graphs have a common property. That is:

• Generally, the undirected Graph can have one edge between two vertices.

Ví dụ:

• Ở đây, di chuyển từ A đến D hoặc D sang A sẽ tốn 10.
• Trong đồ thị hai chiều, chúng ta có thể có hai cạnh giữa hai đỉnh.

Đây là một ví dụ:

Đồ thị hai chiều

Traveling from A to D will cost us 17, but traveling from D to A will cost us 12. So, we cannot assign two different weights if it is an undirected graph.

Đồ thị vô hạn

The Graph will contain an infinite number of edges and nodes. If a graph is Infinite and it is also a connected graph, then it will contain an infinite number of edges as well. Here, the extended edges mean that more edges might be connected to these nodes via edges. Here is an example of the infinite Graph:

Đồ thị vô hạn

Đồ thị rỗng

A Null Graph contains only nodes or vertices but with no edges. If given a Graph G = (V, E), where V is vertices and E is edges, it will be null if the number of edges E is zero. Here is an example of a Null Graph:

Đồ thị rỗng

Đồ thị tầm thường

A graph data structure is considered trivial if only one vertex or node is present with no edges. Here is an example of a Trivial Graph:

Đa đồ thị

A graph is called a multigraph when multiple edges are present between two vertices, or the vertex has a loop. The term “Loop” in Graph Data Structure means an edge pointing to the same node or vertex. A multigraph can be directed or undirected. Here is an example of a Multi Graph:

There are two edges from B to A. Moreover, vertex E has a self-loop. The above Graph is a directed graph with no weights on edges.

Đồ thị hoàn chỉnh

A graph is complete if each vertex has directed or undirected edges with all other vertices. Suppose there is a total of V number of vertices and each vertex has exactly V-1 edges. Then, this Graph will be called a Complete Graph. In this type of Graph, each vertex is connected to all other vertices via edges. Here is an example of a Complete Graph with five vertices:

You can see in the image that the total number of nodes is five, and all the nodes have exactly four edges.

Đồ thị được kết nối

A Graph is called a Connected graph if we start from a node or vertex and can travel to all the nodes from the starting node. For this, there should be at least one edge between each pair of nodes or vertices. Here is an example of a Connected Graph:

Here is some explanation of the above Connected Graph:

• Assuming there is no edge between C and F, we cannot travel from A to G. However, the edge C to F enables us to travel to any node from a given node.
• Biểu đồ hoàn chỉnh là Biểu đồ được kết nối vì chúng ta có thể di chuyển từ nút này sang bất kỳ nút nào khác trong Biểu đồ đã cho.

Đồ thị tuần hoàn

A graph is said to be cyclic if there are one or more cycles present in the Graph. Here is an example of a Cyclic Graph:

Here, vertices A, B, and C form a cycle. A graph can have multiple cycles inside it.

Đồ thị vòng có hướng (DAG)

A Graph is called a Directed Acyclic Graph or DAG if there are no cycles inside a graph. DAG is important while doing the Sắp xếp theo cấu trúc liên kết or finding the execution order. DAG is also important for creating scheduling systems or scanning dependency of resources, etc. However, the Graph above does not contain any cycle inside. Here is a simple example of a Directed Acyclic Graph (DAG):

Đồ thị chu kỳ

A Cycle Graph is not the same as the cyclic Graph. In a Cycle Graph, each node will have exactly two edges connected, meaning each node will have exactly two degrees. Here is an example of a Cycle Graph:

Đồ thị hai bên

Những loại Đồ thị are special kinds of Graph where vertices are assigned to two sets. A Bipartite Graph must follow the rule:

• The two sets of vertices should be distinct, which means all the vertices must be divided into two groups or sets.
• Same-set vertices should not form any edges.

Đồ thị Euler

A Graph data structure is considered an Euler Graph if all the vertices have an even-numbered degree. The term degree of vertices means the number of edges pointing to or pointing out from a particular vertex. Here is an example of a Euler graph:

All the vertices have even degrees. Vertices A, D, E, and H have two degrees. Here, node C has four degrees, which is even.

Đồ thị Hamilton

A Hamilton Graph is a Connected Graph, where you can visit all the vertices from a given vertex without revisiting the same node or using the same edge. This kind of Connected Graph is known as the “Hamilton Graph”. The path you visit to verify if the given Graph is a Hamilton Graph or not is known as the Hamiltonian Path. Here is a simple graph example of a Hamilton:

Trong hình ảnh này, chúng ta có thể truy cập tất cả các đỉnh từ bất kỳ nút nào trong Biểu đồ trên. Một trong những con đường có thể là ADCHBE. It is also possible to find a Hamilton Cycle. A Hamilton Cycle starts and ends at the same vertex. So, the Hamilton Cycle will be A-D-C-H-B-E-A.

Câu Hỏi Thường Gặp