Chương trình C ++ để tạo một đồ thị ngẫu nhiên bằng cách sử dụng thế hệ cạnh ngẫu nhiên

Trong chương trình này, một đồ thị ngẫu nhiên được tạo ra cho các đỉnh và cạnh ngẫu nhiên. Độ phức tạp về thời gian của chương trình này là O (v * e). Trong đó v là số đỉnh và e là số cạnh.

Thuật toán

 Begin Phát triển một hàm GenRandomGraphs (), với ‘e’ là số cạnh và ‘v’ là số đỉnh, trong danh sách đối số. Gán các giá trị ngẫu nhiên cho số đỉnh và số cạnh của đồ thị, sử dụng hàm rand (). In các kết nối của mỗi đỉnh, không phân biệt hướng. In “Đỉnh biệt lập” cho đỉnh không có bậc. End 

Ví dụ

 #include  #include  using namespace std; void GenRandomGraphs (int NOEdge, int NOVertex) {int i, j, edge [NOEdge] [2], count; i =0; // Gán các giá trị ngẫu nhiên cho số đỉnh và số cạnh của đồ thị, sử dụng hàm rand (). while (i  {"; for (j =0; j  
 Đầu ra 
 
 Tạo đồ thị ngẫu nhiên:Đồ thị có 8 đỉnh và có 18 cạnh. Đồ thị ngẫu nhiên được tạo là:1-> {5 4 2} 2-> {4 8 6 3 1 5} 3-> {5 4 7 2} 4-> {2 3 7 1 8 5} 5-> {3 1 7 4 2 8} 6-> {2 8 7} 7-> {4 3 5 6} 8-> {2 6 4 5}