Tạo cây khung như thế nào?

[Nobita1 (BK Anonymous)]

Em đang có một vấn đề như sau. Em code java.
Em muốn tạo 1 cây khung (chỉ cây khung thôi ạ, không quan tâm đến trọng số )bằng cách, chọn ngẫu nhiên một đỉnh (giả sư u) sau đó chọn ngẫu nhiên một đỉnh v là kề với u (xác định được qua ma trận kề). tiếp theo là đỉnh w là kề với u và không được kề với u, vì nếu kề với u tạo ra chu trình … cứ như vậy ta được các dãy định tạo thành cây khung khi số lần lập = n -1 .

Em nghĩ cả cách chày cối là lưu các đỉnh được chọn vào một mảng, sau khi chọn được đỉnh mới thì kiểm tra đỉnh mới này với các đinh trước đó trong mảng xem có kể nhau không, nhưng như thế rắc rối mà củ chuối quá
Các anh chị và các bạn giúp em với ạ. Em cám ơn nhiều

[rogp10]

DFS thôi (pseudo :D)

:graph G(V, E)
:set<Vertex> visited = empty_set;
:vector<Edge> ve = empty;

dfs(vertex V): foreach(v in set_filter(G.neighborOf(v), v => ~visited.found(v))
begin ve.append(new Edge(V, v)), visited.include(V); dfs(v); end;

BFS:

:graph G(V, E);
:set<Vertex> visited  = empty_set;
:queue<Vertex> flo = empty;
:vector<Edge> ve = empty;

wrap(vertex V): flo.enqueue(V); visited.include(V); bfs(); end;
bfs(): while(~flo.empty()) begin
V = flo.dequeue();
foreach(v in set_filter(G.neighborOf(V), v => ~visited.found(v))
begin ve.append(new Edge(V, v)), visited.include(v); flo.enqueue(v); end;
end;

Thực ra nếu thay vì dùng Visited thì dùng Usable (dùng rồi thì bỏ ra) nó hay hơn.

[hungaya (Hung)]

Xem qua hình như bạn không biết cách lưu graph bằng adjacent list

[Nobita1 (BK Anonymous)]

em cám ơn ạ …

[Nobita1 (BK Anonymous)]

em vừa cũng biết sơ qua, nhưng ưng dụng thì còn kém, em vừa tìm hiểu vừa cải thiện ạ.

[rogp10]

Sửa lại pseudocode cho đẹp