01/10/2018, 14:56

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

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 viết 17:08 ngày 01/10/2018

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.

Hung viết 17:03 ngày 01/10/2018

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

Nobita viết 17:11 ngày 01/10/2018

em cám ơn ạ …

Nobita viết 16:57 ngày 01/10/2018

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 viết 17:11 ngày 01/10/2018

Sửa lại pseudocode cho đẹp

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger