Kiểm tra đồ thị có hướng chứa đường đi Euler (Eulerian Path)

Đường đi Euler (Eulerian path) đi qua mỗi cạnh đúng một lần. Đồ thị có hướng có đường đi Euler khi:

1. Đồ thị liên thông.
2. Tồn tại đỉnh a với out_deg = in_deg + 1 (đỉnh bắt đầu).
3. Tồn tại đỉnh b với in_deg = out_deg + 1 (đỉnh kết thúc).
4. Các đỉnh còn lại: in_deg = out_deg.

Thuật toán

1. Kiểm tra liên thông (DFS/BFS).
2. Tính in-degree và out-degree cho mỗi đỉnh.
3. Áp dụng điều kiện trên.

Ví dụ code (ma trận kề 5x5)

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

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

void dfs(int u, vector<bool>& vis) {
    vis[u] = true;
    for (int v=0; v
Kết quả
Có đường đi Euler