<span class="text_page_counter">Trang 1</span><div class="page_container" data-page="1">

<b>BỘ GIÁO DỤC VÀ ĐÀO TẠO </b>

<b>TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TPHCM KHOA ĐÀO TẠO CHẤT LƯỢNG CAO </b>

<b>ĐỒ ÁN CÔNG NGHỆ THÔNG TIN </b>

</div><span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

2

<b>Tổng quan </b>

Chúng em muốn gửi lời cảm ơn chân thành đến thầy Nguyễn Quang Ngọc, người phụ trách dự án, đã hướng dẫn chúng em thực hiện đồ án. Thầy đã đưa ra những gợi ý và hướng dẫn quý báu để giúp chúng em hiểu được những vấn đề phức tạp liên quan đến đồ án bên cạnh việc trình bày một cách hiệu quả. Đồ án của chúng em đã hoàn thành nhờ sự hướng dẫn của thầy.

Đồ án này được thực hiện trong vòng mười bốn tuần, vừa đủ để hồn thành nó. Tuy nhiên, do thời gian chúng em thực hiện mỗi tuần không tối ưu nên đồ án sẽ mắc nhiều sai sót là điều khó tránh khỏi. Chúng em rất mong nhận được mọi ý kiến đóng góp của thầy để giúp kiến thức còn hạn chế của chúng em được tốt hơn.

Chúng em xin cảm ơn

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

3

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

5

<b>Mục lục bảng </b>

Bảng phân chia công việc ...

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

6

<b>I. Đặc tả </b>

<b>Định nghĩa </b>

Trong toán học và tin học, lý thuyết đồ thị nghiên cứu các tính chất của đồ thị. Một cách khơng chính thức, đồ thị là một tập các đối tượng được gọi là các đỉnh (hoặc nút) nối với nhau bởi các cạnh (hoặc cung). Cạnh có thể có hướng hoặc vơ hướng. Đồ thị thường được vẽ dưới dạng một tập các điểm (các đỉnh nối với nhau bằng các đoạn thẳng (các cạnh).

Đồ thị G là một bộ (V, E), với V là tập khác ∅, hữu hạn các phần tử được gọi là các đỉnh, E là tập các phần tử được gọi là các cạnh. Mỗi phần tử e E liên kết với duy nhất ∈

một cặp đỉnh v, w V và được ký hiệu e = (v,∈ w), v, w ∈ V.

e = (v, w) được gọi là cạnh kề của hai đỉnh v và w. v và w là các đỉnh kề nhau (v kề với w). e1 = (v, w) và e2 = (v, w), e1 và e2 được gọi là 2 cạnh song song. - e = (v, v) được gọi là một khuyên hay vòng.

d(v), gọi là bậc của đỉnh v, là số cạnh kề với v. Nếu đỉnh v có vịng thì vịng được tính là 2.

Đỉnh có bậc bằng 0 được gọi là đỉnh cô lập. Đỉnh có bậc bằng 1 được gọi là đỉnh treo.

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

7

<b>II. Phân chia công việc </b>

Thứ tự Tên sinh viên _{Cơng việc} Đóng góp 1 _{Lê Việt Khánh} _{Tạo một đồ thị} 100% 2 Nguyễn Huy Thêm một đỉnh vào 5 Lê Việt Khánh Xuất ma trận kề 100% 6 Nguyễn Huy Duyệt đồ thị theo 10 Nguyễn Huy Tạo mê cung 100% 11 Lê Việt Khánh Tìm đường ra khỏi

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

8

<b>III. Thiết kế </b>

1. Biểu diễn đồ thị

Các thư viện:

<unordered_map>: Được sử dụng để lưu trữ thông tin về các đỉnh (vertices) của đồ thị và thông tin về các cạnh thơng qua cấu trúc dữ liệu khơng có thứ tự (unordered_map). <queue>: Được sử dụng để triển khai thuật toán duyệt đồ thị theo chiều rộng (BFS).

Queue được sử dụng để duyệt qua các đỉnh theo thứ tự FIFO.

<stack>: Được sử dụng để triển khai thuật toán duyệt đồ thị theo chiều sâu (DFS). Stack được sử dụng để duyệt qua các đỉnh theo thứ tự LIFO.

<limits>: Sử dụng để đặt giá trị vô cùng (infinity) cho việc tính tốn đường đi ngắn nhất trong thuật toán Dijkstra.

<string>: Sử dụng để biểu diễn dữ liệu của đỉnh (vertex) trong đồ thị. <cstdlib> và <ctime>: Sử dụng để tạo số ngẫu nhiên khi tạo mê cung trong hàm

createMaze. Hàm rand() được sử dụng để sinh số ngẫu nhiên, và srand() được sử dụng để khởi tạo seed cho generator số ngẫu nhiên.

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

unordered_map<int, Vertex<T>> vertices;

unordered_map<int, unordered_map<int, int>> adjacencyMatrix; // Su dung ma tran ke

Thêm một đỉnh vào đồ thị đã có public:

// Them dinh vào do thi void addVertex(int id, T data) {

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

Xuất các tên đỉnh, tên cạnh

// Xuat danh sach dinh void displayVertices() { cout << "Ten dinh:" << endl; for (const auto& vertex : vertices) {

cout << "Dinh " << vertex.first << ": " << vertex.second.data << endl; }

}

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

