Đề 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 ma trận 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 ma trận kề tương ứng của đồ thị
Input | Output |
5 9 1 2 1 3 1 4 2 3 2 4 2 5 3 4 3 5 4 5 |
0 1 1 1 0 1 0 1 1 1 1 1 0 1 1 1 1 1 0 1 0 1 1 1 0 |
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 ma trận 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 ma trận kề tương ứng của đồ thị */ int n, m; //n: dinh, m: canh int a[1001][1001]; int main() { // Chuyen NHAP, XUAT thanh file freopen("lab1_1_input.INP", "r", stdin); freopen("lab1_1_output.OUT", "w", stdout); // INPUT cin >> n >> m; for(int i = 0; i < m; i++) { int x, y; cin >> x >> y; a[x][y] = a[y][x] = 1; // Do thi vo huong } // OUTPUT, ma tran ke: n dinh x n dinh for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { cout << a[i][j] << " "; } 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é!