Cài đặt một số thuật toán lý thuyết đồ thị

byTin tức và học tập - 0

 


   Trong phần này chúng ta chỉ cài đặt các thuật toán trên đồ thị  vô hướng liên thông. Các loại đồ thị khác cài đặt tương tự. Biểu diễn đơn đồ thị vô hướng liên thông bằng ma trận kề, tạo tệp tin GRAPH.IN có số đỉnh (n = 13) và ma trận hai kề như hình vẽ

1. Thuật toán duyệt đồ thị

Bài toán duyệt đồ thị:

Đầu vào: Đơn đồ thị vô hướng G = (V, E) gồm m đỉnh và n cạnh. Các đỉnh được đánh số từ 1 đến n. Đỉnh xuất phát là S và đỉnh kết thúc là F.

Đầu ra:

  • Tất cả các đỉnh có thể đến được từ đỉnh S;
  • Một đường đi đơn nếu có từ S đến F.

Mục đích của duyệt đồ thị

  • Kiểm tra đường đi giữa 2 đỉnh
  • Chia đồ thị thành các thành phần liên thông
  • Xây dựng cây khung của đồ thị
  • Kiểm tra xem đồ thị có chu trình hay không

1.1. Thuật toán duyệt đồ thị theo chiều rộng (Breath First Search)

package chap03;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;


