Cài đặt một số thao tác cơ bản trên một đồ thị hữu hướng

DoNg · January 24, 2021, 4:47am

Em đag học CS , giờ đag học môn AI , được thầy cho cái bài về đồ thị mà e đọc đề e thấy nó khó hiểu quá, ai bik chỉ giúp e là đề nó nói về cái gì ko ak T.T

Cài đặt một số thao tác cơ bản trên một đồ thị hữu hướng.

INPUT:
Dòng đầu tiên chứa 03 số v, e và n, đây lần lượt là số đỉnh, số cạnh của đồ thị cùng với số thao tác xử lý, giá trị mỗi số không quá 1 tỷ.
e dòng tiếp theo, mỗi dòng chứa 02 số u và i, thể hiện việc có một cạnh nối từ đỉnh thứ u sang đỉnh thứ i trong đồ thị (thứ tự các cạnh được đánh số từ 1…v)
n dòng tiếp theo, mỗi dòng tương ứng với một thao tác xử lý các thao tác có cú pháp như sau:
Thao tác kiểm tra tính kề của 02 đỉnh, dòng này bắt đầu bằng số 1, theo sau là 02 số u và i.
Thao tác tìm kiếm đỉnh lân cận của 01 đỉnh, dòng này bắt đầu bằng số 2, theo sau là số u

OUTPUT:

Ứng với thao tác kiểm tra tính kề của 02 đỉnh, xuất ra màn hình chuỗi TRUE nếu đỉnh thứ u kề với đỉnh thứ i. Nếu đỉnh thứ u không kề với đỉnh thứ i xuất ra chuỗi FALSE
Ứng với thao tác tìm kiếm đỉnh lân cận của 02 đỉnh, xuất ra màn hình trên cùng một dòng thứ tự của các đỉnh kề với đỉnh thứ u, các đỉnh xuất theo thứ tự tăng dần, cách nhau bởi khoảng trắng. Nếu không có đỉnh nào kề với đỉnh thứ u xuất ra chuỗi NONE

VD: Input :

Thầy hướng dẫn là dùng danh sách liên kết để lưu đồ thị, ai biết dùng như thế nào or có bài tập mẫu share cho e đc ko ạ ! e cảm ơn !

Phan_Hoang · March 11, 2016, 4:22am

Với graph thì mình thường hay sử dụng Vector hơn là LinkedList
(ở đây mình có thắc mắc là tại sao graph có 6 đỉnh mà tới 16 cạnh được nhỉ, vì với 1 cạnh nối 2 đỉnh thì số tổ hợp chỉnh không lặp chỉ có thể là 5*6/2 =15)

Bạn thử tham khảo xem link này họ lưu đỉnh graph bằng Vector xem sao.
http://smallcultfollowing.com/babysteps/blog/2015/04/06/modeling-graphs-in-rust-using-vector-indices/

Với LinkedList thì theo mình nghĩ sẽ lưu