11 Xuất ma trận kề

void displayAdjacencyMatrix() { cout << "Ma tran ke:" << endl; for (const auto& row : adjacencyMatrix) { cout << "Tu dinh " << row.first << ": "; for (const auto& neighbor : row.second) {

cout << neighbor.first << "(" << neighbor.second << ") "; }

cout << endl; }

}

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

12 Duyệt đồ thị theo chiều rộng:

void BFS(int start) {

unordered_map<int, bool> visited;

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

13

void DFS(int start) {

unordered_map<int, bool> visited;

for (const auto& neighbor : adjacencyMatrix[current]) { int vertex = neighbor.first;

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

14 Đường đi ngắn nhất từ đỉnh v đến đỉnh w, sử dụng thuật toán Dijkstra

void Dijkstra(int v, int w) { unordered_map<int, int> distance;

priority_queue<pair<int, int>, deque<pair<int, int>>, greater<pair<int, int>>> pq;

for (const auto& vertex : vertices) {

for (const auto& neighbor : adjacencyMatrix[u]) { int vertex = neighbor.first;

int weight = neighbor.second;

if (distance[vertex] > distance[u] + weight) { distance[vertex] = distance[u] + weight;

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

bool hasEdge(int v, int w) {

return adjacencyMatrix[v].find(w) != adjacencyMatrix[v].end(); }

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

16

2. Một ứng dụng của đồ thị

Tạo mê cung

void createMaze(int start) { unordered_map<int, bool> visited;

unordered_map<int, bool> unvisitedNeighbors; for (const auto& neighbor : adjacencyMatrix[current]) {

</div><span class="text_page_counter">Trang 17</span><div class="page_container" data-page="17">

cout << "Me cung duoc tao tu dinh " << start << ":" << endl; for (int i = 0; i < index; ++i) {

cout << visitedVertices[i] << " "; }

cout << endl; }

</div><span class="text_page_counter">Trang 18</span><div class="page_container" data-page="18">

18 Tìm đường ra khỏi mê cung

// Tim duong ra khoi me cung tu v den w void findExitFromMaze(int v, int w) { unordered_map<int, bool> visited;

cout << "Duong di tu dinh " << v << " den dinh " << w << ":" << endl; for (int i = 0; i < index; ++i) {

</div><span class="text_page_counter">Trang 19</span><div class="page_container" data-page="19">

19

} }

if (stack.empty() && path[index - 1] != w) {

// Quay lai neu không tim thay neighbor va duong di chua tim duoc

</div><span class="text_page_counter">Trang 20</span><div class="page_container" data-page="20">

20

<b>IV. Tổng kết </b>

1. Sinh viên tự đánh giá

Hoàn thành các yêu cầu cơ bản. Code tưởng đối sạch.

GUI vẫn còn quá đơn giản. Cần bổ sung thêm nhiều chức năng.

5. Ý tưởng phát triển

Thêm các giao diện cho chương trìn

</div><span class="text_page_counter">Trang 21</span><div class="page_container" data-page="21">

21

</div><span class="text_page_counter">Trang 22</span><div class="page_container" data-page="22">

22

</div><span class="text_page_counter">Trang 23</span><div class="page_container" data-page="23">

23

</div><span class="text_page_counter">Trang 24</span><div class="page_container" data-page="24">

24

</div><span class="text_page_counter">Trang 25</span><div class="page_container" data-page="25">

25

</div><span class="text_page_counter">Trang 26</span><div class="page_container" data-page="26">

26

</div><span class="text_page_counter">Trang 27</span><div class="page_container" data-page="27">

27

</div><span class="text_page_counter">Trang 28</span><div class="page_container" data-page="28">

28

</div><span class="text_page_counter">Trang 29</span><div class="page_container" data-page="29">

29

</div><span class="text_page_counter">Trang 30</span><div class="page_container" data-page="30">

30

</div><span class="text_page_counter">Trang 31</span><div class="page_container" data-page="31">

31

</div><span class="text_page_counter">Trang 32</span><div class="page_container" data-page="32">

32

</div><span class="text_page_counter">Trang 33</span><div class="page_container" data-page="33">

33

</div>