public class BFSDemo {

/**
 * Phương thức chính của toàn bộ chương trình.
 */
private int size;
private boolean free[];
private int queue[];
private int G[][];
/**
 * Đọc dữ liệu từ file và lưu vào trong mảng hai chiều.
 */
public void readData() {
File file = new File(getClass().getResource("GRAPH.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
this.size = Integer.parseInt(reader.readLine());
G = new int[size][size];
free = new boolean[size];
queue = new int[size];
for (int i = 0; i < this.size; i++) 
free[i] = true;
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị dữ liệu ra ngoài màn hình.
 */
public void showResult() {
for (int i = 0; i < this.size; i++) {
for (int j = 0; j < this.size; j++) {
System.out.print(G[i][j] + " ");
}
System.out.println();
}
}

/**
 * Phương thức tìm kiếm theo chiều rộng
 */
public void breadthFirstSearch(int v) {
int u, first, last;
first = last = 0;
queue[last] = v;
free[v] = false;
while (first <= last) {
u = queue[first];
first = first + 1;
System.out.print(u + " ");
for (int i = 0; i < size; i++) {
if (free[i] && G[u][i] == 1) {
last = last + 1;
queue[last] = i;
free[i] = false;
}
}
}
}
/**
 * Hàm main.
 * 
 * @param args(not use)
 */
public static void main(String[] args) {
BFSDemo obj = new BFSDemo();
obj.readData();
obj.showResult();
for(int i = 0; i < obj.size;i++){
if(obj.free[i]){
obj.breadthFirstSearch(i);
}
}
}
}

1.2. Thuật toán duyệt đồ thị theo chiều sâu (Depth First Search)

package chap03;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class DFSDemo {

private int size;
private boolean free[];
private int G[][];

/**
 * Đọc dữ liệu từ file dữ liệu vào ma trận.
 */
public void readData() {
File file = new File(getClass().getResource("GRAPH.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
this.size = Integer.parseInt(reader.readLine());
G = new int[size][size];
free = new boolean[size];
for (int i = 0; i < this.size; i++)
free[i] = true;
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

public void showResult() {
for (int i = 0; i < this.size; i++) {
for (int j = 0; j < this.size; j++) {
System.out.print(G[i][j] + " ");
}
System.out.println();
}
}

/**
 * Thuật toán duyệt đồ thị theo chiều sâu.
 * @author MinhNX
 */
public void depthFirstSearch(int v) {
System.out.print(v + " ");
free[v] = false;
for (int u = 0; u < size; u++) {
if (free[u] && G[v][u] == 1) {
depthFirstSearch(u);
}
}
}

/**
 * Hàm chính của chương trình.
 * @param args (not use)
 */
public static void main(String[] args) {
System.out.println("Tìm kiếm theo chiều sâu.");
DFSDemo obj = new DFSDemo();
obj.readData();
for (int i = 0; i < obj.size; i++) {
if (obj.free[i])
obj.depthFirstSearch(i);
}
}
}

2. Thuật toán tìm đường đi trong đồ thị liên thông
    Kiểm tra hai đỉnh bất kỳ trong đồ thị có đường đi hay không? Nếu có đường đi thì in đường đi đó. Ta cũng có hai cách tìm đường đi từ hai đỉnh bất kỳ dựa trên thuật toán duyệt đồ thị theo chiều rộng và theo chiều sâu:

2.1. Tìm  đường đi theo chiều sâu

package chap03;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;


public class FindPathDFS {

private int size;
private boolean free[];
private int G[][];
private int prev[];


/**
 * Đọc dữ liệu từ tệp tin vào ma trận kề
 */
public void readData() {
File file = new File(getClass().getResource("DFS13.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
/* Khởi tạo giá trị mạng chưa xét. */
free = new boolean[size];
prev = new int[size];
for (int i = 0; i < this.size; i++){
free[i] = true;
prev[i] = 0;
}
/* Đọc dữ liệu từ file lưu và mảng G. */
G = new int[size][size];
for (int i = 0; i < size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị dữ liệu mảng ma trận kề.
 */
public void showResult() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + " ");
}
System.out.println();
}
}

/**
 * Tìm đường theo thuật toán tìm đường theo chiều sâu.
 * 
 * @param v: Số đỉnh trên đồ thị.
 */
public void findPathDFS(int v) {
System.out.print(v + " ");
free[v] = false;
for (int u = 0; u < size; u++) {
if (free[u] && G[v][u] == 1) {
prev[u] = v;
findPathDFS(u);
}
}
}
/**
 * Hàm in kết quả.
 */
public void result(int s, int t){
if(prev[t] == 0){
System.out.println("Không có đường đi từ " + s+ " đến" + t);
return;
}
System.out.println("\nIn đường đi từ " + s + " đến " + t);
int j = t;
System.out.print(t + "->");
while(prev[j] != s){
System.out.print(prev[j] +"->");
j = prev[j];
}
System.out.print(s);
}

/**
 * Main method.<br>
 * 
 * @param args (Not use)
 */
public static void main(String[] args) {
FindPathDFS obj = new FindPathDFS();
obj.readData();
System.out.println("Nhập dữ liệu đỉnh đầu s và đỉnh cuối t.");
Scanner input = new Scanner(System.in);
int s = input.nextInt();
int t = input.nextInt();
obj.findPathDFS(s);
obj.result(s, t);
}
}

2.2. Tìm  đường đi theo chiều rộng

package chap03;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;

public class FindPathBFS {

private int size;
private boolean free[];
private int queue[];
private int prev[];
private int G[][];

/**
 * Hàm đọc dữ liệu từ file text
 */
public void readData() {
File file = new File(getClass().getResource("DFS13.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
G = new int[size][size];
free = new boolean[size];
queue = new int[size];
prev = new int[size];
for (int i = 0; i < size; i++){
free[i] = true;
prev[i] = 0;
}
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị dữ liệu ra ngoài màn hình.
 */
public void showResult() {
for (int i = 0; i < this.size; i++) {
for (int j = 0; j < this.size; j++) {
System.out.print(G[i][j] + " ");
}
System.out.println();
}
}

/**
 * Phương thức tìm kiếm theo chiều rộng
 */
public void fintPahtBFS(int v) {

int u, first, last;
first = last = 0;
queue[last] = v;
free[v] = false;

while (first <= last) {
u = queue[first];
first = first + 1;
System.out.print(u + " ");
for (int i = 0; i < size; i++) {
if (free[i] && G[u][i] == 1) {
last = last + 1;
queue[last] = i;
free[i] = false;
prev[i] = u;
}
}
}
}
/**
 * Hàm in kết quả.
 */
public void result(int s, int t){
if(prev[t] == 0){
System.out.println("Không có đường đi từ " + s+ " đến" + t);
return;
}
System.out.println("\nIn đường đi từ " + s + " đến " + t);
int j = t;
System.out.print(t + "->");
while(prev[j] != s){
System.out.print(prev[j] +"->");
j = prev[j];
}
System.out.print(s);
}
/**
 * Main method
 */
public static void main(String[] args) {
FindPathBFS obj = new FindPathBFS();
obj.readData();
System.out.println("Nhập dữ liệu đỉnh đầu s và đỉnh cuối t.");
Scanner input = new Scanner(System.in);
int s = input.nextInt();
int t = input.nextInt();
obj.fintPahtBFS(s);
obj.result(s, t);
}
}

3. Thuật toán tìm thành phần liên thông của đồ thị
  • Nếu đồ thị G = (V, E) liên thông thì thành phần liên thông là 1.
  • Nếu đồ thị G = (V, E) không liên thông thì hãy chỉ ra có bao nhiêu đồ thị con G' = (V', E') liên thông và liệt kê các đỉnh liên thông đó.
    Chung ta sẽ áp dụng thuật toán duyệt đồ thị theo chiều rộng hoặc theo chiều sâu để tìm thành phần liên thông này như sau:

// Sử dụng thuật toán duyệt đồ thị theo chiều sâu

package chap03;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;


public class FindConnecedDFS {

private int size;
private boolean free[];
private int G[][];
private int index[];
private int intConnected;

/**
 * Đọc dữ liệu từ file dữ liệu vào ma trận.
 */
public void readData() {
File file = new File(getClass().getResource("LT.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
/* Khởi tạo giá trị mạng chưa xét. */
free = new boolean[size];
index = new int[size];
for (int i = 0; i < this.size; i++){
free[i] = true;
index[i] = 0;
}
intConnected = 0;
/* Đọc dữ liệu từ file lưu và mảng G. */
G = new int[size][size];
for (int i = 0; i < size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}
/**
 * Hiển thị dữ liệu mảng ma trận kề.
 */
public void showResult() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + " ");
}
System.out.println();
}
}
/**
 * Thuật toán tìm kiếm theo chiều sâu.
 * @param v
 */
public void DFS(int v){
System.out.print(v + " ");
free[v] = false;
index[v] = intConnected;
for (int u = 0; u < size; u++) {
if (free[u] && G[v][u] == 1) {
DFS(u);
}
}
}
/**
 * Hiển thị số thành phần liên thông.
      * @author Nguyen Xuan Minh
 * 
 * @param intConnected
 */
public void showConnected(int intConnected){
if(intConnected == 1){
System.out.println("Đồ thị liên thông.");
return;
}else{
for(int i = 1; i <= intConnected; i++){
System.out.println("\nThành phần liên thông thứ " + i);
for(int j = 0; j< size; j++){
if(index[j] == i){
System.out.print(j + " ");
}
}
}
}
}
/**
 * Main method.<br>
 * @author Nguyen Xuan Minh
 * @param args (Not used)
 */
public static void main(String[] args) {
FindConnecedDFS obj = new FindConnecedDFS();
obj.readData();
obj.showResult();
for(int i = 0; i < obj.size; i++){
if(obj.free[i]){
obj.intConnected++;
obj.DFS(i);
}
}
obj.showConnected(obj.intConnected);
}
}

// Sử dụng thuật toán duyệt đồ thị theo chiều rộng

package chap03;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class FindConnectdBFS {
private int size;
private boolean free[];
private int G[][];
private int index[];
private int intConnected;
private int queue[];

public void readData() {
File file = new File(getClass().getResource("LT.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
/* Khởi tạo giá trị mạng chưa xét. */
free = new boolean[size];
index = new int[size];
queue = new int[size];
for (int i = 0; i < this.size; i++){
free[i] = true;
index[i] = 0;
}
intConnected = 0;
/* Đọc dữ liệu từ file lưu và mảng G. */
G = new int[size][size];
for (int i = 0; i < size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}
/**
 * Hiển thị dữ liệu mảng ma trận kề.
 */
public void showResult() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + " ");
}
System.out.println();
}
}
public void BFS(int v) {
int u, first, last;
first = last = 0;
queue[last] = v;
free[v] = false;
while (first <= last) {
u = queue[first];
first = first + 1;
index[u] = intConnected;
System.out.print(u + " ");
for (int i = 0; i < size; i++) {
if (free[i] && G[u][i] == 1) {
last = last + 1;
queue[last] = i;
free[i] = false;
}
}
}
}
public void showConnected(int intConnected){
if(intConnected == 1){
System.out.println("Đồ thị liên thông.");
return;
}else{
for(int i = 1; i <= intConnected; i++){
System.out.println("\nThành phần liên thông thứ " + i);
for(int j = 0; j< size; j++){
if(index[j] == i){
System.out.print(j + " ");
}
}
}
}
}
/**
 * Main method.
 * @param args (not use)
 */
public static void main(String[] args) {
FindConnectdBFS obj = new FindConnectdBFS();
obj.readData();
obj.showResult();
for(int i = 0; i < obj.size;i++){
if(obj.free[i]){
obj.intConnected++;
obj.BFS(i);
}
}
obj.showConnected(obj.intConnected);
}
}

Kiểm thử với độ thị sau:
    

Kết quả đối với hai thuật toán trên là như sau


4. Tìm chu trình 

4.1. Tìm chu trình Euler và tìm đường đi Euler

package chap03;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class EulerCycle {

private int size;
private int G[][];
private int stack[];
private int top = 0;

/**
 * Đọc vào số đỉnh, ma trận kề lưu vào trong mảng G.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void readData() {
File file = new File(getClass().getResource("EulerPath.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
stack = new int[size * size];
G = new int[size][size];
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị kết quả.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void showResult() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + " ");
}
System.out.println();
}
}

/**
 * Tìm bậc của đỉnh.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public int degree(int v) {
int degree = 0;
for (int u = 0; u < this.size; u++) {
if (G[u][v] == 1 || G[v][u] == 1) {
degree = degree + 1;
}
}
return degree;
}

/**
 * Kiểm tra xem đồ thị có chu trình.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public boolean validEuler() {
boolean euler = false;
for (int i = 0; i < size; i++) {
if (degree(i) % 2 == 0)
euler = true;
else{
euler = false;
break;
}
}
return euler;
}
/**
 * Kiểm tra xem đồ thị có đường đi Euler.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public boolean validEulerPath() {
boolean eulerPath = false;
int count = 0;
for (int i = 0; i < size; i++) {
if (degree(i) % 2 == 1)
count++;
}
if(count == 2){
eulerPath = true;
}else
eulerPath = false;
return eulerPath;
}

/**
 * Tìm đỉnh bậc lẻ.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public int oddDegreeVertex() {
int vertex = -1;
for (int node = 1; node <= size; node++) {
if ((degree(node) % 2) != 0) {
vertex = node;
break;
}
}
return vertex;
}

/**
 * Đẩy phần tử vào đỉnh của ngăn xếp.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void push(int x) {
top = top + 1;
stack[top] = x;
}

/**
 * Lấy phần tử đầu ở đầu ngăn xếp.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2015
 */
public int pop() {
return stack[top--];
}

/**
 * 
 * @param v
 */
public void copy() {
int temp[][] = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
temp[i][j] = G[i][j];
}
}
}

public void findTour(int v) {
for (int u = 0; u < size; u++) {
if (G[u][v] == 1) {
G[u][v] = 0;
G[v][u] = 0;
findTour(u);
}
}
push(v);
}

/**
 * Hiển thị kết quả.
 */
public void showEulerTour() {
while (top != 0) {
System.out.print(pop() + " ");
}
}

/**
 * Chương trình chính.<br>
 */
public static void main(String[] args) {
EulerCycle obj = new EulerCycle();
obj.readData();
obj.showResult();
obj.copy();
if (obj.validEuler()) {
System.out.println("Đồ thị có chu trình Euler.");
obj.findTour(0);
obj.showEulerTour();
} else if(obj.validEulerPath()){
System.out.println("Đồ thị có đường đi Euler.");
obj.findTour(obj.oddDegreeVertex());
obj.showEulerTour();
}else
System.out.println("Đồ thị không có chu trình cũng như đường đi Euler.");
}
}

4.2. Tìm chu trình Hamilton (Đang cập nhập ....)

5. Tìm đường đi ngắn nhất

5.1. Thuật toán Dijkstra


package shortestpath;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class DijkstraAlgorithm {

/* Số đỉnh của đồ thị. */
private int size;
/* Đồ thị trọng số của đồ thị. */
private int G[][];
/* Mảng đánh dấu tập hợp. */
private int T[];
/* Mảng đánh dấu độ dài từ đỉnh đầu đến đỉnh cuối. */
private int L[];
/* Đỉnh liền trước trên đường đi. */
private int prev[];
/* Giá trị này là vô cực*/
private static final int VO_CUC = 1000;

/**
 * Khởi tạo.
 * 
 * @param firstVertex
 */
public void Initialize(int firstVertex) {
T = new int[size];
L = new int[size];
prev = new int[size];
for (int i = 0; i < size; i++) {
T[i] = 1;
L[i] = VO_CUC;
prev[i] = -1;
}
L[firstVertex] = 0;
}
/**
 * Thuật toán Dijkstra tìm đường đi ngắn nhất.
 * 
 * @param firstVertex: Đỉnh đầu tiên
 * @param endVertex: Đỉnh kết thúc
 */
public void dijkstra(int firstVertex, int endVertex) {
while (T[endVertex] == 1) {
int min = VO_CUC;
int minVertex = -1;
for (int i = 0; i < size; i++) {
if (T[i] == 1 &&  L[i] <= min) {
min = L[i];
minVertex = i;
}
}
if(minVertex == -1 || min == VO_CUC){
System.out.println("Không có đường đi ngắn nhất");
break;
}
T[minVertex] = 0;
for(int u = 0; u < size; u++){
if(G[minVertex][u] != VO_CUC && T[u]==1 && L[u] > L[minVertex] + G[minVertex][u]){
L[u] =  L[minVertex] + G[minVertex][u];
prev[u] = minVertex;
}
}
}
}
/**
 * Hiển thị đường đi ngắn nhất.
 */
public void showShortestPath(int firstVertex, int endVertex){
int j = endVertex;
System.out.println("Đường đi ngắn nhất:");
System.out.print(endVertex);
while(j != firstVertex){
j = prev[j];
System.out.print("->" + j);
}
System.out.println("\nĐộ dài là: " + L[endVertex]);
}
/**
 * Đọc vào số đỉnh, ma trận kề lưu vào trong mảng G.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void readData() {
File file = new File(getClass().getResource("GRAPH.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
G = new int[size][size];
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị kết quả.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void showResult() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + "  ");
}
System.out.println();
}
}

/**
 * Main method.<br>
 * 
 * @param args(not use)
 */
public static void main(String[] args) {
DijkstraAlgorithm obj = new DijkstraAlgorithm();
obj.readData();
obj.showResult();
obj.Initialize(0);
obj.dijkstra(0, 5);
obj.showShortestPath(0, 5);
}

}

5.2. Thuật toán Ford-Bellman

package shortestpath;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class BellmanFordAlgorithm {

/* Số đỉnh của đồ thị. */
private int size;
/* Đồ thị trọng số của đồ thị. */
private int G[][];
/* Độ dài đường đi ngắn nhất qua tối đa k đỉnh. */
private int Pi[][];
/* Đỉnh liền trước trên đường đi. */
private int prev[];
/* Giá trị này là vô cực */
private static final int VO_CUC = 1000;
/**/
@SuppressWarnings("unused")
private boolean success = false;
/* Số bước lắp thuật toán */
private int k;

/**
 * Khởi tạo.
 * 
 * @param firstVertex
 */
public void Initialize(int firstVertex) {
Pi = new int[size+1][size+1];
prev = new int[size];
for (int i = 0; i < size; i++) {
Pi[0][i] = VO_CUC;
prev[i] = i;
}
Pi[0][firstVertex] = 0;
}

/**
 * Thuật toán Bellman - Ford.
 * 
 * @param firstVertex
 */
public void bellmanFord(int firstVertex) {
success = false;
for (k = 1; k <= size; k++) {
for (int i = 0; i < size; i++) {
Pi[k][i] = Pi[k - 1][i];
for (int j = 0; j < size; j++) {
if (G[j][i] != VO_CUC && Pi[k - 1][j] != VO_CUC) {
if(Pi[k][i] == VO_CUC || Pi[k][i]>Pi[k-1][j] +G[j][i]){
Pi[k][i] = Pi[k-1][j] +G[j][i];
prev[i] = j;
}
}
}
}
boolean same = true;
for(int i = 0; i <size;i++){
if(Pi[k][i] != Pi[k-1][i]){
same = false;
break;
}
}
if(same){
success = true;
break;
}
}
}

/**
 * Hiển thị đường đi ngắn nhất.
 */
public void showShortestPath(int firstVertex, int endVertex) {
int j = endVertex;
System.out.println("Đường đi ngắn nhất:");
System.out.print(endVertex);
while (j != firstVertex) {
j = prev[j];
System.out.print("->" + j);
}
System.out.println("\nChi phí là:" + Pi[k][endVertex]);
}

/**
 * Đọc vào số đỉnh, ma trận kề lưu vào trong mảng G.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void readData() {
File file = new File(getClass().getResource("GRAPH.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
G = new int[size][size];
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị kết quả.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void showResult() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + "  ");
}
System.out.println();
}
}

/**
 * Main method.<br>
 * 
 * @param args (not use)
 */
public static void main(String[] args) {
BellmanFordAlgorithm obj = new BellmanFordAlgorithm();
obj.readData();
obj.Initialize(0);
obj.bellmanFord(0);
obj.showShortestPath(0, 2);
}

}

5.3. Thuật toán Floyd

package shortestpath;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class FloydAlgorithm {

/* Số đỉnh của đồ thị. */
private int size;
/* Đồ thị trọng số của đồ thị. */
private int G[][];
/* Độ dài đường đi ngắn nhất qua tối đa k đỉnh. */
private int D[][];
/* Đỉnh liền trước trên đường đi. */
private int P[][];
/* Giá trị này là vô cực */
private static final int VO_CUC = 1000;

/* Số bước lắp thuật toán */
private int k;

/**
 * Khởi tạo.
 * 
 * @param firstVertex
 */
public void Initialize() {
D = new int[size+1][size+1];
P = new int[size+1][size+1];
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
if (G[i][j] != VO_CUC) {
D[i][j] = G[i][j];
P[i][j] = i;
} else {
D[i][j] = VO_CUC;
P[i][j] = -1;
}
}
}
}

/**
 * Hiển thị đường đi ngắn nhất.
 */
public void showShortestPath(int firstVertex, int endVertex) {
if (P[firstVertex][endVertex] == -1) {
System.out.print("Không có đường đi từ " + firstVertex + " đến "
+ endVertex);
} else {
System.out.println("Đường đi ngắn nhất từ " + firstVertex + " đến "
+ endVertex + " là: ");
System.out.print(endVertex + "<---");
int u = endVertex;
while (P[firstVertex][u] != firstVertex) {
u = P[firstVertex][u];
System.out.print(u + "<---");
}
System.out.print(firstVertex);
System.out.println("\n Với độ dài đường đi là: "
+ D[firstVertex][endVertex]);
}
}

/**
 * Đọc vào số đỉnh, ma trận kề lưu vào trong mảng G.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void readData() {
File file = new File(getClass().getResource("GRAPH3.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
size = Integer.parseInt(reader.readLine());
G = new int[size+1][size+1];
for (int i = 1; i <= size; i++) {
String[] aLineOfMatrix = reader.readLine().split("\\s+");
for (int j = 1; j <= size; j++) {
G[i][j] = Integer.parseInt(aLineOfMatrix[j-1]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị kết quả.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void showResultD() {
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
System.out.print(D[i][j] + "  ");
}
System.out.println();
}
}

public void showResultP() {
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
System.out.print(P[i][j] + "  ");
}
System.out.println();
}
}

public void floyd() {
for (k = 1; k <= size; k++) {
for (int i = 1; i <= size; i++) {
for (int j = 1; j <= size; j++) {
if (D[i][j] != VO_CUC) {
if (D[i][j] > D[i][k] + D[k][j]) {
D[i][j] = D[i][k] + D[k][j];
P[i][j] = P[k][j];
}
} 
}
}
System.out.println("Vòng lặp thứ " + k);
System.out.println("Ma trận trọng số.");
showResultD();
System.out.println("Ma trận đường đi");
showResultP();
}
}

/**
 * @param args
 */
public static void main(String[] args) {
FloydAlgorithm obj = new FloydAlgorithm();
obj.readData();
obj.Initialize();
obj.showResultD();
obj.showResultP();
obj.floyd();
obj.showShortestPath(2, 3);
}

}

6. Cây khung
6.1. Duyệt cây

// Duyệt cây theo chiều sâu

package tree;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;


public class TREEDFSAglo {

/* Số đỉnh của đồ thị. */
private int size;
/* Mảng đánh dấu trạng thái của đỉnh được chưa xét hay chưa */
private boolean free[];
/* Ma trận kề hoặc ma trận trọng số của cây khung. */
private int G[][];
/* Số cạnh của cây */
private int numberEdge = 0;
/* Cây khung T */
private String T[];

/**
 * Đọc vào số đỉnh, ma trận kề lưu vào trong mảng G.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void readData() {
File file = new File(getClass().getResource("TREEDFS10.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
/* Số đỉnh của đồ thị. */
size = Integer.parseInt(reader.readLine());
/* Ma trận kề hoặc ma trận trọng số. */
G = new int[size][size];
/* Chuỗi lưu cây khung */
T = new String[size];
for(int i = 0; i < size; i++){
T[i] = "";
}
/* Ma trận đánh dấu trạng thái của đỉnh có được xét hay không. */
free = new boolean[size];
/* Thiết lập trạng thái của tất cả các đỉnh đều chưa được xét. */
for (int i = 0; i < size; i++)
free[i] = true;
/* Đọc dữ liệu từ file text và lưu vào ma trận kề hoặc ma trận trọng số G. */
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị kết quả.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void showResultMatixAdj() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + "  ");
}
System.out.println();
}
}

