# data[].attributes.body
BIỂU DIỄN ĐỒ THỊ BẰNG MA TRẬN KỀ

# data[].attributes.attachment_link.readable_text
Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844

Trong lý thuyết đồ thị, việc tổ chức dữ liệu cho từng bài toán, thuật toán rất quan trọng, nó quyết định kích thước dữ liệu bài toán, thời gian thực tế của bài toán. Vì vậy trong bài viết này mình sẽ giới thiệu các bạn một số cách tổ chức dữ liệu trong đồ thị.

1. Tổng quan về ma trận kề trong lý thuyết đồ thị

Giả sử chúng ta có một đơn đồ thị vô hướng không trọng số, có n đỉnh. Chúng ta coi như các đỉnh được đánh số từ 1 đến n.

Tổ chức dữ liệu theo kiểu ma trận kề trong lý thuyết đồ thị bằng cách xây dựng ma trận vuông a[i,j] cấp n. Với:

A[i][j] = 1 khi đồ thi của chúng ta có cạnh nối từ đỉnh i đến đỉnh j.

A[i][j] = 0 khi đồ thị không có cạnh nối từ đỉnh i đến đỉnh j.

a. Đề bài ví dụ

Cho đồ thị đơn vô hướng, dữ liệu lấy từ input, dòng gồm 2 số n, m là số đỉnh và số cạnh của đồ thị, m dòng tiếp theo, mỗi dòng gồm 2 số u, v thể hiện cạnh nối giữa 2 đỉnh.

Ví dụ có n = 5 đỉnh, và có m = 4 cặp cạnh sau:

1 2

1 3

1 4

3 5

b. Dữ liệu ma trận kề được xây dựng

2. Nhập dữ liệu vào ma trận kề bằng c++

Các bạn có thể tham khảo thêm về việc dùng ma trận kề trong BFS và DFS tại đây:
Thuật toán tìm kiếm theo chiều sâu DFS Thuật toán tìm kiếm theo chiều rộng BFS
3. Ma trận kề có trọng số và có hướng
Bên trên chúng ta nói về đồ thị không trọng số, và vô hướng. Vậy nếu đồ thị có trọng số, hay có hướng thì sao?
4. Ưu điểm và nhược điểm khi dùng ma trận kề trong lý thuyết đồ thị

Dễ dàng nhận thấy vì sử dụng mảng 2 chiều nên kích thước dữ liệu chúng ta tốn n^2 và độ phức tạp của dữ liệu này cũng là O(n^2).

Nhưng ma trận kề trong lý thuyết đồ thị cũng có ưu điểm là khi nhìn vào dữ liệu được tổ chức bằng ma trận kề, thì dễ dàng nhận biết được 2 đỉnh nào kề với nhau, chúng ta dễ cài đặt, và biết được bậc của từng đỉnh nếu đó là đồ thị đơn.

# data[].attributes.attachment_link.title
Bài 1: Ma trận kề C++/Pascal Lý thuyết đồ thị - Kiến Thức 24h

# data[].attributes.attachment_link.description
Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC. Liên hệ ngay: 035.870.8844 Trong lý thuyết đồ thị, việc tổ chức dữ liệu cho từng bài toán, thuật toán rất quan trọng, nó quyết định kích thước dữ liệu bài toán, thời gian thực tế của bài toán.

# data[].attributes.body
SGK CHUYÊN TIN 2

# data[].attributes.attachment_link.title
[downloadsachmienphi.com] Tài Liệu Giáo Khoa Chuyên Tin Quyển 2 - Hồ Sĩ Đàm

# data[].attributes.body
SGK CHUYÊN TIN 1

# data[].attributes.attachment_link.title
[downloadsachmienphi.com] Tài Liệu Giáo Khoa Chuyên Tin Quyển 1 - Hồ Sĩ Đàm

# data[].attributes.body
Bài kiểm tra 15p

# data[].attributes.body
QHĐ CẤU HÌNH
QHĐ TRÊN CÂY

# data[].attributes.body
QHĐ

# data[].attributes.attachment_link.title
Một số bài toán quy hoạch động điển hình

# data[].attributes.attachment_link.description
Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của $n$ khách hàng. Khách hàng $i$ muốn sử dụng máy trong khoảng thời gian từ $a_i$ đến $b_i$ và trả tiền thuê là $c_i$.

