Đề cương môn Công nghệ thông tin - Trường Đại học lao động -  xã hội.

ĐỒ ÁN CÔNG NGHỆ THÔNG TIN ĐỒ THỊ
GVHD : THS Nguyễn Quang Ngọc NHÓM 01 SVTH: Nguyễn Huy MSSV: 21110187 SVTH: Lê Việt Khánh MSSV: 21110206 LỚP: 21110CL6
Họ và tên Sinh viên : Nguyễn Huy........................MSSV: 21110187.........................
Lê Việt Khánh....................MSSV: 21110206.........................
Ngành: Công nghệ Thông tin
Tên đề tài: Đồ thị.........................................................................................................
Họ và tên Giáo viên hướng dẫn: ThS Nguyễn Quang Ngọc........................................ Nhận xét
1. Về nội dung đề tài & khối lượng thực hiện:
.....................................................................................................................................
.....................................................................................................................................
.....................................................................................................................................
..................................................................................................................................... 2. Ưu điểm
.....................................................................................................................................
.....................................................................................................................................
.....................................................................................................................................
..................................................................................................................................... 3. Khuyết điểm
.....................................................................................................................................
.....................................................................................................................................
.....................................................................................................................................
..................................................................................................................................... 4. Đánh giá loại:
5. Điểm:.......................................................................................................................
Tp.Hồ Chí Minh, ngày tháng 11 năm 2023 Giáo viên hướng dẫn
(Ký & ghi rõ họ tên) 2 Mục lục
Phần I: Mở đầu .............................................................................................................. 4
1. Lý do chọn đề tài .................................................................................................... 4
2. Mục đích của đề tài, đối tượng và phạm vi nghiên cứu ...................................... 4
3. Kết quả dự kiến đạt được ...................................................................................... 4
4. Bảng phân công nhiệm vụ ..................................................................................... 5
Phần II: Thiết kế ............................................................................................................ 6
1. Biểu diễn đồ thị ...................................................................................................... 6
2. Một ứng dụng của đồ thị ..................................................................................... 17
Phần III: Tổng kết ....................................................................................................... 23
1. Đánh giá Sinh viên ............................................................................................... 23
2. Khó khăn .............................................................................................................. 23
3. Ưu điểm ................................................................................................................. 23
4. Nhược điểm........................................................................................................... 23
5. Ý tưởng phát triển................................................................................................ 23 3 Phần I: Mở đầu
1. Lý do chọn đề tài
Hiện nay, ứng dụng của đồ thị được sử dụng rộng rãi trong nhiều ứng dụng công nghệ
thông tin như lập trình trò chơi cờ ca rô, hoặc tìm đường đi trên bản đồ do nhu cầu của
người dùng. Áp dụng kiến thức về đồ thị vào các ứng dụng thực tế có thể tạo ra những
ứng dụng có giá trị trong cuộc sống.
Lý thuyết đồ thị đóng vai trò quan trọng, làm cơ sở toán cho tin học. Việc lựa chọn đề
tài Đồ Thị nhằm mục đích nghiên cứu chuyên sâu các kiến thức trong đồ thị, qua đó
áp dụng các kiến thức liên quan đến lý thuyết đồ thị, cấu trúc dữ liệu và giải thuật để
lập trình ra các ứng dụng có thể giải quyết vấn đề trong đồ thị.
2. Mục đích của đề tài, đối tượng và phạm vi nghiên cứu
Mục đích của đề tài đồ thị là áp dụng kiến thức về lý thuyết đồ thị, cấu trúc dữ liệu và
giải thuật để lập trình một ứng dụng giúp giải quyết các vấn đề liên quan đến đồ thị bằng C++.
Đối tượng của đề tài là một ứng dụng được lập trình bởi một nhóm gồm 2 sinh viên.
Mục đích chính của ứng dụng là áp dụng các kiến thức đồ thị để tìm đường đi ngắn nhất ra khỏi mê cung.
Phạm vi nghiên cứu bao gồm sử dụng nhiều nguồn thông tin trên Google, YouTube và
các giáo trình để tìm hiểu về lý thuyết đồ thị, từ cơ bản đến chuyên sâu. Qua đó, Áp
dụng cá kiến thức từ các môn học và các kiến thức liên quan để phát triển ứng dụng để
giải quyết các vấn đề cụ thể liên quan đến đồ thị trong lập trình C++.
3. Kết quả dự kiến đạt được
Nắm được các kiến thức về lý thuyết đồ thị, cấu trúc dữ liệu và giải thuật, áp dụng
hiệu quả các kiến thức đồ thị kết hợp với ngôn ngữ lập trình C++ để tạo ra ứng dụng
đồ thị cơ bản và nâng cao. 4
4. Bảng phân công nhiệm vụ 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 100% đồ thị đã có 3 Lê Việt Khánh Thêm cạnh vào đồ 100% thị 4 Nguyễn Huy Xuất các tên đỉnh, 100% tên cạnh 5 Lê Việt Khánh Xuất ma trận kề 100% 6 Nguyễn Huy Duyệt đồ thị theo 100% chiều rộng 7 Nguyễn Huy Duyệt đồ thị theo 100% chiều sâu 8 Lê Việt Khánh Đường đi ngắn nhất 100%
từ đỉnh v đến đỉnh w 9 Lê Việt Khánh Kiểm tra có chu trình 100% Euler 10 Nguyễn Huy Tạo mê cung 100% 11 Lê Việt Khánh Tìm đường ra khỏi 100% mê cung 12 Nguyễn Huy Viết báo cáo 50% Lê Việt Khánh 50%
Bảng phân chia công việc 1 5
Phần II: Thiết kế
1. Biểu diễn đồ thị
Các thư viện được sử dụng: Thứ tự Tên thư viện Mục đích 1
Đượ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). 2
Đượ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. 3
Đượ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. 4
Sử dụng để đặt giá trị vô cùng (infinity) cho việc
tính toán đường đi ngắn nhất trong thuật toán Dijkstra. 5
Sử dụng để biểu diễn dữ
liệu của đỉnh (vertex) trong đồ thị.. 6 và
Sử dụng để tạo số ngẫu 6 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 Bảng thư viện
Tạo một đồ thị // Cau truc dinh template struct Vertex { T data;
// Cac thong tin khac cua dinh (neu can) }; // Lap do thi template class Graph { private: unordered_map> vertices;
unordered_map> adjacencyMatrix; // Su dung ma tran ke 7
Thêm một đỉnh vào đồ thị đã có public: // Them dinh vào do thi
void addVertex(int id, T data) { Vertex newVertex; newVertex.data = data; vertices[id] = newVertex; }
Thêm cạnh vào đồ thị với trọng số
void addEdge(int v, int w, int weight) {
adjacencyMatrix[v][w] = weight;
adjacencyMatrix[w][v] = weight; // Do thi vo huong }
void changeVertexData(int id, T newData) { vertices[id].data = newData; }
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; } } 8 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; } }
Nhập các thông tin đỉnh và cạnh trong hàm main Graph graph; graph.addVertex(1, "A"); graph.addVertex(2, "B"); graph.addVertex(3, "C"); graph.addVertex(4, "D"); cout << endl; graph.addEdge(1, 2, 1); graph.addEdge(1, 3, 2); graph.addEdge(2, 4, 3); graph.addEdge(3, 4, 2); cout << endl; graph.displayVertices();
graph.displayAdjacencyMatrix(); 9
Xuất kết quả thông tin các đỉnh và ma trận kề: 10
Biểu diễn đồ thị bằng hình ảnh: 11
Duyệt đồ thị theo chiều rộng: void BFS(int start) { unordered_map visited; queue queue; visited[start] = true; queue.push(start);
cout << "Duyet BFS tu dinh " << start << ": "; while (!queue.empty()) { int current = queue.front();
cout << current << " "; queue.pop();
for (const auto& neighbor : adjacencyMatrix[current]) {
if (!visited[neighbor.first]) {
visited[neighbor.first] = true; queue.push(neighbor.first); } } } cout << endl; } 12
Duyệt đồ thị theo chiều sâu: void DFS(int start) { unordered_map visited; stack stack;
cout << "Duyet DFS tu dinh " << start << ": "; stack.push(start); visited[start] = true; while (!stack.empty()) { int current = stack.top(); stack.pop();
cout << current << " ";
for (const auto& neighbor : adjacencyMatrix[current]) { int vertex = neighbor.first; if (!visited[vertex]) { stack.push(vertex); visited[vertex] = true; } } } cout << endl; } 13
Cho đồ thị duyệt từ đỉnh 1, ta có kết quả duyệt đồ thị theo chiều rộng và chiều sâu
Biểu diễn bằng hình ảnh 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 distance;
priority_queue, deque>, greater>> pq;
for (const auto& vertex : vertices) {
distance[vertex.first] = numeric_limits::max(); } distance[v] = 0; pq.push({0, v}); while (!pq.empty()) { int u = pq.top().second; pq.pop();
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;
pq.push({distance[vertex], vertex}); } } }
cout << "Duong di ngan nhat tu dinh " << v << " den dinh " << w << " la: " << distance[w] << endl; } 15
Cho đồ thị đi từ đỉnh 1 đến đỉnh 4, ta có kết quả của tìm đường đi ngắn nhất, sử dụng thuật toán Dijkstra là:
Kiểm tra có chu trình Euler bool hasEulerCycle() {
for (const auto& adjacency : adjacencyMatrix) {
if (adjacency.second.size() % 2 != 0) { return false; } } return true; } bool hasEdge(int v, int w) {
return adjacencyMatrix[v].find(w) != adjacencyMatrix[v].end(); }
Kết quả của kiểm tra chu trình Euler 16
2. Một ứng dụng của đồ thị Tạo mê cung void createMaze(int start) { unordered_map visited; stack stack;
int visitedVertices[100] = {0}; // So luong dinh toi da (sua doi tuy theo yeu cau) visited[start] = true; stack.push(start); int index = 0;
visitedVertices[index++] = start; while (!stack.empty()) { int current = stack.top(); stack.pop();
unordered_map unvisitedNeighbors;
for (const auto& neighbor : adjacencyMatrix[current]) {
if (!visited[neighbor.first]) {
unvisitedNeighbors[neighbor.first] = true; } }
if (!unvisitedNeighbors.empty()) {
int* unvisitedArr = new int[unvisitedNeighbors.size()]; int count = 0;
for (const auto& unvisited : unvisitedNeighbors) {
unvisitedArr[count++] = unvisited.first; } 17
int randomNeighbor = unvisitedArr[rand() % count]; delete[] unvisitedArr; stack.push(current);
addEdge(current, randomNeighbor, 1);
visited[randomNeighbor] = true; stack.push(randomNeighbor);
visitedVertices[index++] = randomNeighbor; } }
cout << "Me cung duoc tao tu dinh " << start << ":" << endl;
for (int i = 0; i < index; ++i) {
cout << visitedVertices[i] << " "; } cout << endl; } Các bước:
+ Khởi tạo stack (stack stack) để theo dõi quá trình duyệt đồ thị theo chiều sâu.
+ Khởi tạo mảng visitedVertices để lưu trữ các đỉnh đã được thăm theo thứ tự.
+ Bắt đầu từ đỉnh start, đánh dấu nó là đã thăm và thêm vào stack.
+ Vòng lặp chạy cho đến khi stack rỗng.
+ Lấy đỉnh trên cùng của stack (int current = stack.top(); stack.pop();).
+ Tìm tất cả các đỉnh kề chưa được thăm (unvisitedNeighbors).
+ Nếu có đỉnh kề chưa được thăm:
- Chọn một đỉnh kề ngẫu nhiên (randomNeighbor).
- Thêm cạnh giữa current và randomNeighbor với trọng số 1.
- Đánh dấu randomNeighbor là đã thăm và thêm vào stack.
+ Lưu trữ đỉnh current vào mảng visitedVertices. 18
+ In ra đỉnh đã tạo được mê cung từ đỉnh start. Chi tiết
unordered_map visited;: Đánh dấu đỉnh đã được duyệt
stack stack;: Sử dụng stack để theo dõi các đỉnh
int visitedVertices[100] = {0};: Mảng lưu trữ đỉnh đã được duyệt (sửa đổi tùy theo yêu cầu)
int index = 0;: Biến index theo dõi vị trí trong mảng visitedVertices
visitedVertices[index++] = start;: Lưu đỉnh xuất phát vào mảng visitedVertices
int current = stack.top();: Lấy đỉnh đầu tiên từ stack
addEdge(current, randomNeighbor, 1);: Thêm cạnh giữa đỉnh hiện tại và đỉnh kề chọn
visited[randomNeighbor] = true;: Đánh dấu đỉnh kề đã được duyệt
stack.push(randomNeighbor);: Đẩy đỉnh kề vào stack để xử lý tiếp
visitedVertices[index++] = randomNeighbor;: Lưu đỉnh kề vào mảng visitedVertices
+ Sử dụng một stack để theo dõi các đỉnh và một mảng visited để đánh dấu các đỉnh đã được thăm.
+ unvisitedNeighbors: Là một danh sách các đỉnh kề chưa được duyệt của đỉnh hiện tại.
+ Trong quá trình lặp, mỗi lần chọn một đỉnh ngẫu nhiên từ danh sách các đỉnh kề
chưa được duyệt và thêm cạnh giữa đỉnh hiện tại và đỉnh đã chọn.
+ Lặp lại quá trình này cho đến khi không còn đỉnh kề nào chưa được duyệt.
+ Mỗi lần lặp, một đỉnh kề chưa được duyệt được chọn ngẫu nhiên và kết nối với đỉnh hiện tại.
+ Quá trình lặp tiếp tục cho đến khi không còn đỉnh kề nào chưa được duyệt.
+ Mê cung cuối cùng được biểu diễn thông qua các cạnh được thêm vào đồ thị.
+ Mảng visitedVertices lưu trữ thứ tự các đỉnh đã được thăm, và kết quả cuối cùng sẽ
được xuất ra màn hình. 19
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 visited; stack stack;
int path[100] = {0}; // So luong dinh toi da (sua doi tuy theo yeu cau) int index = 0; stack.push(v); while (!stack.empty()) { int current = stack.top(); stack.pop(); path[index++] = current; if (current == w) {
cout << "Duong di tu dinh " << v << " den dinh " << w << ":" << endl;
for (int i = 0; i < index; ++i) {
cout << path[i] << " "; } cout << endl; return; } visited[current] = true;
for (const auto& neighbor : adjacencyMatrix[current]) {
if (!visited[neighbor.first]) { stack.push(neighbor.first); 20