/**
 * Thủ tục duyệt cây theo chiều sâu.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void TREEDFS(int v) {
free[v] = false;
for (int u = 0; u < size; u++) {
if(free[u] && G[v][u] == 1){
free[u] = false;
T[numberEdge] = "("+ v + ", " + u + ")";
numberEdge++;
if(numberEdge == size-1){
return;
}else
TREEDFS(u);
}
}
}
/**
 * Hiển thị cây khung T.
 */
public void showTree(){
System.out.println("Cây khung T: ");
for(int i = 0; i <= numberEdge; i++){
System.out.print(T[i] + " ");
}
}
/**
 * Phương thức main.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public static void main(String[] args) {
TREEDFSAglo obj = new TREEDFSAglo();
obj.readData();
obj.showResultMatixAdj();
for(int i = 0; i < obj.size; i++){
if(obj.free[i])
obj.TREEDFS(i);
}
if(obj.numberEdge < obj.size-1)
System.out.println("Đồ thị không liên thông.");
else
obj.showTree();
}

}


// Duyệt cây theo chiều rộng

package tree;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;


public class TREEBFSAglo {

/* Số đỉnh của đồ thị. */
private int size;
/* Mảng đánh dấu trạng thái của đỉnh được chưa xét hay chưa */
private boolean free[];
/* Ma trận kề hoặc ma trận trọng số của cây khung. */
private int G[][];
/* Số cạnh của cây */
private int numberEdge = 0;
/* Cây khung T */
private String T[];
/* Khai báo QUEUE */
private int QUEUE[];