# data[].attributes.body
Trang 99-->109

# data[].attributes.body
QUY HOẠCH ĐỘNG NÂNG  CAO

# data[].attributes.body
Thực hành

# data[].attributes.attachment_link.description
Đầu tiên, ta bắt đầu từ trạng thái 0, chúng ta có $f[0] = 0$. Xét đến tổng 1. Có duy nhất đồng xu 1 nhỏ hơn hoặc bằng tổng 1, nên ta có $f[1] = f[1-V_0] + 1 = f[0] + 1 = 1$. Xét đến tổng 2.

# data[].attributes.body
cây

# data[].attributes.attachment_link.title
[Cây Nhị Phân Tìm Kiếm] Bài 2. Khai báo-khởi tạo-Duyệt NLR cây nhị phân(cây nhị phân tìm kiếm)

# data[].attributes.attachment_link.title
[Cây Nhị Phân Tìm Kiếm] Bài 1. Tổng quan về cây nhị phân - cây nhị phân tìm kiếm

# data[].attributes.body
CÂY NHỊ PHÂN

# data[].attributes.attachment_link.title
Cấu trúc dữ liệu & giải thuật - Chương 3 - Bài 2 - Cây AVL

# data[].attributes.attachment_link.readable_text
Cấu trúc dữ liệu cây là gì ?

Cấu trúc dữ liệu cây biểu diễn các nút (node) được kết nối bởi các cạnh. Chúng ta sẽ tìm hiểu về Cây nhị phân (Binary Tree) và Cây tìm kiếm nhị phân (Binary Search Tree) trong phần này.

Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Một cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con. Một cây nhị phân tận dụng lợi thế của hai kiểu cấu trúc dữ liệu: một mảng đã sắp thứ tự và một danh sách liên kết (Linked List), do đó việc tìm kiếm sẽ nhanh như trong mảng đã sắp thứ tự và các thao tác chèn và xóa cũng sẽ nhanh bằng trong Linked List.

Các khái niệm cơ bản về cây nhị phân

Dưới đây là một số khái niệm quan trọng liên quan tới cây nhị phân:

Đường: là một dãy các nút cùng với các cạnh của một cây.

Nút gốc (Root): nút trên cùng của cây được gọi là nút gốc. Một cây sẽ chỉ có một nút gốc và một đường xuất phát từ nút gốc tới bất kỳ nút nào khác. Nút gốc là nút duy nhất không có bất kỳ nút cha nào.

Nút cha: bất kỳ nút nào ngoại trừ nút gốc mà có một cạnh hướng lên một nút khác thì được gọi là nút cha.

Nút con: nút ở dưới một nút đã cho được kết nối bởi cạnh dưới của nó được gọi là nút con của nút đó.

Nút lá: nút mà không có bất kỳ nút con nào thì được gọi là nút lá.

Cây con: cây con biểu diễn các con của một nút.

Truy cập: kiểm tra giá trị của một nút khi điều khiển là đang trên một nút đó.

Duyệt: duyệt qua các nút theo một thứ tự nào đó.

Bậc: bậc của một nút biểu diễn số con của một nút. Nếu nút gốc có bậc là 0, thì nút con tiếp theo sẽ có bậc là 1, và nút cháu của nó sẽ có bậc là 2, ...

Khóa (Key): biểu diễn một giá trị của một nút dựa trên những gì mà một thao tác tìm kiếm thực hiện trên nút.

Biểu diễn cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân biểu diễn một hành vi đặc biệt. Con bên trái của một nút phải có giá trị nhỏ hơn giá trị của nút cha (của nút con này) và con bên phải của nút phải có giá trị lớn hơn giá trị của nút cha (của nút con này). Hình minh họa:

Chúng ta đang triển khai cây bởi sử dụng đối tượng nút và kết nối chúng thông qua các tham chiếu.

Nút (Node) trong cây tìm kiếm nhị phân

Một nút sẽ có cấu trúc như dưới đây. Nút có phần dữ liệu và phần tham chiếu tới các nút con bên trái và nút con bên phải.

struct node {
   int data;
   struct node *leftChild;
   struct node *rightChild;
};

