Nền tảng Kiến thức - Hành trang tới Tương lai
Card image

Chương 1-Bài 8. Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề

Tác giả: Dương Nguyễn Phú Cường #11154
Ngày đăng: Hồi xưa đó
Lượt xem: 173

Đề bài

Cho đồ thị vô hướng G=<V,E> được biểu diễn dưới dạng ma trận kề. 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 số n là số đỉnh của đồ thị (1 <= n <= 1000)
  • N dòng tiếp theo, mỗi dòng N số biểu diễn ma trận kề của đồ thị.

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
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
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 ma trận kề. 
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 số n là số đỉnh của đồ thị (1 <= n <= 1000)
N dòng tiếp theo, mỗi dòng N số biểu diễn ma trận kề của đồ thị.

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
int a[1001][1001]; // ma tran ke
vector<int> adj[1001]; // danh sach ke

int main() {
  // Chuyen NHAP, XUAT thanh file
  freopen("lab1_4_input.INP", "r", stdin);
  freopen("lab1_4_output.OUT", "w", stdout);
  
  // INPUT
  cin >> n;
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      cin >> a[i][j];
    }
  }
  
  // In ra ma tran ke vua lay duoc
//	cout << "Ma tran ke: " << n << " dinh" << endl;
//	for(int i = 1; i <= n; i++) {
//		for(int j = 1; j <= n; j++) {
//			cout << a[i][j] << " ";
//		}
//		cout << endl;
//	}
  
  // Luu vao danh sach ke
  for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
      if(a[i][j] == 1
        && i < j)
      {
        adj[i].push_back(j);
        adj[j].push_back(i);
      }
    }
  }
  
  // OUTPUT, danh sach ke
  for(int i = 1; i <= n; i++) {
    cout << i << ": ";
    for(int x: adj[i]) {
      cout << x << " ";
    }
    cout << endl;
  }
}

Chương trình học


  1. Lý thuyết đồ thị 31
    1. Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
    2. Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
    3. Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
    4. Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
    5. Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
    6. Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
    7. Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
    8. Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
    9. Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
    10. Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
    11. Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
    12. Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
    13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
    14. Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
    15. 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
    16. Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
    17. 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
    18. Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
    19. Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
    20. 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
    21. 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
    22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
    23. 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
    24. Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
    25. 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
    26. Chu trình và đường đi Euler #11519
    27. Lab 7 - Tìm chu trình Euler #11520
    28. Lab 7.1 - Tìm đường đi Euler #11528
    29. Bài toán Luồng cực đại #11532
    30. Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
    31. Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
  2. Tài liệu tham khảo 2
    1. Kho sách, nguồn tài liệu tham khảo Lập trình C++ - Cấu trúc dữ liệu và Giải thuật #11100
    2. Bài tập Lý thuyết Đồ thị có lời giải #11547
  3. Quy hoạch động 1
    1. Lý thuyết các bài toán sử dụng Quy hoạch động #11567
Các bài học

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


  1. Lý thuyết đồ thị 31
    1. Các khái niệm cơ bản về Lý thuyết Đồ thị #11087
    2. Biểu diễn đồ thị trên máy tính bằng Ma trận kề #11112
    3. Biểu diễn đồ thị trên máy tính bằng Danh sách cạnh #11117
    4. Biểu diễn đồ thị trên máy tính bằng Danh sách kề #11116
    5. Lab 1 - Chuyển Danh sách cạnh sang Ma trận kề #11138
    6. Lab 1.2 - Chuyển Danh sách cạnh sang Danh sách kề #11144
    7. Lab 1.3 - Chuyển Ma trận kề sang Danh sách cạnh #11151
    8. Lab 1.4 - Chuyển Ma trận kề sang Danh sách kề #11154
    9. Lab 1.5 - Chuyển Danh sách kề sang Ma trận kề #11158
    10. Lab 1.6 - Chuyển Danh sách kề sang Danh sách cạnh #11161
    11. Duyệt cây theo chiều sâu DFS (Depth First Search) #10963
    12. Duyệt cây theo chiều rộng BFS (Breadth First Search) #11081
    13. Thuật toán Tìm đường đi giữa 2 đỉnh của Đồ thị bằng C/C++ #11079
    14. Lab 2 - Duyệt cây theo chiều sâu DFS (Depth First Search) #11167
    15. 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
    16. Lab 3 - Duyệt cây theo chiều rộng BFS (Breadth First Search) #11169
    17. 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
    18. Lab 4 - Tìm các thành phần liên thông trên đồ thị vô hướng #11179
    19. Tìm đường đi ngắn nhất bằng Thuật toán Dijkstra #11403
    20. 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
    21. 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
    22. Thuật toán Kruskal – Tìm cây khung (bao trùm) nhỏ nhất #11485
    23. 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
    24. Thuật toán Prim - Tìm cây khung (bao trùm) nhỏ nhất #11516
    25. 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
    26. Chu trình và đường đi Euler #11519
    27. Lab 7 - Tìm chu trình Euler #11520
    28. Lab 7.1 - Tìm đường đi Euler #11528
    29. Bài toán Luồng cực đại #11532
    30. Lab 8 - Tìm luồng cực đại - sử dụng thuật toán Ford - Fulkerson #11533
    31. Lab 8.1 - Tìm luồng cực đại - sử dụng thuật toán Edmonds - Karp (Shortest path) #11534
  2. Tài liệu tham khảo 2
    1. Kho sách, nguồn tài liệu tham khảo Lập trình C++ - Cấu trúc dữ liệu và Giải thuật #11100
    2. Bài tập Lý thuyết Đồ thị có lời giải #11547
  3. Quy hoạch động 1
    1. Lý thuyết các bài toán sử dụng Quy hoạch động #11567

Bài học trước Bài học tiếp theo