/**
 * Đọc vào số đỉnh, ma trận kề lưu vào trong mảng G.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void readData() {
File file = new File(getClass().getResource("TREEDFS10.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
/* Số đỉnh của đồ thị. */
size = Integer.parseInt(reader.readLine());
/* Ma trận kề hoặc ma trận trọng số. */
G = new int[size][size];
/*Mảng QUEUE chứa các đỉnh là đỉnh kề của đỉnh v*/
QUEUE = new int[size];
/* Chuỗi lưu cây khung */
T = new String[size];
for(int i = 0; i < size; i++){
T[i] = "";
}
/* Ma trận đánh dấu trạng thái của đỉnh có được xét hay không. */
free = new boolean[size];
/* Thiết lập trạng thái của tất cả các đỉnh đều chưa được xét. */
for (int i = 0; i < size; i++)
free[i] = true;
/* Đọc dữ liệu từ file text và lưu vào ma trận kề hoặc ma trận trọng số G. */
for (int i = 0; i < this.size; i++) {
String[] Line= reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Hiển thị kết quả.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void showResultMatixAdj() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + "  ");
}
System.out.println();
}
}

/**
 * Thủ tục duyệt cây theo chiều sâu.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void TREEBFS(int v) {
int u, first, last;
first = last = 0;
QUEUE[last] = v;
free[v] = false;
while (first <= last) {
u = QUEUE[first];
first = first + 1;
for (int i = 0; i < size; i++) {
if (free[i] && G[u][i] == 1) {
last = last + 1;
QUEUE[last] = i;
T[numberEdge] = "("+ u + ", " + i + ")";
numberEdge++;
free[i] = false;
if(numberEdge == size-1)
return;
}
}
}
}
/**
 * Hiển thị cây khung T.
 */
