Lý thuyết đồ thị | Cấu trúc dữ liệu và giải thuật | Đại học Bách Khoa Hà Nội

Lý thuyết đồ thị
Đồ thị là cấu trúc dữ liệu gồm 2 phần sau:
Là tập hữu hạn các đỉnh gọi là các nút
Một tập hữu hạn các cặp có dạng (u,v) gọi là cạnh. Cặp có thứ tự vì (u,v)
khác (v,u) trong trường hợp đồ thị có hướng (đồ thị động). Cặp có dạng
(u,v) chỉ ra rằng có một cạnh từ đỉnh u tới đỉnh v. Các cạnh có thể chứa giá trị (chi phí).
Sau đây là ví dụ về đồ thị vô hướng 5 đỉnh:
Cách biểu diễn đồ thị đ ợ
ư c sử dụng nhiều nhất: O Ma trận kề O Danh sách kề
Có các đại diện khác cũng như, Ma trận tỷ lệ và Danh sách tỷ lệ. Việc lựa chọn biểu
diễn đồ thị là tùy theo tình huống cụ thể. Nó hoàn toàn phụ thuộc vào loại hoạt động
được thực hiện và tính dễ sử dụng. 1. Ma trận kề
Ma trận kề là một mảng 2D có kích thước V*V trong đó V là số đỉnh của đồ thị
adj[][] , trong đó adj[i][j] = 1 chỉ ra rằng có một cạnh từ đỉnh i tới đỉnh j. Ma trận
kề cho đồ thị vô hướng luôn đối xứng. Ma trận kề cũng được sử dụng để biểu diễn đồ t ị
h có trọng số. Nếu adj [i] [j] = w, thì có một cạnh từ đỉnh i đến đỉnh j có trọng số w. Trịnh Xuân Đạt
Ma trận kề cho biểu đồ ví dụ t ê r n:
Ưu điểm: Trình diễn dễ thực hiện và dễ theo dõi hơn. Việc loại bỏ một cạnh mất O
(1) thời gian. Các truy vấn như liệu có cạnh từ đỉnh 'u' đến đỉnh 'v' là hiệu quả và có
thể được thực hiện O (1).
Nhược điểm: Tốn nhiều khoảng trống hơn O (𝑉2). Ngay cả khi đồ thị thưa thớt
(chứa ít cạnh hơn), nó vẫn sử dụng cùng một không gian. Thêm một đỉnh là O (𝑉2) thời gian. Trịnh Xuân Đạt
Cho số đỉnh số cạnh và các thông số cảu đồ thị hãy biểu diễn nó dưới ma trận kề. Đầu vào: Số đỉnh Số cạch
Các thông số kết nối của các đỉnh Kết quả:
Ma trận kề biểu diễn đồ thị Test case: Đầu vào: Kết quả: 4 0 1 0 0 5 0 0 0 1 1 2 1 0 0 1 2 4 0 1 0 0 3 1 3 4 4 2 Trịnh Xuân Đạt Code mẫu: #include using namespace std; //by code Đạt Trịnh bool A[10] 1 [ 0]; void initialize() { for(int i = 0; i < 1 ; 0 ++i) for(int j = 0; j < 1 ; 0 ++j) A[i][j] = false; } int main() { int x, y, nodes, edges; initialize(); cin >> nodes; cin >> edges;
for(int i = 0; i < edges; ++i) { cin >> x >> y; A[x][y] = true; } for(int i=1;i<=node ; s ++i){ for(int j=1;j<=node ; s ++j) if(A[i][j]){ cout<<1<<' '; }
else cout<<0<<' '; cout<<'\n'; } } Trịnh Xuân Đạt 2. Danh sách kề
Một mảng danh sách được sử dụng. Kích thước của mảng bằng số đỉnh. Cho mảng
là mảng []. Một mảng mục [i] đại diện cho danh sách các đỉnh kề với đỉnh thứ i .
Biểu diễn này cũng có thể được sử dụng để biểu diễn một đồ thị có trọng số. Trọng
số của các cạnh có thể được biểu diễn dưới dạng danh sách các cặp. Sau đây là biểu
diễn danh sách kề của biểu đồ trên. Code biểu diễn: #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; cin >> n >> m; vector adj[n]; for(int i=0;i int x,y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } int k; cin >> k; cout< for(auto i:adj[k]){ cout<<" "< } } Trịnh Xuân Đạt Giải thích: Đồ t ị
h gồm n điểm và m cạnh
vector adj[n]; Khai báo danh sách kề.
Nạp dữ liệu của đồ thị cho danh sách: for(int i=0;i int x,y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); }
Hiện thông tin các đỉnh kề với đỉnh k nào đó: int k; cin >> k; cout< for(auto i:adj[k]){ cout<<" "< } Duyệt đồ thị:
Có 2 cách phổ thông nhất để duyệt đồ thị đó là loang theo chiều rộng (bfs) và
loang theo chiều sâu (dfs). 1: BFS - Breadth First Search
Phương pháp tiếp cận: Vấn đề này có thể được giải quyết bằng cách sử dụng
phương thức truyền tải đầu tiên theo chiều rộng đơn giản từ một nguồn nhất định.
Việc triển khai sử dụng danh sách kề. Trịnh Xuân Đạt
Bài ví dụ: Duyệt BFS để in ra khoảng cách từ nút 1 đến các nút còn lại #include using namespace std; vector adj[100005]; int d[10005]; void bfs(){ int u, i, v; queue qu; qu.push(1); d[1] = 1; while (qu.size()) { u = qu.front(); qu.pop(); for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (d[v] == 0) { d[v] = d[u] + 1; qu.push(v); } } } } int main() { int n,m; cin >> n >> m; for(int i=0;i int x,y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); } bfs();
for(int i=1;i<=n;++i)cout< i < <<' ';
cout< for(int i=1;i<=n;++i)cout< d < [i]<<' '; } Trịnh Xuân Đạt Bài thực hành:
Cho đồ thị gồm n đỉnh m cạnh. Đếm xem đồ thị có bao nhiêu tầng level khác nhau. Dữ liệu:
Dòng nhất gồm 2 số nguyên n , m số đỉnh – số cạnh
m dòng tiếp theo mỗi dòng gồm 2 số nguyên x,y nút x nối với nút y. Kết quả:
In ra số nguyên duy nhất là số level của đồ thị. Ví dụ: INPUT OUTPUT 5 4 3 1 2 2 3 3 4 1 4 Trịnh Xuân Đạt Đề bài:
Bạn đã được cung cấp một Cây bao gồm N nút. Cây là một biểu đồ được kết nối
đầy đủ bao gồm N nút và N−1 cạnh. Đầu vào:
Dòng đầu tiên bao gồm một số nguyên N biểu thị số lượng nút trong
cây. Mỗi cái tiếp theo n−1 chứa các thông số kết nối 2 đỉnh Số nguyên x Kết quả:
Bạn cần in một số nguyên duy nhất biểu thị số lượng nút trên cấp x . Ràng buộc: Ghi chú
Đảm bảo rằng ít nhất một nút sẽ nằm trên cấp x Trịnh Xuân Đạt Test case: Đầu vào: Kết quả: 20 3 11 1 1 2 13 3 15 4 17 5 11 6 2 7 1 8 15 9 4 10 15 12 5 13 2 14 17 15 15 16 11 17 15 18 9 19 16 20 2 Hà nội - 2020 Trịnh Xuân Đạt
Giải thuật: Áp dụng cơ bản BFS có trong hướng dẫn tại BFS cơ bản. Chương trình: #include using namespace std; // Trịnh Xuân Đạt int n; vector> G(100005); vector ves(100005,false); vector lev(1000,-1); void bfs(int s){ queue Q; Q.push(s); ves[s]=tru ; e lev[s]=1; while(!Q.empty()){ int v = Q.front(); Q.pop(); for(auto &i:G[v]){ if(ves[i] == false){ lev[i] = lev[v]+1; Q.push(i); ves[i] = true; } } } } int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; for(int i=1;i+ ){ int x,y; cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } int o,d=0; cin >> o; bfs(1); for(int i=1;i<=n;++i){ if(lev[i]==o)d++; } cout< return 0; } Trịnh Xuân Đạt Đề Bài:
Nhà sư đến thăm vùng đất của Quần đảo. Có tổng cộng N hòn đảo được đánh số từ
1 đến N . Một số cặp đảo được kết nối với nhau bằng những cây cầu hai chiều chạy trên mặt nước.
Đạt ghét đi qua những cây cầu này vì chúng đòi hỏi rất nhiều nỗ lực. Anh ta đang
đứng ở Đảo số 1 và muốn đến Đảo số N. Tìm tối thiểu số lượng cầu mà anh ta sẽ
phải đi qua, nếu anh ta đi theo con đường tối ưu. Đầu vào:
Dòng đầu chứa T . Số test kiểm tra .
Dòng đầu tiên của mỗi bộ test chứa hai số nguyên N , M .
Mỗi dòng trong số M dòng chứa hai số nguyên X và Y , biểu thị rằng có một
cầu nối giữa đảo X và Đảo Y . Kết quả:
In câu trả lời cho từng tr ờ
ư ng hợp kiểm tra trong một dòng mới Ràng buộc: Test case: Trịnh Xuân Đạt Đầu vào: Kết quả: 2 2 3 2 2 1 2 2 3 4 4 1 2 2 3 3 4 4 2 Hà Nội - 2020
Giải thuật: BFS đánh dấu level
Để giải được bài này bạn cần phải học qua BFS cơ bản mà tôi đã trình bày trong tài
liệu gốc. Từ đó sẽ biết cách đánh dấu level từng cấp độ cho các nút trong đồ thị.
Công việc khá đơn giản chỉ là in ra level của nút N trong đồ thị đã đánh dấu ấy. Trịnh Xuân Đạt Chương trình: #include using namespace std; int n,m; vector> G; vector ves; vector lev; void bfs(int s){ queue Q; Q.push(s); ves[s]=tru ; e lev[s]=0; while(!Q.empty()){ int v = Q.front(); Q.pop(); for(auto &i:G[v]){ if(ves[i] == false){ lev[i] = lev[v]+1; Q.push(i); ves[i] = true; } } } } void solve(){ cin >> n >> m ; G.clear(); G.resize(100005);
ves.clear(); ves.resize(1000005,false);
lev.clear() ; lev.resize(10005); for(int i=0;i+ ){ int x,y; cin >> x >> y; G[x].push_back(y); G[y].push_back(x); } bfs(1); cout<} int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin >> t; while(t- ) - solve(); return 0; } Trịnh Xuân Đạt Trịnh Xuân Đạt