Chương trình C++ kiểm tra đồ thị có hướng chứa chu trình Euler

Chu trình Euler (Euler cycle/circuit) là một đường đi; qua đó chúng ta có thể thăm mọi cạnh đúng một lần. Chúng ta có thể sử dụng cùng đỉnh nhiều lần. Chu trình Euler là một loại đặc biệt của đường đi Euler. Khi đỉnh bắt đầu của đường đi Euler cũng được nối với đỉnh kết thúc của đường đi đó, thì nó được gọi là Chu trình Euler.

Để kiểm tra xem một đồ thị có phải là Euler hay không, ta phải kiểm tra hai điều kiện:

• Đồ thị phải liên thông.
• Bậc vào (in-degree) và bậc ra (out-degree) của mỗi đỉnh phải bằng nhau.

Đầu vào — Ma trận kề của đồ thị.

Đầu ra — Tìm thấy Chu trình Euler

Thuật toán

traverse(u, visited)

Đầu vào — Đỉnh bắt đầu u và mảng visited để đánh dấu đỉnh đã thăm.

Đầu ra — Duyệt tất cả các đỉnh liên thông.

Bắt đầu
    Đánh dấu u là đã thăm
    Với mọi đỉnh v, nếu v kề với u
        Nếu v chưa được thăm
            traverse(v, visited)
Kết thúc

isConnected(graph)

Đầu vào — Đồ thị.

Đầu ra — True nếu đồ thị liên thông.

Bắt đầu
    Định nghĩa mảng visited cho tất cả đỉnh
    Với mọi đỉnh u trong đồ thị
        Đặt tất cả đỉnh là chưa thăm
        traverse(u, visited)
        Nếu còn đỉnh nào chưa thăm thì trả về false
    Trả về true
Kết thúc

isEulerCircuit(Graph)

Đầu vào — Đồ thị cho trước.

Đầu ra — True khi tìm thấy một chu trình Euler.

Bắt đầu
    Nếu isConnected() là false, trả về false
    Định nghĩa danh sách đếm cạnh vào và cạnh ra cho mỗi đỉnh
    Với mọi đỉnh i trong đồ thị
        sum := 0
        Với mọi đỉnh j kề với i
            Tăng cạnh vào cho đỉnh i
            Tăng sum
        Số cạnh ra của đỉnh i là sum
    Nếu danh sách cạnh vào và cạnh ra giống nhau, trả về true
    Ngược lại trả về false
Kết thúc

Mã ví dụ

#include <iostream>
#include <vector>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 1, 1},
    {1, 0, 0, 0, 0},
    {0, 0, 1, 0, 0}
};

void traverse(int u, bool visited[]) {
    visited[u] = true;
    for(int v = 0; v < NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v])
                traverse(v, visited);
        }
    }
}

bool isConnected() {
    bool *vis = new bool[NODE];
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false;
        traverse(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i])
                return false;
        }
    }
    return true;
}

bool isEulerCircuit() {
    if(isConnected() == false)
        return false;
    vector<int> inward(NODE, 0), outward(NODE, 0);
    for(int i = 0; i < NODE; i++) {
        int sum = 0;
        for(int j = 0; j < NODE; j++) {
            if(graph[i][j]) {
                inward[j]++;
                sum++;
            }
        }
        outward[i] = sum;
    }
    if(inward == outward)
        return true;
    return false;
}

int main() {
    if(isEulerCircuit())
        cout << "Tìm thấy Chu trình Euler.";
    else
        cout << "Không có Chu trình Euler.";
}

Kết quả đầu ra

Tìm thấy Chu trình Euler.