public void showTree(){
System.out.println("Cây khung T: ");
for(int i = 0; i <= numberEdge; i++){
System.out.print(T[i] + " ");
}
}
/**
 * Phương thức main.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public static void main(String[] args) {
TREEBFSAglo obj = new TREEBFSAglo();
obj.readData();
obj.showResultMatixAdj();
obj.TREEBFS(0);
if(obj.numberEdge < obj.size-1)
System.out.println("Đồ thị không liên thông.");
else
obj.showTree();
}

}

6.2. Tìm cây khung nhỏ nhất 
6.2.1. Thuật toán Kruskal


package tree;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class KruskalAlgo {

/* Số đỉnh của đồ thị. */
private int size;
/* Ma trận kề hoặc ma trận trọng số của cây khung. */
private int G[][];
/* Khai báo nhãn của đỉnh. */
private int lblVertex[];

/* Cây khung nhỏ nhất và số phần tử của cây. */
private Edges T[];
private int nT = 0;
/* Số phần tử của danh sách cạnh. */
private Edges lstEdge[];
private int nEdgeCount = 0;

/**
 * Đọc vào số đỉnh, ma trận kề lưu vào trong mảng G.
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void readData() {
File file = new File(getClass().getResource("PRIM.IN").getPath());
BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(file));
/* Số đỉnh của đồ thị. */
size = Integer.parseInt(reader.readLine());
/* Ma trận kề hoặc ma trận trọng số. */
G = new int[size][size];
/* Chuỗi lưu cây khung */
lblVertex = new int[size];
/* Khởi tạo mảng size phần tử */
T = new Edges[size];
/*
 * Đọc dữ liệu từ file text và lưu vào ma trận kề hoặc ma trận trọng
 * số G.
 */
