Từ 1 tới 7 trên tổng số 7 kết quả

Đề tài: Lý thuyết đồ thị với C++

  1. #1
    Ngày gia nhập
    04 2008
    Nơi ở
    Hà Nội
    Bài viết
    0

    Angry Lý thuyết đồ thị với C++

    Mình đang cần các Modul chương trình cài đặt thuật toán của đồ thị Euler và Hamilton. Mấy bài này thày giáo mình dạy cứ như sinh viên biêt hết rồi nên bây giờ làm BTL khổ quá.
    Bạn nào có share cho mình nhé.
    Cảm ơn các bạn!

  2. #2
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Chu trình Euler thì Ở đây, nhưng ht code theo C, bạn chuyển lại chút nha, còn Hamilton thì bạn coding cho quen.
    Đã được chỉnh sửa lần cuối bởi Forlorn_hope : 12-04-2008 lúc 03:11 PM. Lý do: Cho gọn lại
    Không biết ghi gì luôn ...

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Tớ học ở Huflit, nhưng lại không đi học nên mấy cái này cũng mù trời đông. Chắc cũng phải học lại mấy cái này thêm cho vững. Có gì nhờ Ht mới được ( HT Mobile ok ?) .

  4. #4
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Đây cậu, Hamilton của cậu :
    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3.  
    4. const int MAX_VERTICES = 100;
    5. static int count = 0;
    6.  
    7. void print_hamilton_circut(const std::vector<int>& hamilton);
    8. void read_valid_path(std::ostream& oss, std::istream& iss,
    9.                      bool valid_path[][MAX_VERTICES], int paths);
    10. void make_all_vertex_true(bool visited[], int vertices);
    11. void find_hamilton_path(int to, int all_paths,
    12.                         bool valid_path[][MAX_VERTICES],
    13.                         bool visited[],
    14.                         std::vector<int>& hamilton);
    15.  
    16. void read_valid_path(std::ostream& oss, std::istream& iss,
    17.                      bool valid_path[][MAX_VERTICES], int paths)
    18. {
    19.   int from, to;
    20.   int index = 0;
    21.   while(index < paths){
    22.     oss << " [] from vertex : ";
    23.     iss >> from;
    24.     oss << "      ==> to vertex : ";
    25.     iss >> to;
    26.     valid_path[from - 1][to - 1] = true;
    27.     valid_path[to - 1][from - 1] = true;
    28.     index++;
    29.   }
    30. }
    31.  
    32. void print_hamilton_circut(const std::vector<int>& hamilton)
    33. {
    34.   std::cout << "\n [ Hamilton path ] \n";
    35.   for(std::vector<int>::const_iterator it = hamilton.begin();
    36.       it != hamilton.end(); ++it)
    37.   {
    38.     std::cout << *it + 1 << " -> ";
    39.   }
    40. }
    41.  
    42. void find_hamilton_path(int to, int cities,
    43.                         bool valid_path[][MAX_VERTICES],
    44.                         bool visited[],
    45.                         std::vector<int>& hamilton){
    46.   int from;
    47.   for(from = 0; from < cities; ++from){
    48.     if(visited[from] && valid_path[hamilton[to - 1]][from]){
    49.       hamilton[to] = from;
    50.       if(to < cities - 1){
    51.         visited[from] = false;
    52.         find_hamilton_path(to + 1,
    53.                            cities,
    54.                            valid_path,
    55.                            visited,
    56.                            hamilton);
    57.         visited[from] = true;
    58.       }
    59.       else{
    60.         if(valid_path[from][hamilton[0]]){
    61.           print_hamilton_circut(hamilton);
    62.           count++;
    63.         }
    64.       }
    65.     }
    66.   }
    67. }
    68.  
    69. void make_all_vertex_true(bool visited[], int vertices){
    70.   for(int x = 0; x < vertices; ++x){
    71.     visited[x] = true;
    72.   }
    73.  
    74. }
    75.  
    76. void base_case(std::vector<int>& hamilton, bool visited[]){
    77.   hamilton[0] = 0;
    78.   visited[0] = false;
    79. }
    80.  
    81.  
    82. int main(){
    83.   int vertices;
    84.   int edges;
    85.   std::cout << "\nHow many vertices : ";
    86.   std::cin >> vertices;
    87.   std::cout << "\nHow many edges : ";
    88.   std::cin >> edges;
    89.  
    90.   bool valid_path[MAX_VERTICES][MAX_VERTICES] = {0};
    91.   bool visited[MAX_VERTICES];
    92.  
    93.   std::vector<int> hamilton(vertices, 0);
    94.  
    95.   make_all_vertex_true(visited, vertices);
    96.  
    97.   read_valid_path(std::cout, std::cin, valid_path, edges);
    98.  
    99.   base_case(hamilton, visited);
    100.  
    101.   find_hamilton_path(1, vertices, valid_path, visited, hamilton);
    102.  
    103.   if(count == 0){
    104.     std::cout << "Oops...there's no such hamilton path existed.\n";
    105.   }
    106.  
    107.   return 0;
    108. }

  5. #5
    Ngày gia nhập
    12 2006
    Nơi ở
    US
    Bài viết
    1,917

    Code này đỉnh hơn đây, tha hồ cho cậu enjoy
    C++ Code:
    1. #include <iostream>
    2. #include <fstream>
    3. #include <string>
    4. #include <vector>
    5. using namespace std;
    6. vector<int> procedure_1(vector< vector<int> > graph, vector<int> path);
    7. vector<int> procedure_2(vector< vector<int> > graph, vector<int> path);
    8. vector<int> procedure_2b(vector< vector<int> > graph, vector<int> path);
    9. vector<int> procedure_2c(vector< vector<int> > graph, vector<int> path);
    10. vector<int> procedure_3(vector< vector<int> > graph, vector<int> path);
    11. vector<int> sort(vector<vector<int> > graph);
    12. vector<vector<int> >
    13.             reindex(vector<vector<int> > graph, vector<int> index);
    14. ifstream infile ("graph.txt");     //Input file
    15. ofstream outfile("paths.txt");     //Output file
    16.  
    17. int main()
    18. {
    19.  int i, j, k, n, vertex, edge;
    20.  infile>>n;                        //Read number of vertices
    21.  vector< vector<int> > graph;       //Read adjacency matrix of graph
    22.  for(i=0; i<n; i++)
    23.  {
    24.   vector<int> row;
    25.   for(j=0; j<n; j++)
    26.   {
    27.    infile>>edge;
    28.    row.push_back(edge);
    29.   }
    30.   graph.push_back(row);
    31.  }
    32.  
    33.  vector<int> index=sort(graph);
    34.  graph=reindex(graph,index);
    35.  
    36.  for(vertex=0; vertex<n; vertex++)  //Loop through all vertices
    37.  {
    38.   vector<int> path;
    39.   path.push_back(vertex);           //Select initial vertex
    40.   path=procedure_1(graph,path);     //Part I
    41.   path=procedure_2(graph,path);     //Part II
    42.   k=path.size();
    43.   if(k<n)   {path=procedure_2b(graph,path); k=path.size();}
    44.   if(k<n)   {path=procedure_2c(graph,path); k=path.size();}
    45.   if(k<n) outfile<<"Path("<<k<<"): ";
    46.   else outfile<<"Hamiltonian Tour: ";//Part III
    47.   for(i=0; i<path.size(); i++) outfile<<index[path[i]]+1<<" ";
    48.   outfile<<endl;
    49.   if(k==n)
    50.   {
    51.    vector<int> circuit_maker=procedure_3(graph,path);
    52.    if(!circuit_maker.empty())
    53.    {
    54.     for(j=0; j<circuit_maker.size(); j++)
    55.     {
    56.      outfile<<"Hamiltonian Circuit:\t";
    57.      for(k=0; k<=circuit_maker[j]; k++)
    58.       outfile<<index[path[k]]+1<<" ";
    59.      for(k=n-1; k>circuit_maker[j]; k--)
    60.       outfile<<index[path[k]]+1<<" ";
    61.      outfile<<endl;
    62.     }
    63.    }
    64.    outfile<<endl;
    65.   }
    66.  }
    67.  cout<<"See paths.txt for results."<<endl;
    68.   system("PAUSE");
    69.   return 0;
    70. }
    71.  
    72. vector<int> procedure_1(vector< vector<int> > graph, vector<int> path)
    73. {
    74.  int i, j, k, n=graph.size();
    75.  vector<int> extended_path;
    76.  vector<int> visited;
    77.  for(i=0; i<n; i++)
    78.   visited.push_back(0);
    79.  int present;
    80.  for(i=0; i<path.size(); i++)
    81.  {
    82.   present=path[i];
    83.   visited[present]=1;
    84.   extended_path.push_back(present);
    85.  }
    86.  for(k=0; k<n; k++)
    87.  {
    88.   vector<int> neighbor;
    89.   for(i=0; i<n; i++)
    90.    if(graph[present][i]==1 && visited[i]==0)
    91.     neighbor.push_back(i);
    92.    if(!neighbor.empty())
    93.    {
    94.     int choice=neighbor[0];
    95.     int minimum=n;
    96.     for(i=0; i<neighbor.size(); i++)
    97.     {
    98.      vector<int> next_neighbor;
    99.      for(j=0; j<n; j++)
    100.       if(graph[neighbor[i]][j]==1 && visited[j]==0)
    101.        next_neighbor.push_back(j);
    102.       int eta=next_neighbor.size();
    103.       if(eta<minimum)
    104.       {
    105.        choice=neighbor[i];
    106.        minimum=eta;
    107.       }
    108.     }
    109.     present=choice;
    110.     visited[present]=1;
    111.     extended_path.push_back(present);
    112.    }
    113.    else break;
    114.  }
    115.  return extended_path;
    116. }
    117.  
    118. vector<int> procedure_2(vector< vector<int> > graph, vector<int> path)
    119. {
    120.  int i, j, k, n=graph.size();
    121.  bool quit=false;
    122.  while(quit!=true)
    123.  {
    124.  int m=path.size(), inlet=-1, outlet=-1;
    125.   vector<int> neighbor;
    126.   for(i=0; i<path.size(); i++)
    127.    if(graph[path[m-1]][path[i]]==1) neighbor.push_back(i);
    128.    vector<int> unvisited;
    129.    for(i=0; i<n; i++)
    130.    {
    131.     bool outside=true;
    132.     for(j=0; j<path.size(); j++)
    133.      if(i==path[j]) outside=false;
    134.      if(outside==true) unvisited.push_back(i);
    135.    }
    136.    if((!unvisited.empty()) && (!neighbor.empty()))
    137.    {
    138.     int maximum=0;
    139.     for(i=0; i<neighbor.size(); i++)
    140.      for(j=0; j<unvisited.size(); j++)
    141.       if(graph[path[neighbor[i]+1]][unvisited[j]]==1)
    142.       {
    143.        vector<int> next_neighbor;
    144.        for(k=0; k<unvisited.size(); k++)
    145.        if(graph[unvisited[j]][unvisited[k]]==1)
    146.          next_neighbor.push_back(unvisited[k]);
    147.        int eta=next_neighbor.size();
    148.        if(eta>=maximum)
    149.         {
    150.          inlet=neighbor[i];
    151.          outlet=unvisited[j];
    152.          maximum=eta;
    153.         }
    154.       }
    155.    }
    156.    vector<int> extended_path;
    157.    if(inlet!=-1 && outlet!=-1)
    158.    {
    159.     for(i=0; i<=inlet; i++)
    160.      extended_path.push_back(path[i]);
    161.     for(i=path.size()-1; i>inlet; i--)
    162.      extended_path.push_back(path[i]);
    163.     extended_path.push_back(outlet);
    164.    }
    165.    if(!extended_path.empty()) path=extended_path;
    166.    if(m<path.size()) path=procedure_1(graph,path);
    167.    else quit=true;
    168.  }
    169.  return path;
    170. }
    171.  
    172. vector<int> procedure_2b(vector< vector<int> > graph, vector<int> path)
    173. {
    174.  int i, j, k, l, p, n=graph.size();
    175.  bool quit=false;
    176.  while(quit!=true)
    177.  {
    178.   vector<int> extended_path;
    179.   int m=path.size();
    180.   vector<int> unvisited;
    181.   for(i=0; i<n; i++)
    182.   {
    183.     bool outside=true;
    184.     for(j=0; j<path.size(); j++)
    185.      if(i==path[j]) outside=false;
    186.     if(outside==true) unvisited.push_back(i);
    187.   }
    188.   bool big_check=false;
    189.   for(i=0; i<path.size(); i++)
    190.   {
    191.     for(j=0; j<unvisited.size(); j++)
    192.     {
    193.      if(graph[unvisited[j]][path[i]]==1)
    194.      {
    195.        vector<int> temp_path;
    196.        temp_path.push_back(unvisited[j]);
    197.        vector<int> temp_extended_path;
    198.        vector<int> temp_visited;
    199.        for(l=0; l<n; l++)
    200.        temp_visited.push_back(0);
    201.        int present;
    202.        for(l=0; l<temp_path.size(); l++)
    203.        {
    204.        present=temp_path[l];
    205.         temp_visited[present]=1;
    206.         temp_extended_path.push_back(present);
    207.        }
    208.        for(l=0; l<n; l++)
    209.        {
    210.        bool unfound=true;
    211.        for(k=0; k<unvisited.size(); k++)
    212.         if(l==unvisited[k]) unfound=false;
    213.        if(unfound==true) temp_visited[l]=1;
    214.        }
    215.        for(l=0; l<n; l++)
    216.        {
    217.         vector<int> neighbor;
    218.        for(l=0; l<n; l++)
    219.        if(graph[present][l]==1 && temp_visited[l]==0)
    220.         neighbor.push_back(l);
    221.        if(!neighbor.empty())
    222.         {
    223.          int choice=neighbor[0];
    224.          int minimum=n;
    225.          for(l=0; l<neighbor.size(); l++)
    226.           {
    227.            vector<int> next_neighbor;
    228.           for(k=0; k<n; k++)
    229.            if(graph[neighbor[l]][k]==1 && temp_visited[k]==0)
    230.             next_neighbor.push_back(k);
    231.            int eta=next_neighbor.size();
    232.            if(eta<minimum)
    233.             {
    234.              choice=neighbor[l];
    235.              minimum=eta;
    236.             }
    237.           }
    238.           present=choice;
    239.           temp_visited[present]=1;
    240.          temp_extended_path.push_back(present);
    241.         }
    242.        else break;
    243.      }
    244.      int last_vertex=temp_extended_path[temp_extended_path.size()-1];
    245.      int vj;
    246.      bool check=false;
    247.      while(check==false && !temp_extended_path.empty())
    248.      {
    249.      for(p=path.size()-2; p>i; p--)
    250.      {
    251.       if(graph[path[p]][last_vertex]==1
    252.          && graph[path[i+1]][path[p+1]]==1)
    253.       {
    254.        check=true;
    255.        vj=p;
    256.        break;
    257.       }
    258.      }
    259.      if(check==false)
    260.      {
    261.       temp_extended_path.pop_back();
    262.       last_vertex=temp_extended_path[temp_extended_path.size()-1];
    263.      }
    264.      }
    265.      if(check==true)
    266.      {
    267.       vector<int> temp;
    268.       for(p=0; p<=i; p++)
    269.       temp.push_back(path[p]);
    270.       for(p=0; p<temp_extended_path.size(); p++)
    271.       temp.push_back(temp_extended_path[p]);
    272.       for(p=vj; p>i; p--)
    273.       temp.push_back(path[p]);
    274.       for(p=vj+1; p<path.size(); p++)
    275.       temp.push_back(path[p]);
    276.       temp_extended_path=temp;
    277.       big_check=true;
    278.       extended_path=temp_extended_path;
    279.      }
    280.      }
    281.     }
    282.      if(big_check==true)
    283.      {
    284.       break;
    285.      }
    286.   }
    287.    if(!extended_path.empty()) path=extended_path;
    288.    if(m<path.size())
    289.    {
    290.     path=procedure_1(graph,path);
    291.     path=procedure_2(graph,path);
    292.    }
    293.    else quit=true;
    294.  }
    295.  return path;
    296. }
    297.  
    298. vector<int> procedure_2c(vector< vector<int> > graph, vector<int> path)
    299. {
    300.   vector<int> reversed_path;
    301.   for(int i=path.size()-1; i>=0; i--) reversed_path.push_back(path[i]);
    302.   reversed_path=procedure_2b(graph,reversed_path);
    303.   return reversed_path;
    304. }
    305.  
    306. vector<int> procedure_3(vector< vector<int> > graph, vector<int> path)
    307. {
    308.  
    309.  int i, n=path.size();
    310.  
    311.  vector<int> circuit_maker;
    312.  for(i=0; i<n-1; i++)
    313.   if((graph[path[0]][path[i+1]]==1) && (graph[path[i]][path[n-1]]==1))
    314.    circuit_maker.push_back(i);
    315.  return circuit_maker;
    316. }
    317.  
    318. vector<int> sort(vector<vector<int> > graph)
    319. {
    320.  int i, j;
    321.  vector<int> degree;
    322.  for(i=0; i<graph.size(); i++)
    323.  {
    324.   int sum=0;
    325.   for(j=0; j<graph[i].size(); j++)
    326.   if(graph[i][j]==1) sum++;
    327.   degree.push_back(sum);
    328.  }
    329.  vector<int> index;
    330.  for(i=0; i<degree.size(); i++) index.push_back(i);
    331.  for(i=0; i<degree.size(); i++)
    332.  for(j=i+1; j<degree.size(); j++)
    333.  if(degree[i]<degree[j]) swap(index[i],index[j]);
    334.  return index;
    335. }
    336.  
    337. vector<vector<int> >
    338.       reindex(vector<vector<int> > graph, vector<int> index)
    339. {
    340.   int i, j;
    341.   vector<vector<int> > temp=graph;
    342.   for(i=0; i<temp.size(); i++)
    343.   for(j=0; j<temp[i].size(); j++)
    344.   temp[i][j]=graph[index[i]][index[j]];
    345.   return temp;
    346. }

  6. #6
    Ngày gia nhập
    10 2007
    Nơi ở
    Gameloft studio
    Bài viết
    175

    Mặc định Lý thuyết đồ thị với C++

    Trích dẫn Nguyên bản được gửi bởi kidkid Xem bài viết
    Chắc cũng phải học lại mấy cái này thêm cho vững. Có gì nhờ Ht mới được ( HT Mobile ok ?) .
    ht thì lâu quá không đụng tới mấy cái đồ thị, nhưng cũng phải lo học lại, chắc tạo thêm cái topic về môn này để trao đổi cho hay.
    kidkid mà nhờ thì ht ngại quá, trao đổi hay hơn,ok
    Không biết ghi gì luôn ...

  7. #7
    Ngày gia nhập
    04 2008
    Nơi ở
    Hà Nội
    Bài viết
    0

    Cảm ơn các bạn đã giúp đỡ mình.
    Mấy hôm nay bận làm cái BTL quá nên không có thời gian Online. Hôm nay mới vào cảm ơn các bạn

Các đề tài tương tự

  1. Thuyết Trình Ext Js for asp.net
    Gửi bởi bigs1993 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 07-12-2013, 11:06 PM
  2. bài tập lý thuyết đồ thị
    Gửi bởi canhocthem trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 5
    Bài viết cuối: 11-10-2010, 11:39 PM
  3. lý thuyết đồ thị!
    Gửi bởi phamtuan04081989 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 1
    Bài viết cuối: 17-05-2010, 03:22 PM
  4. lý thuyết tô màu cho đồ thị
    Gửi bởi #include# trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 2
    Bài viết cuối: 24-09-2008, 04:11 PM
  5. [Phụ lục C] - Dành cho tra cứu lý thuyết C
    Gửi bởi Kevin Hoang trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 22-08-2006, 11:53 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn