Kiểm tra xem một biểu đồ đã cho có phải là cây hay không

Trong bài toán này, một đồ thị vô hướng được đưa ra, chúng ta phải kiểm tra xem đồ thị có phải là cây hay không. Chúng ta có thể đơn giản tìm thấy nó bằng cách kiểm tra các tiêu chí của một cây. Cây sẽ không chứa chu trình, vì vậy nếu có bất kỳ chu trình nào trong biểu đồ thì đó không phải là cây.

Chúng ta có thể kiểm tra nó bằng cách sử dụng một cách tiếp cận khác, nếu đồ thị được kết nối và nó có V-1 cạnh, nó có thể là một cái cây. Ở đây V là số đỉnh trong đồ thị.

Đầu vào và Đầu ra

 Đầu vào:Ma trận kề.0 0 0 0 10 0 0 0 10 0 0 0 10 0 0 0 11 1 1 1 0 Đầu ra:Biểu đồ là một cây 

Thuật toán

isCycle (u, đã thăm, cha mẹ)

Đầu vào: Đỉnh bắt đầu u, danh sách đã thăm để đánh dấu là đã ghé thăm hay chưa, đỉnh mẹ.

Đầu ra: Đúng nếu có một chu trình trong biểu đồ.

 Bắt đầu đánh dấu u là đã thăm cho tất cả đỉnh v liền kề với u, thực hiện nếu v được truy cập, sau đó nếu isCycle (v, đã thăm, u) =true, sau đó trả về true else nếu v ≠ cha, sau đó trả về true là xong trả về falseEnd 

isTree (biểu đồ)

Đầu vào: Biểu đồ vô hướng.

Đầu ra: Đúng khi biểu đồ là cây.

 Begin xác định một mảng đã truy cập để đánh dấu nút nào được truy cập hoặc không được truy cập ban đầu đánh dấu tất cả các nút là chưa được truy cập nếu isCycle (0, đã thăm, φ) là đúng, sau đó // đỉnh cha của đỉnh bắt đầu là null trả về false nếu biểu đồ là không được kết nối thì trả về false nếu không thì trả về true 
 Ví dụ 
 
 #include  #define NODE 5 sử dụng không gian tên std; int graph [NODE] [NODE] ={{0, 1, 1, 1, 0}, {1, 0, 1, 0, 0}, { 1, 1, 0, 0, 0}, {1, 0, 0, 0, 1}, {0, 0, 0, 1, 0}}; bool isCycle (int u, bool visit [], int parent) {visit [u] =true; // đánh dấu v là đã thăm cho (int v =0; v  
 Đầu ra 
 
 Biểu đồ là một cái cây.