Trong một cây, tất cả các nút chia sẻ cùng một cấu trúc.

Hoạt động cơ bản trên cây tìm kiếm nhị phân

Dưới đây liệt kê các hoạt động cơ bản có thể được thực hiện trên cấu trúc dữ liệu cây tìm kiếm nhị phân:

Chèn: chèn một phần tử vào trong một cây/ tạo một cây.

Tìm kiếm: tìm kiếm một phần tử trong một cây.

Duyệt tiền thứ tự: duyệt một cây theo cách thức duyệt tiền thứ tự (tham khảo chương sau).

Duyệt trung thứ tự: duyệt một cây theo cách thức duyệt trung thứ tự (tham khảo chương sau).

Duyệt hậu thứ tự: duyệt một cây theo cách thức duyệt hậu thứ tự (tham khảo chương sau).

Trong chương này, chúng ta sẽ tìm hiểu chi tiết cách tạo (chèn) cấu trúc cây và cách tìm kiếm một phần tử dữ liệu trên một cây. Chương sau chúng ta sẽ tìm hiểu chi tiết về các cách duyệt cây.

Hoạt động chèn trong cây tìm kiếm nhị phân

Bước chèn đầu tiên sẽ tạo thành cây. Tiếp đó là sẽ chèn từng phần tử vào trong cây. Đầu tiên chúng ta cần xác định vị trí chính xác của nó. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa, thì tìm kiếm vị trí rỗng trong cây con bên trái và chèn dữ liệu. Nếu không nhỏ hơn, tìm vị trí rỗng trong cây con bên phải và chèn dữ liệu. (Nếu bạn chưa hiểu, bạn có thể đọc lại phần Biểu diễn cây tìm kiếm nhị phân ở trên để biết tại sao lại chèn như vậy và xem hình minh họa)

Giải thuật cho hoạt động chèn

If root là NULL
   thì tạo nút gốc (root node)
return

If root đã tồn tại thì sau đó
   so sánh dữ liệu với node.data

   while tới vị trí chèn đã xác định

      If dữ liệu là lớn hơn node.data
         tới cây con bên phải
      else
         tới cây con bên trái

   kết thúc while

   chèn dữ liệu

Kết thúc If

Giải thuật mẫu cho hoạt động chèn

Từ trên ta có thể suy ra giải thuật mẫu cho hoạt động chèn trong cây tìm kiếm nhị phân như sau:

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //Nếu cây là trống, chúng ta tạo root node
   if(root == NULL) {
      root = tempNode;
   }else {
      current = root;
      parent  = NULL;

      while(1) {
         parent = current;

         //tới cây con bên trái
         if(data < parent->data) {
            current = current->leftChild;

            //chèn dữ liệu vào bên trái
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }

         //tới cây con bên phải
         else {
            current = current->rightChild;

            //chèn dữ liệu vào bên phải
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }
   }
}

Để tìm hiểu code đầy đủ của cấu trúc dữ liệu cây trong ngôn ngữ C, mời bạn click chuột vào chương: Duyệt cây trong C.

Hoạt động tìm kiếm trong cây nhị phân

Mỗi khi một phần tử cần tìm kiếm: bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa, thì tìm kiếm phần tử trong cây con bên trái; nếu không nhỏ hơn thì tìm kiếm phần tử trong cây con bên phải. (Nếu bạn chưa hiểu, bạn có thể đọc lại phần Biểu diễn cây tìm kiếm nhị phân ở trên để biết tại sao lại tìm kiếm như vậy và xem hình minh họa)

Giải thuật cho hoạt động tìm kiếm

If root.data là bằng với search.data
   return root
else
   while không tìm thấy dữ liệu

      If data là lớn hơn node.data
         tới cây con bên phải
      else
         tới cây con bên trái

      If data được tìm thấy
         return node

   kết thúc while

   return không tìm thấy data

Kết thúc if

Giải thuật mẫu cho hoạt động tìm kiếm

Từ trên ta có thể suy ra giải thuật mẫu cho hoạt động tìm kiếm trong cây tìm kiếm nhị phân như sau:

struct node* search(int data) {
   struct node *current = root;
   printf("Truy cap phan tu: ");

