Tôi muốn có thể tạo ra các đồ thị ngẫu nhiên, không bị phát hiện và được kết nối trong Java. Ngoài ra, tôi muốn có thể kiểm soát số lượng đỉnh tối đa trong biểu đồ. Tôi không chắc điều gì sẽ là cách tốt nhất để tiếp cận vấn đề này, nhưng đây là một vài điều tôi có thể nghĩ đến:Cách tạo biểu đồ ngẫu nhiên?
(1) Tạo một số giữa 0 và n và để đó là số đỉnh. Sau đó, bằng cách nào đó một cách ngẫu nhiên liên kết các đỉnh với nhau (có thể tạo ra một số ngẫu nhiên trên mỗi đỉnh và để cho đó là số lượng các cạnh ra khỏi đỉnh nói). Di chuyển đồ thị bắt đầu từ một đỉnh tùy ý (nói với Breadth-First-Search) và để đồ thị ngẫu nhiên của chúng tôi G là tất cả các nút được truy cập (theo cách này, chúng tôi đảm bảo rằng G được kết nối).
(2) Tạo ma trận vuông ngẫu nhiên (trong số 0 và 1) với chiều dài cạnh giữa 0 và n (bằng cách nào đó). Đây sẽ là ma trận kề cho biểu đồ của chúng ta (đường chéo của ma trận sau đó sẽ là tất cả 1 's hoặc tất cả 0' s). Tạo cấu trúc dữ liệu từ biểu đồ và duyệt biểu đồ từ bất kỳ nút nào để nhận danh sách các nút được kết nối và gọi biểu đồ G.
Bất kỳ cách nào khác để tạo biểu đồ đủ ngẫu nhiên đều được hoan nghênh. Lưu ý: Tôi không cần đồ thị hoàn toàn ngẫu nhiên, tức là biểu đồ bạn tạo không cần phải có bất kỳ thuộc tính toán học đặc biệt nào (như tính đồng nhất của một số loại). Tôi chỉ cần rất nhiều và rất nhiều đồ thị cho mục đích thử nghiệm của một cái gì đó khác.
Đây là lớp Java Node Tôi đang sử dụng:
public class Node<T> {
T data;
ArrayList<Node> children= new ArrayList<Node>();
...}
Đây là lớp Graph Tôi đang sử dụng (bạn có thể nói tại sao tôi chỉ quan tâm đến đồ thị kết nối tại thời điểm này):
public class Graph {
Node mainNode;
ArrayList<Node> V= new ArrayList<Node>();
public Graph(Node node){
mainNode= node;
}
...}
Như một ví dụ, đây là cách tôi làm cho đồ thị cho mục đích thử nghiệm ngay bây giờ:
//The following makes a "kite" graph G (with "a" as the main node).
/* a-b
|/|
c-d
*/
Node<String> a= new Node("a");
Node<String> b= new Node("b");
Node<String> c= new Node("c");
Node<String> d= new Node("d");
a.addChild(b);
a.addChild(c);
b.addChild(a);
b.addChild(c);
b.addChild(d);
c.addChild(a);
c.addChild(b);
c.addChild(d);
d.addChild(c);
d.addChild(b);
Graph G1= new Graph(a);
Đối với điều này, bạn có thể sử dụng thư viện tạo dữ liệu ngẫu nhiên như Quickcheck for Java. Tuy nhiên, các thư viện như vậy thường không có phương pháp dựng sẵn để tạo biểu đồ, vì vậy điều này có thể hơi phức tạp một chút. Hãy dùng thử và trả lời nếu bạn gặp sự cố. –
Tôi sẽ kết hợp hai cách tiếp cận. Ban đầu tạo một biểu đồ được kết nối đơn giản bằng cách kết nối một nút ngẫu nhiên không có trong biểu đồ với một nút ngẫu nhiên trong đó. Sau đó, từ các đỉnh có thể không được xác định ('0' trong ma trận), chọn một số để thêm vào biểu đồ để làm cho nó đậm đặc hơn. – millimoose
@RobinGreen, mặc dù có vẻ như Quickcheck sẽ giúp tạo ra các nguyên thủy, tôi vẫn sẽ phải tạo ra 'Node' chứa các phần tử nguyên thủy (đó là phần khó khăn hơn nhiều). Tôi cũng đang tìm kiếm một công trình rõ ràng hơn mà không cần sử dụng thư viện. – bourbaki4481472