for (int i = 0; i < this.size; i++) {
String[] Line = reader.readLine().split("\\s+");
for (int j = 0; j < this.size; j++) {
G[i][j] = Integer.parseInt(Line[j]);
}
}
} catch (FileNotFoundException ex) {
System.out.println("Lỗi không tìm thấy File.");
} catch (IOException ex) {
System.out.println("Lỗi vào/ra dữ liệu.");
} finally {
if (reader != null)
try {
reader.close();
} catch (IOException e) {
System.out.println("Lỗi đóng file.");
}
}
}

/**
 * Khởi tạo mảng cạnh
 */
public void initialize() {
lstEdge = new Edges[size * size];
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
if (G[i][j] != 0) {
Edges temp = new Edges();
temp.setU(i);
temp.setV(j);
temp.setW(G[i][j]);
lstEdge[nEdgeCount] = temp;
nEdgeCount++;
}
}
}
}

/**
 * Sắp xếp các cạnh theo thứ tự tăng dần của trọng số.
 */
public void sortListEdge(){
for(int i = 0; i < nEdgeCount - 1; i++){
for(int j = i+1; j < nEdgeCount; j++){
if(lstEdge[i].getW() > lstEdge[j].getW()){
swap(lstEdge[i], lstEdge[j]);
}
}
}
}
public void swap(Edges a, Edges b){
Edges temp = new Edges();
temp.setU(a.getU());
temp.setV(a.getV());
temp.setW(a.getW());
a.setU(b.getU());
a.setV(b.getV());
a.setW(b.getW());
b.setU(temp.getU());
b.setV(temp.getV());
b.setW(temp.getW());
}