   while(current->data != data) {
      if(current != NULL)
      printf("%d ",current->data);

      //tới cây con bên trái

      if(current->data > data) {
         current = current->leftChild;
      }
      //else  tới cây con bên phải
      else {
         current = current->rightChild;
      }

      //không tìm thấy
      if(current == NULL) {
         return NULL;
      }

      return current;
   }
}

Để tìm hiểu code đầy đủ của cấu trúc dữ liệu cây trong ngôn ngữ C, mời bạn click chuột vào chương: Duyệt cây trong C.
Bài học Cấu trúc dữ liệu và giải thuật phổ biến tại vietjack.com:

# data[].attributes.attachment_link.description
Cấu trúc dữ liệu cây - Học Cấu trúc dữ liệu & giải thuật với ngôn ngữ C, C++ và Java theo các bước cơ bản tới nâng cao bắt đầu từ Giải thuật, Cấu trúc dữ liệu, Mảng, Danh sách liên kết, Danh sách liên kết đôi, Danh sách

# data[].attributes.body
TIẾT 1,2 -CHIỀU 20/3/19 (NHÓM 3,4)

# data[].attributes.body
TIẾT 2,3 - SÁNG 15/3/19 (NHÓM 1,2)

# data[].attributes.body
CẤU TRÚC DỮ LIỆU NÂNG CAO
Mô Hình Cây Trong Tổ Chức Dữ Liệu

# data[].attributes.body
ÔN TẬP+ KT 1 TIẾT

# data[].attributes.body
TÌM CẶP ĐIỂM GẦN NHẤT

# data[].attributes.body
PHÂN PHỐI CHƯƠNG TRÌNH

# data[].attributes.body
HỌC KỲ 2

# data[].attributes.body
MA TRẬN ĐỀ KIỂM TRA KỲ 2

# data[].attributes.body
TIẾT 2,3-SÁNG 30/1/19 (NHÓM 4,3)
TIẾT 1,2-CHIỀU 30/1/19 (NHÓM 2,1)

# data[].attributes.body
TIẾT 2,3-SÁNG 20/2/19 (NHÓM 1,2)
TIẾT 1,2-CHIỀU 20/2/19 (NHÓM 3,4)

# data[].attributes.body
ĐIỂM NẰM TRONG ĐA GIÁC

# data[].attributes.body
LỊCH KT CHUNG KỲ 2

# data[].attributes.attachment_link.title
LICH KIEM TRA CHUNG HOC KY 2 NAM HOC 2018-2019

# data[].attributes.body
CHUYÊN TIN 3

# data[].attributes.body
CHIA ĐỂ TRỊ

# data[].attributes.body
BÀI TẬP BÀI TOÁN LẬP LỊCH

# data[].attributes.body
SGK Chuyên Tin 1 Trang 86-->90

# data[].attributes.body
Chuyên đề: GIỚI THIỆU BÀI TOÁN LẬP LỊCH

# data[].attributes.body
BÀI TẬP

# data[].attributes.body
KT 15 PHÚT (THUẬT TOÁN DIJKSTRA)

# data[].attributes.attachment_link.title
TÌM ĐƯỜNG ĐI NGẮN NHẤT TỪ ĐỈNH ĐẦU ĐẾN ĐỈNH CUỐI THEO THUẬT TOÁN DIJKSTRA

# data[].attributes.attachment_link.title
Thuật toán Dijkstra | Hướng dẫn giải tay | Carry by Bắp

# data[].attributes.body
Infographic

# data[].attributes.body
Thuật Toán Dijkstra

# data[].attributes.body
KIỂM TRA 1 TIẾT

# data[].attributes.headline
Lập bảng tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại trong đồ thị

# data[].attributes.subject
Lập bảng tìm đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại trong đồ thị

# data[].attributes.body
Theo thuật toán Floyd

# data[].attributes.body
Thuật Toán FLOYD

# data[].attributes.body
Duyệt đường đi ngắn nhất trong đồ thị có trọng số

# data[].attributes.body
DEADLINE

# data[].attributes.body
Deadline: 23 giờ (31/8/18)

# data[].attributes.body
VD về BFS và DFS

