Đă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:
    [You must be registered and logged in to see this link.] | [You must be registered and logged in to see this link.]

    #include
    #include

    using std::[You must be registered and logged in to see this link.];
    using std::endl;
    using std::endl;
    using std::[You must be registered and logged in to see this link.];

    const int maxx = 20;

    void Read_input_from_user(bool grid[][maxx], int vertices)
    {
    int u, v;
    for(int x = 0; x < vertices; ++x)
    {
    [You must be registered and logged in to see this link.] << "Enter u : \t";
    [You must be registered and logged in to see this link.] >> u;
    u--;
    [You must be registered and logged in to see this link.] << "Enter v : \t";
    [You must be registered and logged in to see this link.] >> v;
    v--;
    grid[u][v] = true;
    grid[v][u] = true;
    [You must be registered and logged in to see this link.] << "---------------------\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)
    {
    [You must be registered and logged in to see this link.] << "From _nodes" << start + 1 << " you can visit :\n";
    for(int v = 0; v < nodes; ++v)
    {
    if(trace[v] != 0)
    {
    [You must be registered and logged in to see this link.] << " _nodes : " << v + 1 << " , ";
    }
    }

    [You must be registered and logged in to see this link.] << "\n--------------------------------------------\n";
    [You must be registered and logged in to see this link.] << "The path from " << start + 1 << " to " << end + 1 << '\n';

    if(trace[end] == 0){
    [You must be registered and logged in to see this link.] << "Unavailable.! to go to from " << end + 1
    << " to -> " << start + 1 << '\n';
    }
    else{
    while(end != start)
    {
    [You must be registered and logged in to see this link.] << end + 1 << "<-";
    end = trace[end];
    }
    [You must be registered and logged in to see this link.] << start + 1 << endl;
    }

    }


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

    int nodes, vertices;
    [You must be registered and logged in to see this link.] << "Please input the number of Node : \n";
    [You must be registered and logged in to see this link.] >> nodes;
    [You must be registered and logged in to see this link.] << "Please input the number of Vertices : \n";
    [You must be registered and logged in to see this link.] >> vertices;

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

    //Read the necessary path
    int starting_position, finishing_position;
    [You must be registered and logged in to see this link.] << "Please Input the Starting Node : \n";
    [You must be registered and logged in to see this link.] >> starting_position;
    [You must be registered and logged in to see this link.] << "Please Input the Finishing Node : \n";
    [You must be registered and logged in to see this link.] >> 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:
    [You must be registered and logged in to see this link.] | [You must be registered and logged in to see this link.]

    /*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::[You must be registered and logged in to see this link.];
    using std::[You must be registered and logged in to see this link.];
    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)
    {
    [You must be registered and logged in to see this link.] << "Enter u : \t";
    [You must be registered and logged in to see this link.] >> u;
    u--;
    [You must be registered and logged in to see this link.] << "Enter v : \t";
    [You must be registered and logged in to see this link.] >> v;
    v--;
    grid[u][v] = true;
    grid[v][u] = true;
    [You must be registered and logged in to see this link.] << "---------------------\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)
    {
    [You must be registered and logged in to see this link.] << "From _nodes" << start + 1 << " you can visit :\n";
    for(int v = 0; v < nodes; ++v)
    {
    if(trace[v] != 0)
    {
    [You must be registered and logged in to see this link.] << " _nodes : " << v + 1 << " , ";
    }
    }

    [You must be registered and logged in to see this link.] << "\n--------------------------------------------\n";
    [You must be registered and logged in to see this link.] << "The path from " << start + 1 << " to " << end + 1 << '\n';

    if(trace[end] == 0){
    [You must be registered and logged in to see this link.] << "Unavailable.! to go to from " << end + 1
    << " to -> " << start + 1 << '\n';
    }
    else{
    while(end != start)
    {
    [You must be registered and logged in to see this link.] << end + 1 << "<-";
    end = trace[end];
    }
    [You must be registered and logged in to see this link.] << start + 1 << endl;
    }
    }

    int main()
    {
    bool grid[maxx][maxx] = { false };
    std::vector<int> trace(maxx, 0);
    int nodes, vertices;
    [You must be registered and logged in to see this link.] << "Please input the number of Node : \n";
    [You must be registered and logged in to see this link.] >> nodes;
    [You must be registered and logged in to see this link.] << "Please input the number of Vertices : \n";
    [You must be registered and logged in to see this link.] >> vertices;

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

    //Read the necessary path
    int starting_position, finishing_position;
    [You must be registered and logged in to see this link.] << "Please Input the Starting Node : \n";
    [You must be registered and logged in to see this link.] >> starting_position;
    [You must be registered and logged in to see this link.] << "Please Input the Finishing Node : \n";
    [You must be registered and logged in to see this link.] >> 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:
    [You must be registered and logged in to see this link.] | [You must be registered and logged in to see this link.]

    /*Roy-Warshall algorithm*/
    #include
    #include
    using std::[You must be registered and logged in to see this link.];
    using std::endl;
    using std::[You must be registered and logged in to see this link.];

    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)
    {
    [You must be registered and logged in to see this link.] << "Enter u : \t";
    [You must be registered and logged in to see this link.] >> u;
    u--;
    [You must be registered and logged in to see this link.] << "Enter v : \t";
    [You must be registered and logged in to see this link.] >> v;
    v--;
    grid[u][v] = true;
    grid[v][u] = true;
    [You must be registered and logged in to see this link.] << "---------------------\n";
    }
    [You must be registered and logged in to see this link.] << 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([You must be registered and logged in to see this link.], grid, nodes);
    int component = 0;
    for(int pos = 0; pos < nodes; ++pos)
    {
    if(free[pos] == true)
    {
    component++;
    [You must be registered and logged in to see this link.] << "Connected Component " << component << " : \n";
    for(int _neighbor = 0; _neighbor < nodes; ++_neighbor)
    {
    if(grid[pos][_neighbor])
    {
    [You must be registered and logged in to see this link.] << _neighbor + 1 << " , ";
    free[_neighbor] = false;
    }
    }
    [You must be registered and logged in to see this link.] << "\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;
    }
    [You must be registered and logged in to see this link.] << "Please input the number of Node : \n";
    [You must be registered and logged in to see this link.] >> nodes;
    [You must be registered and logged in to see this link.] << "Please input the number of Vertices : \n";
    [You must be registered and logged in to see this link.] >> 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