// Chương trình tìm đường đi ngắn nhất bằng thuật toán Floyd - Warshall
#include <iostream>
#include <fstream>
using namespace std;
#define INF INT_MAX
void importFile(char *file_input_name, int **&Graph, int &vertexNumber);
void FloydWarshall(int **Graph, int vertexNumber, int **dist, int **next);
void main()
{
int vertexNumber; // Số đỉnh
int **Graph; // Ma trận trọng số
importFile("input.txt", Graph, vertexNumber); // Nhập vào ma trận
int startVer = 0; // Giả sử đỉnh bắt đầu là 0
int goalVer = vertexNumber-1; // Giả sử đỉnh kết thúc là n-1
// Khởi tạo các mảng
int **dist = new int*[vertexNumber]; // int **dist: mảng chứa các độ dài đường đi ngắn nhất
int **next = new int*[vertexNumber]; // int **next: mảng chứa các đỉnh tiếp theo trong đường đi
for(int i = 0; i < vertexNumber; ++i)
{
dist[i] = new int[vertexNumber];
next[i] = new int[vertexNumber];
}
// Tìm đường đi ngắn nhất
FloydWarshall(Graph, vertexNumber, dist, next);
// In đường đi ngắn nhất
cout << "Duong di ngan nhat tu " << startVer+1 << " den " << goalVer+1 << " co do dai " << dist[startVer][goalVer] << " la:" << endl;
int k = startVer;
cout << startVer+1;
do
{
k = next[k][goalVer];
cout << " -> " << k+1;
} while (k != goalVer);
// Xóa con trỏ sau khi sử dụng
for(int i = 0; i < vertexNumber; ++i)
{
delete []dist[i];
delete []next[i];
}
delete []dist;
delete []next;
}
/// THUẬT TOÁN FLOYD - WARSHALL ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT
void FloydWarshall(int **Graph, int vertexNumber, int **dist, int **next)
{
/* == BƯỚC 1 ==*/
/* KHỞI TẠO */
for (int i = 0; i < vertexNumber; ++i)
{
for(int j = 0; j < vertexNumber; ++j)
{
if(i == j)
dist[i][j] = 0;
else
{
// Lưu ý: Theo đúng tư tưởng thuật toán,
// các đỉnh i, j không có cạnh nối trong ma trận trọng số
// sẽ quy ước giá trị M[i][j] = INF.
// Tuy nhiên, để đơn giản,
// ta có thể coi như không có trường hợp
// cạnh có trọng số bằng 0 và quy ước giá trị M[i][j] = 0
// cho các đỉnh i, j không kề nhau.
if(Graph[i][j] != 0)
{
dist[i][j] = Graph[i][j];
next[i][j] = j;
}
else
{
dist[i][j] = INF;
next[i][j] = -1;
}
}
}
}
/* == BƯỚC 2 == */
// Với mọi k = 1, 2, ..., n
for(int k = 0; k < vertexNumber; ++k)
{
// Với mọi đỉnh i, j
for(int i = 0; i < vertexNumber; ++i)
{
for(int j = 0; j < vertexNumber; ++j)
{
if((dist[i][k] != INF && dist[k][j] != INF && k != j) && (dist[i][j] > dist[i][k] + dist[k][j]))
{
dist[i][j] = dist[i][k] + dist[k][j];
next[i][j] = k;
}
}
}
}
}
// Đọc một ma trận
void importFile(char *file_input_name, int **&Graph, int &vertexNumber)
{
ifstream inFile(file_input_name);
if (inFile.is_open())
{
inFile >> vertexNumber; // Đọc số lượng đỉnh
int **WeightMatrix = new int*[vertexNumber];
for (int t = 0; t < vertexNumber; t++)
{
WeightMatrix[t] = new int[vertexNumber];
}
for (int i = 0; i < vertexNumber; i++)
{
for (int j = 0; j < vertexNumber; j++)
{
inFile >> WeightMatrix[i][j];
}
}
Graph = WeightMatrix;
inFile.close();
}
else
cout << "Unable to open file";
}
Thứ Sáu, 15 tháng 11, 2013
Dijkstra
#include <fstream>
#include <iostream>
using namespace std;
#define INF INT_MAX
void importFile(char *file_input_name, int **&Graph, int &verNum);
void Dijkstra(int **Graph, int verNum, int starVer, int goalVer, int *&B, int *&L, int *&T);
void main()
{
// Nhập ma trận kề của đồ thị
int **Graph; // Ma trận trọng số (Weight Matrix)
int verNum; // Số lượng đỉnh (vertex number)
importFile("input.txt", Graph, verNum);
int startVer = 0; // Giả sử đỉnh bắt đầu là 0
int goalVer = verNum-1; // Giả sử đỉnh kết thúc là n-1
// Khởi tạo các mảng
int *T = new int[verNum]; // *T : Mảng đánh đấu xem đỉnh i có thuộc T hay không
int *B = new int[verNum]; // *B: mảng chứa các đỉnh trên đường đi
int *L = new int[verNum]; // *L: mảng chứa độ dài đường đi
// Dijkstra Algorithm
Dijkstra(Graph, verNum, startVer, goalVer, B, L, T);
// In đường đi ngắn nhất
cout << "Duong di ngan nhat tu " << startVer+1 << " den " << goalVer+1 << " co do dai " << L[goalVer] << " la:" << endl;
cout << goalVer << " <- ";
int i = goalVer;
while(B[i] != startVer)
{
cout << B[i] << " <- ";
i = B[i];
}
cout << startVer << endl;
// Xóa các con trỏ đã dùng
delete []B;
delete []L;
delete []T;
for (int i = 0; i < verNum; i++)
{
delete []Graph[i];
}
delete []Graph;
}
/// THUẬT TOÁN DIJKSTRA ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT
void Dijkstra(int **Graph, int verNum, int startVer, int goalVer, int *&B, int *&L, int *&T)
{
// Tìm đường đi ngắn nhất
/* == BƯỚC 1 ==*/
for (int i = 0; i < verNum; ++i)
{
T[i] = 1; // Gán T = V
L[i] = INF; // Gán L[i] = VOCUC với mọi đỉnh i
B[i] = -1; // Gán B[i] = -1 với mọi đỉnh i
}
L[startVer] = 0; // Gán L[s] = 0
/* == BƯỚC 2: Kiểm tra g có còn thuộc T hay không == */
while(T[goalVer] == 1)
{
/* == BƯỚC 3: Chọn đỉnh i thuộc T sao cho L[i] nhỏ nhất và gán T = T\{i} == */
int Lmin = INF; // Lưu giá trị L[i] nhỏ nhất
int iMin = INF; // Lưu chỉ số đỉnh có L[i] nhỏ nhất
// Duyệt qua tìm giá trị Lmin
for(int i = 0; i < verNum; ++i)
{
// Kiểm tra đỉnh i có thuộc T hay không và so sánh tìm giá trị L[i] nhỏ nhất
if(T[i] == 1 && L[i] < Lmin)
{
Lmin = L[i];
iMin = i;
}
}
T[iMin] = 0; // gán T = T\{i} với i=iMin có L[i]=Lmin nhỏ nhất tìm được
/* == BƯỚC 4: Với mọi j thuộc T và có cạnh nối đến i=iMin == */
for(int j = 0; j < verNum; ++j)
{
if((T[j] == 1 && Graph[iMin][j] != INF) && (L[j] == INF || L[j] > L[iMin] + Graph[iMin][j]))
{
L[j] = L[iMin] + Graph[iMin][j];
B[j] = iMin;
}
}
/*== BƯỚC 5: Quay lại bước 2 ==*/
}
/*== BƯỚC 6: Dừng thuật toán ==*/
}
// Đọc một ma trận
void importFile(char *file_input_name, int **&Graph, int &verNum)
{
ifstream inFile(file_input_name);
if (inFile.is_open())
{
inFile >> verNum; // Đọc số lượng đỉnh
int **WeightMatrix = new int*[verNum];
for (int t = 0; t < verNum; t++)
{
WeightMatrix[t] = new int[verNum];
}
for (int i = 0; i < verNum; i++)
{
for (int j = 0; j < verNum; j++)
{
int nWeight;
inFile >> nWeight;
if (nWeight == 0 && i != j)
{
nWeight = INF;
}
WeightMatrix[i][j] = nWeight;
}
}
Graph = WeightMatrix;
inFile.close();
}
else
cout << "Unable to open file";
}
#include <iostream>
using namespace std;
#define INF INT_MAX
void importFile(char *file_input_name, int **&Graph, int &verNum);
void Dijkstra(int **Graph, int verNum, int starVer, int goalVer, int *&B, int *&L, int *&T);
void main()
{
// Nhập ma trận kề của đồ thị
int **Graph; // Ma trận trọng số (Weight Matrix)
int verNum; // Số lượng đỉnh (vertex number)
importFile("input.txt", Graph, verNum);
int startVer = 0; // Giả sử đỉnh bắt đầu là 0
int goalVer = verNum-1; // Giả sử đỉnh kết thúc là n-1
// Khởi tạo các mảng
int *T = new int[verNum]; // *T : Mảng đánh đấu xem đỉnh i có thuộc T hay không
int *B = new int[verNum]; // *B: mảng chứa các đỉnh trên đường đi
int *L = new int[verNum]; // *L: mảng chứa độ dài đường đi
// Dijkstra Algorithm
Dijkstra(Graph, verNum, startVer, goalVer, B, L, T);
// In đường đi ngắn nhất
cout << "Duong di ngan nhat tu " << startVer+1 << " den " << goalVer+1 << " co do dai " << L[goalVer] << " la:" << endl;
cout << goalVer << " <- ";
int i = goalVer;
while(B[i] != startVer)
{
cout << B[i] << " <- ";
i = B[i];
}
cout << startVer << endl;
// Xóa các con trỏ đã dùng
delete []B;
delete []L;
delete []T;
for (int i = 0; i < verNum; i++)
{
delete []Graph[i];
}
delete []Graph;
}
/// THUẬT TOÁN DIJKSTRA ĐỂ TÌM ĐƯỜNG ĐI NGẮN NHẤT
void Dijkstra(int **Graph, int verNum, int startVer, int goalVer, int *&B, int *&L, int *&T)
{
// Tìm đường đi ngắn nhất
/* == BƯỚC 1 ==*/
for (int i = 0; i < verNum; ++i)
{
T[i] = 1; // Gán T = V
L[i] = INF; // Gán L[i] = VOCUC với mọi đỉnh i
B[i] = -1; // Gán B[i] = -1 với mọi đỉnh i
}
L[startVer] = 0; // Gán L[s] = 0
/* == BƯỚC 2: Kiểm tra g có còn thuộc T hay không == */
while(T[goalVer] == 1)
{
/* == BƯỚC 3: Chọn đỉnh i thuộc T sao cho L[i] nhỏ nhất và gán T = T\{i} == */
int Lmin = INF; // Lưu giá trị L[i] nhỏ nhất
int iMin = INF; // Lưu chỉ số đỉnh có L[i] nhỏ nhất
// Duyệt qua tìm giá trị Lmin
for(int i = 0; i < verNum; ++i)
{
// Kiểm tra đỉnh i có thuộc T hay không và so sánh tìm giá trị L[i] nhỏ nhất
if(T[i] == 1 && L[i] < Lmin)
{
Lmin = L[i];
iMin = i;
}
}
T[iMin] = 0; // gán T = T\{i} với i=iMin có L[i]=Lmin nhỏ nhất tìm được
/* == BƯỚC 4: Với mọi j thuộc T và có cạnh nối đến i=iMin == */
for(int j = 0; j < verNum; ++j)
{
if((T[j] == 1 && Graph[iMin][j] != INF) && (L[j] == INF || L[j] > L[iMin] + Graph[iMin][j]))
{
L[j] = L[iMin] + Graph[iMin][j];
B[j] = iMin;
}
}
/*== BƯỚC 5: Quay lại bước 2 ==*/
}
/*== BƯỚC 6: Dừng thuật toán ==*/
}
// Đọc một ma trận
void importFile(char *file_input_name, int **&Graph, int &verNum)
{
ifstream inFile(file_input_name);
if (inFile.is_open())
{
inFile >> verNum; // Đọc số lượng đỉnh
int **WeightMatrix = new int*[verNum];
for (int t = 0; t < verNum; t++)
{
WeightMatrix[t] = new int[verNum];
}
for (int i = 0; i < verNum; i++)
{
for (int j = 0; j < verNum; j++)
{
int nWeight;
inFile >> nWeight;
if (nWeight == 0 && i != j)
{
nWeight = INF;
}
WeightMatrix[i][j] = nWeight;
}
}
Graph = WeightMatrix;
inFile.close();
}
else
cout << "Unable to open file";
}
PRIM(minimum spanning tree)
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;
struct SEdge
{
int m_iRow; // Số dòng của một đỉnh
int m_iCol; // Số cột của một đỉnh
};
// Đọc một ma trận
void importFile(char *filename_input_name, int Graph[][100],int &vertexNumber)
{
ifstream txt (filename_input_name);
txt >> vertexNumber; // Đọc số lượng đỉnh
if (txt.is_open())
{
for(int i = 0; i < vertexNumber; i++)
{
for(int j = 0; j < vertexNumber; j++)
{
txt >> Graph[i][j];
}
}
txt.close();
}
else
cout << "Unable to open file";
}
// Xuất output
void outputFile(char* file_output_name,int A[][100], int vertexNumber, SEdge *T)
{
ofstream txt (file_output_name);
if (txt.is_open())
{
// Dòng 1 : In ra trọng số của các cạnh
for (int i = 0; i < vertexNumber - 1; i++)
{
txt << A[T[i].m_iRow][T[i].m_iCol];
if (i != vertexNumber)
txt << " ";
}
// Dòng 2 : In các cạnh trong cây khung tìm được
txt << "\n{";
for (int j = 0; j < vertexNumber - 1; j++)
{
txt << "(" << (T[j].m_iRow + 1) << "," << (T[j].m_iCol + 1) << ")";
if (j < vertexNumber - 2)
txt << " ; ";
}
txt << "}";
txt.close();
}
else
cout << "Unable to open file";
}
void PRIM(int Graph[][100], int vertexNumber, SEdge *eaCategory)
{
int *_labelArray = new int[100]; // Mảng đánh nhãn cho 1 đỉnh thuộc tập Y hoặc V\Y
int _categoryNumber = 0; // Số phần tử trong tập T
/** === BƯỚC 1 === **/
// Gán tất cả các đỉnh của đồ thị G thuộc tập V\Y
for(int i=0; i < vertexNumber; i++)
{
_labelArray[i] = 0;
}
// Bắt đầu duyệt từ đỉnh 0, đưa đỉnh 0 vào tập Y
_labelArray[0] = 1;
/** === BƯỚC 4 === **/
// Lặp cho đến khi số phần tử của tập T là n-1
while (_categoryNumber < vertexNumber-1)
{
SEdge edgeMin; // Lưu lại cạnh có trọng số nhỏ nhất
int vlMin = -1; // Giá trị trọng số của cạnh edgeMin, khởi tạo là -1
/** === BƯỚC 2 === **/
for(int i= 0 ; i < vertexNumber; i++)
{
// Kiểm tra xem đỉnh w có thuộc tập V/Y hay không
if(_labelArray[i] == 1)
{
for(int j = 0; j < vertexNumber; j++)
{
bool a = _labelArray[j] == 0; // Đã duyệt chưa
bool b = Graph[j][i] != 0 && Graph[i][j] != 0; // Có cạnh nối hay không
bool c = vlMin == -1 || Graph[j][i] < vlMin; // Nếu cạnh nối giữa v và w nhỏ hơn cạnh có trọng số nhỏ nhất tìm được
if(a && b && c)
{
vlMin = Graph[j][i]; // Gán lại giá trị cạnh nhỏ nhất nho vlMin
edgeMin.m_iRow = i; // Gán lại giá trị đỉnh cho cạnh edgeMin
edgeMin.m_iCol = j; // Gán lại giá trị đỉnh cho cạnh edgeMin
}
}
}
}
/** === BƯỚC 3 === **/
eaCategory[_categoryNumber] = edgeMin; // Thêm cạnh edgeMin vào tập T
_categoryNumber++; // Tăng số lượng phần tử tập T
_labelArray[edgeMin.m_iCol] = 1; // Gán đỉnh w vừa duyệt qua vào tập Y
}
}
void main()
{
int Graph[100][100];
int vertexNumber;
importFile("input.txt", Graph, vertexNumber);
SEdge *eaCategory = new SEdge[vertexNumber - 1];
PRIM(Graph, vertexNumber, eaCategory);
outputFile("output.txt", Graph, vertexNumber, eaCategory);
}
#include <iostream>
#include <cmath>
using namespace std;
struct SEdge
{
int m_iRow; // Số dòng của một đỉnh
int m_iCol; // Số cột của một đỉnh
};
// Đọc một ma trận
void importFile(char *filename_input_name, int Graph[][100],int &vertexNumber)
{
ifstream txt (filename_input_name);
txt >> vertexNumber; // Đọc số lượng đỉnh
if (txt.is_open())
{
for(int i = 0; i < vertexNumber; i++)
{
for(int j = 0; j < vertexNumber; j++)
{
txt >> Graph[i][j];
}
}
txt.close();
}
else
cout << "Unable to open file";
}
// Xuất output
void outputFile(char* file_output_name,int A[][100], int vertexNumber, SEdge *T)
{
ofstream txt (file_output_name);
if (txt.is_open())
{
// Dòng 1 : In ra trọng số của các cạnh
for (int i = 0; i < vertexNumber - 1; i++)
{
txt << A[T[i].m_iRow][T[i].m_iCol];
if (i != vertexNumber)
txt << " ";
}
// Dòng 2 : In các cạnh trong cây khung tìm được
txt << "\n{";
for (int j = 0; j < vertexNumber - 1; j++)
{
txt << "(" << (T[j].m_iRow + 1) << "," << (T[j].m_iCol + 1) << ")";
if (j < vertexNumber - 2)
txt << " ; ";
}
txt << "}";
txt.close();
}
else
cout << "Unable to open file";
}
void PRIM(int Graph[][100], int vertexNumber, SEdge *eaCategory)
{
int *_labelArray = new int[100]; // Mảng đánh nhãn cho 1 đỉnh thuộc tập Y hoặc V\Y
int _categoryNumber = 0; // Số phần tử trong tập T
/** === BƯỚC 1 === **/
// Gán tất cả các đỉnh của đồ thị G thuộc tập V\Y
for(int i=0; i < vertexNumber; i++)
{
_labelArray[i] = 0;
}
// Bắt đầu duyệt từ đỉnh 0, đưa đỉnh 0 vào tập Y
_labelArray[0] = 1;
/** === BƯỚC 4 === **/
// Lặp cho đến khi số phần tử của tập T là n-1
while (_categoryNumber < vertexNumber-1)
{
SEdge edgeMin; // Lưu lại cạnh có trọng số nhỏ nhất
int vlMin = -1; // Giá trị trọng số của cạnh edgeMin, khởi tạo là -1
/** === BƯỚC 2 === **/
for(int i= 0 ; i < vertexNumber; i++)
{
// Kiểm tra xem đỉnh w có thuộc tập V/Y hay không
if(_labelArray[i] == 1)
{
for(int j = 0; j < vertexNumber; j++)
{
bool a = _labelArray[j] == 0; // Đã duyệt chưa
bool b = Graph[j][i] != 0 && Graph[i][j] != 0; // Có cạnh nối hay không
bool c = vlMin == -1 || Graph[j][i] < vlMin; // Nếu cạnh nối giữa v và w nhỏ hơn cạnh có trọng số nhỏ nhất tìm được
if(a && b && c)
{
vlMin = Graph[j][i]; // Gán lại giá trị cạnh nhỏ nhất nho vlMin
edgeMin.m_iRow = i; // Gán lại giá trị đỉnh cho cạnh edgeMin
edgeMin.m_iCol = j; // Gán lại giá trị đỉnh cho cạnh edgeMin
}
}
}
}
/** === BƯỚC 3 === **/
eaCategory[_categoryNumber] = edgeMin; // Thêm cạnh edgeMin vào tập T
_categoryNumber++; // Tăng số lượng phần tử tập T
_labelArray[edgeMin.m_iCol] = 1; // Gán đỉnh w vừa duyệt qua vào tập Y
}
}
void main()
{
int Graph[100][100];
int vertexNumber;
importFile("input.txt", Graph, vertexNumber);
SEdge *eaCategory = new SEdge[vertexNumber - 1];
PRIM(Graph, vertexNumber, eaCategory);
outputFile("output.txt", Graph, vertexNumber, eaCategory);
}
Kruskal
#include <fstream>
#include <iostream>
#include <cmath>
using namespace std;
struct SEdge
{
int m_iRow; // Số dòng của một đỉnh
int m_iCol; // Số cột của một đỉnh
};
// Đọc ma trận có trọng số
void importFile(char *filename_input_name, int Graph[][100],int &vertexNumber)
{
ifstream txt (filename_input_name);
txt >> vertexNumber; // Đọc số lượng đỉnh
if (txt.is_open())
{
for(int i = 0; i < vertexNumber; i++)
{
for(int j = 0; j < vertexNumber; j++)
{
txt >> Graph[i][j];
}
}
txt.close();
}
else
cout << "Unable to open file";
}
// Xuất output
void outputFile(char* file_output_name,int A[][100], int vertexNumber, SEdge *T)
{
ofstream txt (file_output_name);
if (txt.is_open())
{
// Dòng 1 : In ra trọng số của các cạnh
for (int i = 0; i < vertexNumber - 1; i++)
{
txt << A[T[i].m_iRow][T[i].m_iCol];
if (i != vertexNumber)
txt << " ";
}
// Dòng 2 : In các cạnh trong cây khung tìm được
txt << "\n{";
for (int j = 0; j < vertexNumber - 1; j++)
{
txt << "(" << (T[j].m_iRow + 1) << "," << (T[j].m_iCol + 1) << ")";
if (j < vertexNumber - 2)
txt << " ; ";
}
txt << "}";
txt.close();
}
else
cout << "Unable to open file";
}
Edge T[100]; // Mảng chứa các cạnh trong cây khung
int nT = 0; // Số phần tử trong tập T
Edge ListEdge[100]; // Mảng chứa các cạnh của đồ thị G
int edgeNumber = 0; // Số lượng cạnh của G
int Label[100]; // Mảng đánh nhãn đỉnh dùng để xét việc tạo chu trình khi thêm cạnh hay không
// Sắp xếp danh sách cạnh theo thứ tự trọng số tăng dần
void SortEdge()
{
// Dùng thuật toán sắp xếp để sắp xếp danh sách cạnh theo thứ tự trọng số tăng dần
}
// Khởi tạo danh sách cạnh của đồ thị từ ma trận trọng số
void CreateListEdge()
{
// Duyệt qua ma trận trọng số của đồ thị
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
// Nếu có cạnh thì thêm vào danh sách cạnh
if(Graph[i][j] != 0)
{
SEdge edge;
edge.iRow = i;
canh.iCol = j;
DSCANH[nCanh] = canh;
nCanh++;
}
}
}
}
// Hàm kiểm tra việc thêm cạnh e vào T có tạo thành chu trình hay không
bool CoChuTrinh(int e)
{
// Nếu nhãn của hai đỉnh trong e là giống nhau => tạo thành chu trình, trả về true
if(Nhan[DSCANH[e].v] == Nhan[DSCANH[e].w])
return true;
// Tìm xem nhãn nào lớn hơn và nhỏ hơn
int NhanNho, NhanLon;
NhanNho = min(Nhan[DSCANH[e].v], Nhan[DSCANH[e].w]);
NhanNho = max(Nhan[DSCANH[e].v], Nhan[DSCANH[e].w]);
// Duyệt qua nhãn của các đỉnh
for(int i = 0; i < g.nSoDinh; ++i)
{
// Nếu nhãn của đỉnh nào đang bằng nhãn lớn hơn thì gán thành nhãn nhỏ hơn
if(Nhan[i] == NhanLon)
Nhan[i] = NhanNho;
}
return false;
}
// Tìm cây khung nhỏ nhất sử dụng Kruskal
void Kruskal()
{
/** === BƯỚC 1 ===
== LẤY DANH SÁCH CẠNH CỦA ĐỒ THỊ TỪ MA TRẬN KỀ VÀ SẮP XẾP THEO TRỌNG SỐ == **/
KhoiTaoDanhSachCanh();
SapXepCanh();
/** Gán nhãn cho các đỉnh của G (phục vụ cho mục đích kiểm tra việc tạo thành chu trình) **/
for(int i=0; i < g.nSodinh; i++)
{
Nhan[i] = i;
}
/** === BƯỚC 3 === **/
// Lặp cho đến khi số phần tử của tập T là n-1
while (nT < g.nSodinh-1)
{
/** === BƯỚC 2 ===
Lần lượt lấy từng cạnh e trong DSCANH đã sắp xếp, nếu đưa e vào T không tạo thành chu trình thì thêm e vào T **/
for(int e = 0; (e < nCanh) && (nT == g.nSodinh-1); i++)
{
bool khongthem = CoChuTrinh(e); // Kiểm tra xem việc thêm cạnh e vào có tạo chu trình hay không
// Nếu không tạo thành chu trình thì thêm cạnh e vào
if(!khongthem)
{
T[nT] = DSCANH[e];
nT++;
if (nT == g.nSodinh-1)
break;
}
}
if (nT == g.nSodinh - 1)
{
cout << "Lien thong";
}
else
{
cout << "Khong lien thong";
}
}
}
void main()
{
int Graph[100][100];
int vertexNumber;
importFile("input.txt", Graph, vertexNumber);
SEdge *eaCategory = new SEdge[vertexNumber - 1];
Kruskal(Graph, vertexNumber, eaCategory);
outputFile("output.txt", Graph, vertexNumber, eaCategory);
}
#include <iostream>
#include <cmath>
using namespace std;
struct SEdge
{
int m_iRow; // Số dòng của một đỉnh
int m_iCol; // Số cột của một đỉnh
};
// Đọc ma trận có trọng số
void importFile(char *filename_input_name, int Graph[][100],int &vertexNumber)
{
ifstream txt (filename_input_name);
txt >> vertexNumber; // Đọc số lượng đỉnh
if (txt.is_open())
{
for(int i = 0; i < vertexNumber; i++)
{
for(int j = 0; j < vertexNumber; j++)
{
txt >> Graph[i][j];
}
}
txt.close();
}
else
cout << "Unable to open file";
}
// Xuất output
void outputFile(char* file_output_name,int A[][100], int vertexNumber, SEdge *T)
{
ofstream txt (file_output_name);
if (txt.is_open())
{
// Dòng 1 : In ra trọng số của các cạnh
for (int i = 0; i < vertexNumber - 1; i++)
{
txt << A[T[i].m_iRow][T[i].m_iCol];
if (i != vertexNumber)
txt << " ";
}
// Dòng 2 : In các cạnh trong cây khung tìm được
txt << "\n{";
for (int j = 0; j < vertexNumber - 1; j++)
{
txt << "(" << (T[j].m_iRow + 1) << "," << (T[j].m_iCol + 1) << ")";
if (j < vertexNumber - 2)
txt << " ; ";
}
txt << "}";
txt.close();
}
else
cout << "Unable to open file";
}
Edge T[100]; // Mảng chứa các cạnh trong cây khung
int nT = 0; // Số phần tử trong tập T
Edge ListEdge[100]; // Mảng chứa các cạnh của đồ thị G
int edgeNumber = 0; // Số lượng cạnh của G
int Label[100]; // Mảng đánh nhãn đỉnh dùng để xét việc tạo chu trình khi thêm cạnh hay không
// Sắp xếp danh sách cạnh theo thứ tự trọng số tăng dần
void SortEdge()
{
// Dùng thuật toán sắp xếp để sắp xếp danh sách cạnh theo thứ tự trọng số tăng dần
}
// Khởi tạo danh sách cạnh của đồ thị từ ma trận trọng số
void CreateListEdge()
{
// Duyệt qua ma trận trọng số của đồ thị
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < n; ++j)
{
// Nếu có cạnh thì thêm vào danh sách cạnh
if(Graph[i][j] != 0)
{
SEdge edge;
edge.iRow = i;
canh.iCol = j;
DSCANH[nCanh] = canh;
nCanh++;
}
}
}
}
// Hàm kiểm tra việc thêm cạnh e vào T có tạo thành chu trình hay không
bool CoChuTrinh(int e)
{
// Nếu nhãn của hai đỉnh trong e là giống nhau => tạo thành chu trình, trả về true
if(Nhan[DSCANH[e].v] == Nhan[DSCANH[e].w])
return true;
// Tìm xem nhãn nào lớn hơn và nhỏ hơn
int NhanNho, NhanLon;
NhanNho = min(Nhan[DSCANH[e].v], Nhan[DSCANH[e].w]);
NhanNho = max(Nhan[DSCANH[e].v], Nhan[DSCANH[e].w]);
// Duyệt qua nhãn của các đỉnh
for(int i = 0; i < g.nSoDinh; ++i)
{
// Nếu nhãn của đỉnh nào đang bằng nhãn lớn hơn thì gán thành nhãn nhỏ hơn
if(Nhan[i] == NhanLon)
Nhan[i] = NhanNho;
}
return false;
}
// Tìm cây khung nhỏ nhất sử dụng Kruskal
void Kruskal()
{
/** === BƯỚC 1 ===
== LẤY DANH SÁCH CẠNH CỦA ĐỒ THỊ TỪ MA TRẬN KỀ VÀ SẮP XẾP THEO TRỌNG SỐ == **/
KhoiTaoDanhSachCanh();
SapXepCanh();
/** Gán nhãn cho các đỉnh của G (phục vụ cho mục đích kiểm tra việc tạo thành chu trình) **/
for(int i=0; i < g.nSodinh; i++)
{
Nhan[i] = i;
}
/** === BƯỚC 3 === **/
// Lặp cho đến khi số phần tử của tập T là n-1
while (nT < g.nSodinh-1)
{
/** === BƯỚC 2 ===
Lần lượt lấy từng cạnh e trong DSCANH đã sắp xếp, nếu đưa e vào T không tạo thành chu trình thì thêm e vào T **/
for(int e = 0; (e < nCanh) && (nT == g.nSodinh-1); i++)
{
bool khongthem = CoChuTrinh(e); // Kiểm tra xem việc thêm cạnh e vào có tạo chu trình hay không
// Nếu không tạo thành chu trình thì thêm cạnh e vào
if(!khongthem)
{
T[nT] = DSCANH[e];
nT++;
if (nT == g.nSodinh-1)
break;
}
}
if (nT == g.nSodinh - 1)
{
cout << "Lien thong";
}
else
{
cout << "Khong lien thong";
}
}
}
void main()
{
int Graph[100][100];
int vertexNumber;
importFile("input.txt", Graph, vertexNumber);
SEdge *eaCategory = new SEdge[vertexNumber - 1];
Kruskal(Graph, vertexNumber, eaCategory);
outputFile("output.txt", Graph, vertexNumber, eaCategory);
}
Depth-first search
#include "fstream"
#include "iostream"
using namespace std;
int Arr[100][100]; // Ma trận kề
int size; // Số đỉng
int visited[100] = {0}; // Tạo mảng đánh dấu các phần tử đã duyệt
// Nhập file từ ma trận kề
void Import(char *filename)
{
ifstream txt (filename);
txt >> size;
if (txt.is_open())
{
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt >> Arr[i][j];
}
}
txt.close();
}
else cout << "Unable to open file";
}
// Xuất file từ ma trận kề
void Export()
{
ofstream txt ("Output.txt");
if (txt.is_open())
{
txt << size << "\n";
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt << Arr[i][j];
if(j != size-1)
txt << " ";
}
if (i != size-1)
txt << "\n";
}
txt.close();
}
else cout << "Unable to open file";
}
void DFS(int v, int dem) // Deep First Search
{
visited[v] = dem; // Đánh dấu vị trí đã duyệt
int i = 0;
for (i = 0; i < size; ++i) // Tiếp tục xét các cạnh kề
{
bool kt = (Arr[v][i] == 1 || Arr[i][v] == 1); // có cạnh nối hay không
if (kt && visited[i] == 0) // Nếu có cạnh nối và đỉnh đó chưa thăm
{
DFS(i, dem); // Xét tiếp cạnh tiếp theo
}
}
}
int xetLienThong()
{
int dem = 0; // biến để đếm xem có bao nhiêu thành phần liên thông
for (int i = 0; i < size; i++) // Xét mảng visited
{
if (visited[i] == 0) // Nếu duyệt đến phần tử nào
{
dem++;
DFS(i, dem); // thì duyệt theo hướng đó
}
}
return dem;
}
void InThanhPhanLienThong()
{
int soTPLT = xetLienThong();
if(soTPLT == 1)
printf("Do thi lien thong.\n");
else
{
printf("Do thi khong lien thong, co %d TPLT.\n", soTPLT);
for(int i = 1; i <= soTPLT; ++i)
{
printf("Mien lien thong %d:", i);
for(int j = 0; j < size; ++j)
{
if(visited[j] == i)
printf(" %d", j);
}
printf("\n");
}
}
}
void main()
{
Import("Matrix.txt");
Export();
InThanhPhanLienThong();
}
#include "iostream"
using namespace std;
int Arr[100][100]; // Ma trận kề
int size; // Số đỉng
int visited[100] = {0}; // Tạo mảng đánh dấu các phần tử đã duyệt
// Nhập file từ ma trận kề
void Import(char *filename)
{
ifstream txt (filename);
txt >> size;
if (txt.is_open())
{
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt >> Arr[i][j];
}
}
txt.close();
}
else cout << "Unable to open file";
}
// Xuất file từ ma trận kề
void Export()
{
ofstream txt ("Output.txt");
if (txt.is_open())
{
txt << size << "\n";
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt << Arr[i][j];
if(j != size-1)
txt << " ";
}
if (i != size-1)
txt << "\n";
}
txt.close();
}
else cout << "Unable to open file";
}
void DFS(int v, int dem) // Deep First Search
{
visited[v] = dem; // Đánh dấu vị trí đã duyệt
int i = 0;
for (i = 0; i < size; ++i) // Tiếp tục xét các cạnh kề
{
bool kt = (Arr[v][i] == 1 || Arr[i][v] == 1); // có cạnh nối hay không
if (kt && visited[i] == 0) // Nếu có cạnh nối và đỉnh đó chưa thăm
{
DFS(i, dem); // Xét tiếp cạnh tiếp theo
}
}
}
int xetLienThong()
{
int dem = 0; // biến để đếm xem có bao nhiêu thành phần liên thông
for (int i = 0; i < size; i++) // Xét mảng visited
{
if (visited[i] == 0) // Nếu duyệt đến phần tử nào
{
dem++;
DFS(i, dem); // thì duyệt theo hướng đó
}
}
return dem;
}
void InThanhPhanLienThong()
{
int soTPLT = xetLienThong();
if(soTPLT == 1)
printf("Do thi lien thong.\n");
else
{
printf("Do thi khong lien thong, co %d TPLT.\n", soTPLT);
for(int i = 1; i <= soTPLT; ++i)
{
printf("Mien lien thong %d:", i);
for(int j = 0; j < size; ++j)
{
if(visited[j] == i)
printf(" %d", j);
}
printf("\n");
}
}
}
void main()
{
Import("Matrix.txt");
Export();
InThanhPhanLienThong();
}
Breadth-first search
#include <fstream>
#include <iostream>
#include <queue>
using namespace std;
queue<int> Queue; // Tạo hàng đợi
int Arr[100][100]; // Ma trận kề
int size; // Số đỉnh
int visited[100] = {0}; // Mảng kiếm tra đã xét hết các phần tử hay chưa
// Nhập file từ ma trận kề
void Import(char *filename)
{
ifstream txt (filename);
txt >> size;
if (txt.is_open())
{
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt >> Arr[i][j];
}
}
txt.close();
}
else cout << "Unable to open file";
}
// Xuất file từ ma trận kề
void Export()
{
ofstream txt ("Output.txt");
if (txt.is_open())
{
txt << size << "\n";
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt << Arr[i][j];
if(j != size-1)
txt << " ";
}
if (i != size-1)
txt << "\n";
}
txt.close();
}
else cout << "Unable to open file";
}
void BFS(int v, int dem) // Breadth First Search
{
Queue.push(v); // Đưa đỉnh v vào trong hàng đợi
while (!Queue.empty())
{
int p = Queue.front(); // Lấy q ra khỏi hàng đợi
Queue.pop();
visited[p] = dem;
for (int i = 0; i < size; ++i) // Duyệt các đỉnh kề với p
{
bool ck = (Arr[i][p] == 1) || (Arr[p][i] == 1); // Nếu tồn tại cạnh nối
if (ck && visited[i] == 0)
{
Queue.push(i); // Đẩy đỉnh i vào hàng đợi
}
}
}
}
int xetLienThong()
{
int dem = 0; // biến để đếm xem có bao nhiêu thành phần liên thông
for (int i = 0; i < size; i++) // Xét mảng visited
{
if (visited[i] == 0) // Nếu duyệt đến phần tử nào
{
dem++;
BFS(i, dem); // thì duyệt theo hướng đó
}
}
return dem;
}
void InThanhPhanLienThong()
{
int soTPLT = xetLienThong();
if(soTPLT == 1)
printf("Do thi lien thong.\n");
else
{
printf("Do thi khong lien thong, co %d TPLT.\n", soTPLT);
for(int i = 1; i <= soTPLT; ++i)
{
printf("Mien lien thong %d:", i);
for(int j = 0; j < size; ++j)
{
if(visited[j] == i)
printf(" %d", j);
}
printf("\n");
}
}
}
void main()
{
Import("Matrix.txt");
Export();
InThanhPhanLienThong();
}
#include <iostream>
#include <queue>
using namespace std;
queue<int> Queue; // Tạo hàng đợi
int Arr[100][100]; // Ma trận kề
int size; // Số đỉnh
int visited[100] = {0}; // Mảng kiếm tra đã xét hết các phần tử hay chưa
// Nhập file từ ma trận kề
void Import(char *filename)
{
ifstream txt (filename);
txt >> size;
if (txt.is_open())
{
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt >> Arr[i][j];
}
}
txt.close();
}
else cout << "Unable to open file";
}
// Xuất file từ ma trận kề
void Export()
{
ofstream txt ("Output.txt");
if (txt.is_open())
{
txt << size << "\n";
for(int i=0;i<size;i++){
for(int j=0;j<size;j++){
txt << Arr[i][j];
if(j != size-1)
txt << " ";
}
if (i != size-1)
txt << "\n";
}
txt.close();
}
else cout << "Unable to open file";
}
void BFS(int v, int dem) // Breadth First Search
{
Queue.push(v); // Đưa đỉnh v vào trong hàng đợi
while (!Queue.empty())
{
int p = Queue.front(); // Lấy q ra khỏi hàng đợi
Queue.pop();
visited[p] = dem;
for (int i = 0; i < size; ++i) // Duyệt các đỉnh kề với p
{
bool ck = (Arr[i][p] == 1) || (Arr[p][i] == 1); // Nếu tồn tại cạnh nối
if (ck && visited[i] == 0)
{
Queue.push(i); // Đẩy đỉnh i vào hàng đợi
}
}
}
}
int xetLienThong()
{
int dem = 0; // biến để đếm xem có bao nhiêu thành phần liên thông
for (int i = 0; i < size; i++) // Xét mảng visited
{
if (visited[i] == 0) // Nếu duyệt đến phần tử nào
{
dem++;
BFS(i, dem); // thì duyệt theo hướng đó
}
}
return dem;
}
void InThanhPhanLienThong()
{
int soTPLT = xetLienThong();
if(soTPLT == 1)
printf("Do thi lien thong.\n");
else
{
printf("Do thi khong lien thong, co %d TPLT.\n", soTPLT);
for(int i = 1; i <= soTPLT; ++i)
{
printf("Mien lien thong %d:", i);
for(int j = 0; j < size; ++j)
{
if(visited[j] == i)
printf(" %d", j);
}
printf("\n");
}
}
}
void main()
{
Import("Matrix.txt");
Export();
InThanhPhanLienThong();
}
Đăng ký:
Bài đăng (Atom)