Đề bài
Cho đồ thị vô hướng G=<V,E> được biểu diễn dưới dạng danh sách cạnh. Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị dưới dạng danh sách kề.Input
- Dòng đầu tiên chứa 2 số n, m là số đỉnh và số cạnh của đồ thị (1 <= n <= 1000, 1 <= m <= n*(n-1)/2).
- M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n). Các cạnh được liệt kê theo thứ tự tăng dần của các đỉnh đầu.
Output
- In ra danh sách kề tương ứng của đồ thị, liệt kê theo thứ tự tăng dần của các đỉnh
Input | Output |
5 9 1 2 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5 |
1: 2 3 4 2: 1 3 4 5 3: 1 2 4 5 4: 1 2 3 5 5: 2 3 4 |
Giải
- Source code:
#include<bits/stdc++.h> #include <iostream> using namespace std; /* Cho đồ thị vô hướng G=<V,E> được biểu diễn dưới dạng danh sách cạnh. Hãy viết chương trình thực hiện chuyển đổi biểu diễn đồ thị dưới dạng danh sách kề. Input Dòng đầu tiên chứa 2 số n, m là số đỉnh và số cạnh của đồ thị (1 <= n <= 1000, 1 <= m <= n*(n-1)/2). M dòng tiếp theo, mỗi dòng là 2 số u, v biểu diễn cạnh u, v của đồ thị (1 <= u, v <= n). Các cạnh được liệt kê theo thứ tự tăng dần của các đỉnh đầu. Output In ra danh sách kề tương ứng của đồ thị, liệt kê theo thứ tự tăng dần của các đỉnh */ int n, m; //n: dinh, m: canh vector<int> adj[1001]; // adj[i]: luu danh sach ke cua dinh i int main() { // Chuyen NHAP, XUAT thanh file freopen("lab1_2_input.INP", "r", stdin); freopen("lab1_2_output.OUT", "w", stdout); // INPUT cin >> n >> m; for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); // Do thi vo huong } // OUTPUT, danh sach ke for(int i = 1; i <= n; i++) { cout << i << ": "; for(int x: adj[i]) { cout << x << " "; } cout << endl; } }
Mục lục
Chương trình học
-
Lý thuyết đồ thị
31
- Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
- Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
- Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
- Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
- Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
- Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
- Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
- Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
- Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
- Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
- Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
- Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
- Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
- Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
- Lab 2.2 - Tìm đường đi bằng cách duyệt cây theo chiều sâu DFS (Depth First Search) #11168
- Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
- Lab 3.2 - Tìm đường đi bằng cách duyệt cây theo chiều rộng BFS (Breadth First Search) #11170
- Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
- Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
- Lab 5 - Tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị (sử dụng thuật toán Dijkstra) #11418
- Lab 5.1 - Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T trên đồ thị (sử dụng thuật toán Dijkstra) #11423
- Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
- Lab 6 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán Kruskal) #11486
- Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
- Lab 6.1 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán PRIM) #11515
- Chu trình và đường đi Euler #11519
- Lab 7 - Tìm chu trình Euler #11520
- Lab 7.1 - Tìm đường đi Euler #11528
- Bài toán Luồng cực đại #11532
- Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
- Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
- Tài liệu tham khảo 2
- Quy hoạch động 1
Các bài học
Bài học trước Bài học tiếp theo
Chương trình học
Bao gồm Module, Chương, Bài học, Bài tập, Kiểm tra...Chương trình học
-
Lý thuyết đồ thị
31
- Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
- Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
- Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
- Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
- Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
- Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
- Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
- Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
- Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
- Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
- Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
- Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
- Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
- Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
- Lab 2.2 - Tìm đường đi bằng cách duyệt cây theo chiều sâu DFS (Depth First Search) #11168
- Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
- Lab 3.2 - Tìm đường đi bằng cách duyệt cây theo chiều rộng BFS (Breadth First Search) #11170
- Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
- Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
- Lab 5 - Tìm đường đi ngắn nhất từ đỉnh S đến tất cả các đỉnh còn lại trên đồ thị (sử dụng thuật toán Dijkstra) #11418
- Lab 5.1 - Tìm đường đi ngắn nhất từ đỉnh S đến đỉnh T trên đồ thị (sử dụng thuật toán Dijkstra) #11423
- Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
- Lab 6 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán Kruskal) #11486
- Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
- Lab 6.1 - Tìm cây khung (bao trùm) cực tiểu nhỏ nhất (sử dụng thuật toán PRIM) #11515
- Chu trình và đường đi Euler #11519
- Lab 7 - Tìm chu trình Euler #11520
- Lab 7.1 - Tìm đường đi Euler #11528
- Bài toán Luồng cực đại #11532
- Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
- Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
- Tài liệu tham khảo 2
- Quy hoạch động 1
Bài học trước Bài học tiếp theo
Menu Tiện ích
Menu Hướng dẫn Học tập
❤🧡💛💚💙💜 Học là phải THỰC HÀNH ❤🧡💛💚💙💜
Thực hiện các bước tuần tự theo nội dung Bài học nhé!