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

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

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

AI.jpg973x687 19.2 KB

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ý

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;
};

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();
}

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)

P_20160311_170623.jpg4096x2304 1.21 MB

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)

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;
}

Đú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 ^^)

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 ạ !

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

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ả ^^

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 !

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)

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 !

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.)

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

Captuddre.JPG929x579 11.7 KB

• 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.

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)

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

kiểm tra tính kề của 02 đỉnh

ê ô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 á

Bài này in hệt bài trên mà (bạn cứ dùng đúng thuật toán mà các bạn ý bầy) rồi customize theo là được.
Chịu khó viết code (chỉ nên hỏi thuật toán và cách tổ chức dữ liệu thôi) thì mới dần dần đỡ ngại và yêu nghề coding hơn. ^^