entity đó (tên, những cạnh nối tới entity # ,)
pointer: chỉ sang entity bên cạnh
https://en.wikipedia.org/wiki/Linked_list

DoNg · March 11, 2016, 5:50am

phần ví dụ mình ghi còn thiếu , đầy đủ thế này nez :

13 dòng đầu là 2 đỉnh có cạnh chug,
7 dòng tiếp là thao tác mình cần xử lý ,

giờ mình không bik làm thế nào để lưu cái input kia để xử lý

tntxtnt · March 11, 2016, 6:53am

trong cái input có cạnh 5-3 tức là cạnh 3 có kề cạnh 5, sao output các cạnh kề của cạnh 3 lại chỉ có cạnh 1 và 6?? Đồ thị có hướng à?

code tối thiểu cho đồ thị vô hướng. Chuyển thành đồ thị có hướng thì chỉ cần xóa 1 dòng.

class UGraph
{
public:
    UGraph(int n) : adjList(n+1) {}
    void addEdge(int u, int v)
    {
        adjList[u].push_back(v);
        adjList[v].push_back(u);
    }
    std::vector<int> adj(int u)const { return adjList[u]; }
private:
    std::vector<std::vector<int>> adjList;
};

Gio · March 11, 2016, 9:40am

typdef long Node;
typedef unordered_map<Node, unordered_set<Node> > Graph;
Graph g;
void addEdge(Node u,Node v){
    g[u].insert(v);
    g[v].insert(u); 
}
// truy vấn 2 đỉnh liền kề 
bool isEdge(Node u,Node v){
      // u có  là 1 đỉnh của đồ thị?
     if(g.find(u)==g.end()) return false;
      // u - v là cạnh ?
     return g[u].find(v)!=g[u].end();
}

Phan_Hoang · March 11, 2016, 10:11am

Thao tác kiểm tra tính kề của 02 đỉnh, dòng này bắt đầu bằng số 1, theo sau là 02 số u và i.
Thao tác tìm kiếm đỉnh lân cận của 01 đỉnh, dòng này bắt đầu bằng số 2, theo sau là số u

Bạn thử mô tả rõ hơn về cái này, tại sao lại là số 1 và 2.
Thế nào được gọi là tính kề của 2 đỉnh?
Thế nào là đỉnh lân cận.
(học lâu quá rồi, chắc quên luôn rồi)

Mình có vẽ lại cái graph của bạn theo 13 dòng trên (dòng 14 sao lại giống dòng 5 nhỉ, cũng k thấy có số 1 và số 2)
Nếu theo graph này có phải 1 kề với 4 và 5, còn đỉnh lân cận của 1 là 3?

(Mình thường hay dùng Vectơ để biểu diễn graph hơn là LinkedList)

Gio · March 11, 2016, 11:01am

Code hoàn chỉnh

sửa unodered_set thành set
sửa hàm addEdge vì đồ thì có hướng
Chạy thử http://ideone.com/xjOyFa

#include <bits/stdc++.h>
using namespace std;
typedef long Node;
typedef unordered_map<Node, set<Node> > Graph;
Graph g;
void addEdge(Node u,Node v){
    g[u].insert(v);
  //  g[v].insert(u); 
}
// truy vấn 2 đỉnh liền kề 
bool isEdge(Node u,Node v){
      // u có  là 1 đỉnh của đồ thị?
     if(g.find(u)==g.end()) return false;
      // u - v là cạnh ?
     return g[u].find(v)!=g[u].end();
}
int main() {
	int n,m,q;
        cin>>n>>m>>q;
        while(m--) {
             Node u,v; cin>>u>>v; addEdge(u,v);
        }
        while(q--){
              Node u,v; int type;
              cin>>type;
              if (type==1){
                   cin>>u>>v;
                   cout<<(isEdge(u,v)?"TRUE":"FALSE")<<endl;
              }else{
                   cin>>u;
                   for (auto n:g[u]){ cout<<n<<" "; }
                   cout<<endl;
              }
        }
	return 0;
}

Phan_Hoang · March 11, 2016, 11:06am

Đúng là dùng Map và Set khá đơn giản nhỉ? Quá good (mình còn chưa hiểu rõ một số phần trong đề bài, và vẫn đang nghĩ theo hướng tổ chức LinkedList ^^)

DoNg · March 11, 2016, 2:45pm

cái này là dùng vector hả , hix , e chưa học về cái này , mà deadline nhanh quá, e cảm ơn ạ !

DoNg · March 11, 2016, 2:48pm

đúng rồi ,đồ thị có hướng đó bác

DoNg · March 11, 2016, 2:49pm

e cảm ơn nhiều lắm ak mới gặp lần đầu , mà thầy k cho bài mẫu nên ko bik bắt đầu như thế nào cả ^^

DoNg · March 11, 2016, 2:55pm

dòng 14 là số 2 đó : tìm đỉnh lân cận của đỉnh 3 - out put ra là 1 vs 6 đó a !

Phan_Hoang · March 11, 2016, 3:09pm

Mình đã hiểu đề bài rồi. ^^
Bạn ý không dùng LinkedList đâu mà sử dụng Map<Node, Set<Node>>,
nghĩa là ví dụ Node1 trỏ vào Node4 và Node5 (theo hình vẽ nhé) thì cái giá trị đầu tiên trong Map sẽ là
Node1 <–> Set(Node4, Node5)

với Set thì sẽ sắp xếp cho mình khi add vào Set, còn LinkedList thì không.
LinkedList phù hợp với các thao tác pop, push hơn.
Tuy nhiên, bài này dùng LinkedList cũng được
Node1 <–> LinkedList(Node4, Node5)

DoNg · March 11, 2016, 3:16pm

a có thể hướng dẫn e xài LinkedList đc ko, khai báo những struct nào , hàm nào, chứ map vs vector e chưa tìm hiểu kĩ đc, e định dùng list các cạnh, trong struct cạnh thì có thông tin đỉnh đầu , đỉnh cuối , sau đó duyệt ds … với lại em nộp bài trên hệ thống nó nhập input vào từng số như ở vd đó, nên mình phải làm sao cho nó nhập vào nữa ms ra đc kq !

tntxtnt · March 11, 2016, 3:30pm

xài map/hashmap làm adjList chậm lắm @_@ Vì muốn truy cập 1 phần tử trong adjList xài map thì phải tốn O(logn) thay vì O(1). Thậm chí hashmap cũng chậm hơn mảng thông thường nhiều. Xài mảng chỉ tốn O(n) bộ nhớ nên chấp nhận được, ko cần xài map để tiết kiệm bộ nhớ làm gì.

tương tự xài set để chứa các phần tử lân cận của 1 node cũng vậy: mỗi lần truy cập 1 phần tử trong đó là tốn O(logn) thay vì O(1) như mảng hay linked list. Thêm 1 edge vào cũng vậy, tốn O(logn) thay vì O(n). (Mặc dù chạy 1 vòng hết các phần tử trong set là O(n) như mảng, nhưng vẫn chậm hơn mảng.)

Re_Mon_Do · March 11, 2016, 3:43pm

còn có ai giúp dùm mình bài này luôn y.
Cài đặt một số thao tác cơ bản trên một đồ thị vô hướng.

INPUT:
Dòng đầu tiên chứa 03 số v, e và n, đây lần lượt là số đỉnh, số cạnh của đồ thị cùng với số thao tác xử lý, giá trị mỗi số không quá 1 tỷ.
e dòng tiếp theo, mỗi dòng chứa 02 số u và i, thể hiện việc có một cạnh nối từ đỉnh thứ u sang đỉnh thứ i trong đồ thị (thứ tự các cạnh được đánh số từ 1…v)
n dòng tiếp theo, mỗi dòng tương ứng với một thao tác xử lý các thao tác có cú pháp như sau:
Thao tác kiểm tra tính kề của 02 đỉnh, dòng này bắt đầu bằng số 1, theo sau là 02 số u và i.
Thao tác tìm kiếm đỉnh lân cận của 01 đỉnh, dòng này bắt đầu bằng số 2, theo sau là số u

OUTPUT:

Ứng với thao tác kiểm tra tính kề của 02 đỉnh, xuất ra màn hình chuỗi TRUE nếu đỉnh thứ u kề với đỉnh thứ i. Nếu đỉnh thứ u không kề với đỉnh thứ i xuất ra chuỗi FALSE
Ứng với thao tác tìm kiếm đỉnh lân cận của 02 đỉnh, xuất ra màn hình trên cùng một dòng thứ tự của các đỉnh kề với đỉnh thứ u, các đỉnh xuất theo thứ tự tăng dần, cách nhau bởi khoảng trắng. Nếu không có đỉnh nào kề với đỉnh thứ u xuất ra chuỗi NONE

Gio · March 11, 2016, 5:10pm

dùng hashmap vì chỉ số của đỉnh có thể đến 10^9. Có thể rời rạc hoá rồi làm như thông thường
kiểm tra đỉnh liền kề bằng linked list phải mất O(len(list)) để tìm còn set mất O(log(len(set))) nó còn tiện cho việc xuất ra đỉnh liền kề
code mang mục đích tham khảo nên không tối ưu.

tntxtnt · March 11, 2016, 5:14pm

nếu số đỉnh lên tới 10^9 mà chỉ có ví dụ 1000 đỉnh có cạnh, còn lại gần 1 tỷ đỉnh đứng riêng lẻ thì bỏ hết 1 tỷ đỉnh đó đi, làm cái graph 1000 đỉnh thôi Đổi thứ tự các đỉnh lại là được mà.

adjacent list là dành cho sparse graph, tức là từ mỗi đỉnh chỉ có khoảng K đỉnh kề, với K là hằng số. Tìm 1 đỉnh trong K đỉnh này có thể nói là O(K) hay O(1). Xài set thì giảm còn O(logK) cũng là O(1), logK đương nhiên lẹ hơn K, nhưng các phần tử trong set ko liên tục nhau, mỗi lần tìm phải deref con trỏ này con trỏ nọ so với mảng các phần tử nằm liên tục nhau thì logK có thể chậm hơn K. Chưa kể là set cồng kềnh hơn mảng nhiều. (adj list = càng nhẹ càng tốt)

DoNg · March 12, 2016, 11:37am

e làm xog cái LinkedList rồi nhưng nộp bài thì bộ test nó lớn quá bị lỗi Time limit , giờ cũng đề bài đó lưu về Danh sách kề thì a có biết lưu thế nào khi input nó chỉ nhập 2 đỉnh có chung cạnh như v ko T.T

Re_Mon_Do · March 13, 2016, 1:16am

ê ông cho tui xin code của ông tham khảo được hok.ông làm cái vô hướng chưa cho xin cái vô hướng á

Cài đặt một số thao tác cơ bản trên một đồ thị hữu hướng

Thao tác kiểm tra tính kề của 02 đỉnh, dòng này bắt đầu bằng số 1, theo sau là 02 số u và i. Thao tác tìm kiếm đỉnh lân cận của 01 đỉnh, dòng này bắt đầu bằng số 2, theo sau là số u

Thao tác kiểm tra tính kề của 02 đỉnh, dòng này bắt đầu bằng số 1, theo sau là 02 số u và i.
Thao tác tìm kiếm đỉnh lân cận của 01 đỉnh, dòng này bắt đầu bằng số 2, theo sau là số u