# data[].attributes.body
Deadline: 23 giờ (ngày 10/9/18)
* Nộp theo tổ (VD: BTTUAN3-TO1.rar)
* Trễ hạn 1 giờ trừ 2 điểm

# data[].attributes.body
https://www.youtube.com/watch?v=e-Q3D4_YyjU

# data[].attributes.attachment_link.title
(28) Depth-first search - Tìm kiếm theo chiều sâu trên đồ thị - Bùi Thế Tâm

# data[].attributes.body
https://www.youtube.com/watch?v=5AN55O8cF8E

# data[].attributes.attachment_link.title
Depth First Search - Thuật toán tìm kiếm theo chiều sâu

# data[].attributes.body
http://topvn.esy.es/thuat-toan/thuat-toan-dfs/

# data[].attributes.attachment_link.readable_text
Tìm kiếm theo chiều sâu (DFS) là thuật toán duyệt hoặc tìm kiếm trên một cây, một thư mục. Việc thực hiện thuật toán được bắt đầu bằng 1 điểm gốc và phát triển xa nhất có thể theo mỗi nhánh. Quá trình tìm kiếm được mô tả như sau: xuất phát từ 1 đỉnh phát triển tới đỉnh cần tìm ( thỏa mãn điều kiện) ở lân cận, phát triển tiếp với đỉnh lân cận đầu tiên tìm được hoặc quay lại khi gặp nhánh cụt để phát triển theo đỉnh lân cận thỏa mãn điều kiện khác.

VD: Có đồ thị sau: Đỉnh xuất phát (1) liệt kê tất cả các nhánh của đồ thị.

Xuất phát từ đỉnh (1) việc duyệt sẽ thực hiện như sau: Từ đỉnh (1) giả sử việc tìm đỉnh lân cận bắt gặp đỉnh đầu tiên là (2) nên thực hiện việc tìm đỉnh lân cận của (2) => (6) do (6) ko có đỉnh lân cận => quay lại (2) => (3) => (4) => quay lại (3) => (5) => quay lại (3) => quay lại (2) => quay lại (1) => (7) => quay lại (1) =>(8) =>(12) => quay lại (8) => (9) => (10) => quay lại (9) => (11) =>quay lại (9) => quay lại (8) => quay lại (1) => Kết thúc.

*** Cách thực hiện thuật toán DFS trong code

++) Sử dụng Đệ quy : >> Tìm hiểu về đệ quy <<

void DFS(int i){

System.out.print(i+" ");

if( j = điều kiện ) // với j là lân cận của i

DFS(j);

}

++) Sử dụng Stack

Stack ( Ngăn xếp) có cơ chế dữ liệu LIFO (Last In - First Out: vào sau ra trước).

Việc thực hiện DFS được làm bằng khởi tạo stack và ném đỉnh xuất phát vào stack ( push()).

Stack mStack=new Stack();

mStack.push(A) // với A là đỉnh xuất phát.

while(!mStack.isEmpty()){ // thực hiện cho đến khi stack rỗng.

x=mStack.pop(); // Lấy đỉnh trong stack ra.

if(y = điều kiện) // y là đỉnh lân cận với đỉnh vừa lấy

mStack.push(y); // nếu y thỏa mãn điều kiện thì ném y vào stack

}

note: Mọi thắc mắc vui lòng để lại comment bên dưới để được giải đáp.

Bài viết tiếp : Bài tập ví dụ dùng DFS.

# data[].attributes.attachment_link.title
[Thuật toán] DFS - Depth-first search - Tìm kiếm theo chiều sâu

# data[].attributes.attachment_link.description
Tìm kiếm theo chiều sâu (DFS) là thuật toán duyệt hoặc tìm kiếm trên một cây, một thư mục. Việc thực hiện thuật toán được bắt đầu bằng 1 điểm gốc và phát triển xa nhất có thể theo mỗi nhánh.

# data[].attributes.body
BFS

# data[].attributes.body
https://www.youtube.com/watch?v=19n9PkMzGZc

# data[].attributes.body
https://drive.google.com/open?id=0B8pTD6hbd2SKWlVTRDhfV2c5UjUyREdUeWNrMzBXMFliWm5V

# data[].attributes.body
1 Số câu hỏi+ Bài tập

# data[].attributes.body
Năm học 2018-2019