Đăng Nhập

Vui lòng khai báo chính xác tên truy cập và mật khẩu!

Quên mật khẩu?

Lý thuyết C++ | Giải thuật đồ thị cài đặt bằng C++

Share
    Xếp
    avatar

    Giới tính : Nữ

    Tuổi : 25

    Đến từ : HCM

    Ngày Tham gia : 13/06/2011

    Tổng số bài gửi : 380

    #1

     on Tue Oct 11, 2011 8:50 pm

    Box này mình sẽ post những cài đặt đối với những giải thuật cơ bản bằng C++, vì đa số các giải thuật này đều được cài đặt bằng Pascal nên cũng gây không ít khó khăn cho những bạn mới học khi muốn tìm hiểu giải thuật mà không biết Pascal T_T. Mình sẽ demo output luôn cho các bạn tiện theo dõi, nếu có bug thì các bạn cứ thoải mái report vì mình cũng không dám nói mình viết là perfect ~~!
    Lưu ý về phần lý thuyết mình sẽ không nêu ra ở đây vì các bạn có thể dễ dàng tìm thấy trên wikipedia.org. Nên mình chỉ để lại 1 link lý thuyết cho những bạn nào muốn tìm hiểu lại thôi.

    Mở đầu sẽ là thuật toán tìm kiếm theo chiều rộng trên đồ thị :
    Breadth First Search :

    Lý thuyết :
    Code:
    [You must be registered and logged in to see this link.]
    Cài đặt bằng ngôn ngữ C++ :
    C++ Code:
    Lựa chọn code | Ẩn/Hiện code

    #include
    #include

    using std::cout;
    using std::endl;
    using std::endl;
    using std::cin;

    const int maxx = 20;

    void Read_input_from_user(bool grid[][maxx], int vertices)
    {
    int u, v;
    for(int x = 0; x < vertices; ++x)
    {
    cout << "Enter u : \t";
    cin >> u;
    u--;
    cout << "Enter v : \t";
    cin >> v;
    v--;
    grid[u][v] = true;
    grid[v][u] = true;
    cout << "---------------------\n";
    }
    }

    void Breadth_first_search(std::queue<int> &Q, std::vector<int> &trace,
    bool grid[][maxx], int start, int nodes)
    {
    int u;
    Q.push(start);
    trace[start] = -1;
    do{
    u = Q.front();
    Q.pop();
    for(int v = 0; v < nodes; ++v)
    {
    if((grid[u][v] == true) && trace[v] == 0)
    {
    Q.push(v);
    trace[v] = u;
    }
    }
    }while(!Q.empty());
    }

    void Trace_result(std::vector<int> &trace, int start, int end, int nodes)
    {
    cout << "From _nodes" << start + 1 << " you can visit :\n";
    for(int v = 0; v < nodes; ++v)
    {
    if(trace[v] != 0)
    {
    cout << " _nodes : " << v + 1 << " , ";
    }
    }

    cout << "\n--------------------------------------------\n";
    cout << "The path from " << start + 1 << " to " << end + 1 << '\n';

    if(trace[end] == 0){
    cout << "Unavailable.! to go to from " << end + 1
    << " to -> " << start + 1 << '\n';
    }
    else{
    while(end != start)
    {
    cout << end + 1 << "<-";
    end = trace[end];
    }
    cout << start + 1 << endl;
    }

    }


    int main()
    {
    //Initialization
    std::vector<int> trace(maxx, 0);
    std::queue<int> Q;
    bool grid[maxx][maxx] = {false};

    int nodes, vertices;
    cout << "Please input the number of Node : \n";
    cin >> nodes;
    cout << "Please input the number of Vertices : \n";
    cin >> vertices;

    //Set value for all vertices.
    Read_input_from_user(grid, vertices);

    //Read the necessary path
    int starting_position, finishing_position;
    cout << "Please Input the Starting Node : \n";
    cin >> starting_position;
    cout << "Please Input the Finishing Node : \n";
    cin >> finishing_position;
    //Decrease to fit with index of C++ start from 0->size-1
    starting_position--;
    finishing_position--;
    //Algorithm starts
    Breadth_first_search(Q, trace, grid, starting_position, nodes);
    Trace_result(trace, starting_position, finishing_position, nodes);

    return 0;
    }



    Demo :

    Xếp
    avatar

    Giới tính : Nữ

    Tuổi : 25

    Đến từ : HCM

    Ngày Tham gia : 13/06/2011

    Tổng số bài gửi : 380

    #2

     on Tue Oct 11, 2011 8:52 pm

    huật toán kế tiếp cũng là 1 thuật toán trên đồ thì "Tìm kiếm theo chiều rộng ". DFS khác với BFS ở chỗ nó dùng đệ qui để tìm các đỉnh cần tới, trong khi BFS thì sử dụng cấu trúc dữ liệu hàng đợi.
    Depth First Search :
    Lý thuyết
    Code:
    [You must be registered and logged in to see this link.]
    Cài đặt bằng ngôn ngữ C++
    C++ Code:
    Lựa chọn code | Ẩn/Hiện code

    /*Bài toán duyêt dinh cua dò thi :

    Input : file van ban path.inp trong dó :
    - Dòng 1 chu só dinh n ( n <= 100 ), só canh m cua dò thi và dinh xuát phát s, dinh ket thúc f cách nhau 1 dáu cách.
    - m dòng tiép theo, mõi dòng có dang 2 só nguyên duong u và v cách nhau 1 dáu cách, the hien canh nói dinh u và v trong dò thi.
    Output :
    - Danh sách các dinh có the dén dc s.
    - Duong di tù s->f.

    Ví du:

    Path.inp: Path.out

    ############ ###########################
    # 8 7 1 5 # # #
    # # # From 1 you can visit #
    # 1 2 # # 1, 2, 3, 4, 5 #
    # 1 3 # # The path from 1 -> 5: #
    # 2 3 # # 5 <- 3 <- 2 <- 1 #
    # 2 4 # # #
    # 3 5 # ###########################
    # 4 6 #
    # 7 8 #
    ############

    */

    #include
    #include

    using std::cout;
    using std::cin;
    using std::endl;

    const int maxx = 20;

    void Read_input_from_user(bool grid[][maxx], int vertices)
    {
    int u, v;
    for(int x = 0; x < vertices; ++x)
    {
    cout << "Enter u : \t";
    cin >> u;
    u--;
    cout << "Enter v : \t";
    cin >> v;
    v--;
    grid[u][v] = true;
    grid[v][u] = true;
    cout << "---------------------\n";
    }
    }

    void Depth_first_search(bool grid[][maxx], std::vector<int> &trace,
    int nodes, int u)
    {
    for(int v = 0; v < nodes; ++v)
    {
    if((grid[u][v] == true) && (trace[v] == 0))
    {
    trace[v] = u;
    //recursive step
    Depth_first_search(grid, trace, nodes, v);
    }
    }
    }

    void Trace_result(std::vector<int> &trace, int start, int end, int nodes)
    {
    cout << "From _nodes" << start + 1 << " you can visit :\n";
    for(int v = 0; v < nodes; ++v)
    {
    if(trace[v] != 0)
    {
    cout << " _nodes : " << v + 1 << " , ";
    }
    }

    cout << "\n--------------------------------------------\n";
    cout << "The path from " << start + 1 << " to " << end + 1 << '\n';

    if(trace[end] == 0){
    cout << "Unavailable.! to go to from " << end + 1
    << " to -> " << start + 1 << '\n';
    }
    else{
    while(end != start)
    {
    cout << end + 1 << "<-";
    end = trace[end];
    }
    cout << start + 1 << endl;
    }
    }

    int main()
    {
    bool grid[maxx][maxx] = { false };
    std::vector<int> trace(maxx, 0);
    int nodes, vertices;
    cout << "Please input the number of Node : \n";
    cin >> nodes;
    cout << "Please input the number of Vertices : \n";
    cin >> vertices;

    //Set value for all vertices.
    Read_input_from_user(grid, vertices);

    //Read the necessary path
    int starting_position, finishing_position;
    cout << "Please Input the Starting Node : \n";
    cin >> starting_position;
    cout << "Please Input the Finishing Node : \n";
    cin >> finishing_position;
    //Decrease to fit with index of C++ start from 0->size-1
    starting_position--;
    finishing_position--;

    Depth_first_search(grid, trace, nodes, starting_position);
    Trace_result(trace, starting_position, finishing_position, nodes);
    return 0;
    }



    Demo :



    Đã được chỉnh sửa lần cuối bởi rox_rook : 02-03-2008 lúc 05:13 AM.
    Xếp
    avatar

    Giới tính : Nữ

    Tuổi : 25

    Đến từ : HCM

    Ngày Tham gia : 13/06/2011

    Tổng số bài gửi : 380

    #3

     on Tue Oct 11, 2011 8:52 pm

    Thuật toán tiếp theo cũng là 1 thuật toán trên đồ thị, nó có tên gọi là Roy_Warshall, tìm ra những đồ thị liên thông với nhau
    Roy_Warshall
    Lý thuyết
    Code:
    [You must be registered and logged in to see this link.]

    Chương trình cài đặt bằng C++

    C++ Code:
    Lựa chọn code | Ẩn/Hiện code

    /*Roy-Warshall algorithm*/
    #include
    #include
    using std::cout;
    using std::endl;
    using std::cin;

    const int maxx = 20;

    void Read_input_from_user(bool grid[][maxx], int vertices, int nodes)
    {
    int u, v;
    for(int y = 0; y < nodes; ++y)
    {
    grid[y][y] = true;
    }

    for(int x = 0; x < vertices; ++x)
    {
    cout << "Enter u : \t";
    cin >> u;
    u--;
    cout << "Enter v : \t";
    cin >> v;
    v--;
    grid[u][v] = true;
    grid[v][u] = true;
    cout << "---------------------\n";
    }
    cout << endl << endl;
    }

    void show_grid(std::ostream &oss, bool grid[][maxx], int nodes)
    {
    oss << "\n[Graph Generation]\n";
    oss << '\n';
    for(int x = 0; x < nodes; ++x)
    {
    for(int y = 0; y < nodes; ++y)
    {
    oss << grid[x][y] << std::setw(2);
    }
    oss << '\n';
    }
    oss << endl << endl;
    }

    void Roy_Warshall_algorithm(bool grid[][maxx], bool free[],
    int vertices, int nodes)
    {
    for(int bridge = 0; bridge < nodes; ++bridge)
    {
    for(int u = 0; u < nodes; ++u)
    {
    for(int v = 0; v < nodes; ++v)
    {
    if(grid[u][bridge] && grid[bridge][v])
    {
    grid[u][v] = true;
    }
    }
    }
    }
    show_grid(cout, grid, nodes);
    int component = 0;
    for(int pos = 0; pos < nodes; ++pos)
    {
    if(free[pos] == true)
    {
    component++;
    cout << "Connected Component " << component << " : \n";
    for(int _neighbor = 0; _neighbor < nodes; ++_neighbor)
    {
    if(grid[pos][_neighbor])
    {
    cout << _neighbor + 1 << " , ";
    free[_neighbor] = false;
    }
    }
    cout << "\n------------------------------------\n";
    }
    }
    }

    int main()
    {
    int vertices, nodes;
    bool grid[maxx][maxx] = {0};
    bool free[maxx] = {};
    for(int x = 0; x < maxx; ++x)
    {
    free[x] = true;
    }
    cout << "Please input the number of Node : \n";
    cin >> nodes;
    cout << "Please input the number of Vertices : \n";
    cin >> vertices;
    Read_input_from_user(grid, vertices, nodes);
    Roy_Warshall_algorithm(grid, free, vertices, nodes);
    return 0;
    }



    Demo
    Code:
    Please input the number of Node :
    12
    Please input the number of Vertices :
    9
    Enter u : 1
    Enter v : 3
    ---------------------
    Enter u : 1
    Enter v : 4
    ---------------------
    Enter u : 1
    Enter v : 5
    ---------------------
    Enter u : 2
    Enter v : 4
    ---------------------
    Enter u : 6
    Enter v : 7
    ---------------------
    Enter u : 6
    Enter v : 8
    ---------------------
    Enter u : 9
    Enter v : 10
    ---------------------
    Enter u : 11
    Enter v : 12
    ---------------------
    Enter u : 9
    Enter v : 11
    ---------------------



    [Graph Generation]

    1 1 1 1 1 0 0 0 0 0 0 0
    1 1 1 1 1 0 0 0 0 0 0 0
    1 1 1 1 1 0 0 0 0 0 0 0
    1 1 1 1 1 0 0 0 0 0 0 0
    1 1 1 1 1 0 0 0 0 0 0 0
    0 0 0 0 0 1 1 1 0 0 0 0
    0 0 0 0 0 1 1 1 0 0 0 0
    0 0 0 0 0 1 1 1 0 0 0 0
    0 0 0 0 0 0 0 0 1 1 1 1
    0 0 0 0 0 0 0 0 1 1 1 1
    0 0 0 0 0 0 0 0 1 1 1 1
    0 0 0 0 0 0 0 0 1 1 1 1


    Connected Component 1 :
    1 , 2 , 3 , 4 , 5 ,
    ------------------------------------
    Connected Component 2 :
    6 , 7 , 8 ,
    ------------------------------------
    Connected Component 3 :
    9 , 10 , 11 , 12 ,
    ------------------------------------
    Press any key to continue . . .

    #4