public void showListEdges(){
System.out.println("Danh sách các cạnh là: ");
for(int i = 0; i <nEdgeCount; i++){
System.out.println(lstEdge[i].getU() +", " +lstEdge[i].getV() + ",: " + lstEdge[i].getW());
}
}
/**
 * Thuật toán tìm cây khung bé nhất sử dụng thuật toán PRIM.
 */
public void kruskal() {

}

/**
 * Hiển thị kết quả.<br>
 * 
 * @author Nguyen Xuan Minh
 * @since 13/04/2016
 */
public void showResultMatixAdj() {
System.out.println("Danh sách kề là: ");
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
System.out.print(G[i][j] + "  ");
}
System.out.println();
}
}

public void showCKNN() {
for (int i = 0; i < nT; i++) {
System.out.print("(" + T[i].getV() + ", " + T[i].getW() + ")");
}
}

/**
 * Chương trình chính
 * 
 * @param args
 *            (not use)
 */
public static void main(String[] args) {
KruskalAlgo obj = new KruskalAlgo();
obj.readData();
obj.showResultMatixAdj();
obj.initialize();
obj.showListEdges();
obj.sortListEdge();
obj.showListEdges();

}

}

class Edges {
/* Khai báo đỉnh thứ nhất */
private int u;

/* Khai báo đỉnh thứ nhất */
private int v;

/* Khai báo trọng số của cạnh */
private int w;

/**
 * Các phương thức set và get hải đỉnh của cạnh
 */
public int getV() {
return v;
}

public void setV(int v) {
this.v = v;
}

public int getW() {
return w;
}

public void setW(int w) {
this.w = w;
}

public int getU() {
return u;
}

public void setU(int u) {
this.u = u;
}

public Edges() {
this.u = 0;
this.v = 0;
this.w = 0;
}
}

6.2.2. Thuật toán Prim (Đang cập nhật)
Tags

0/Post a Comment/Comments

Post a Comment

Previous Post Next Post