地图染色问题(C++)

andalousie

上面这张图就是这个程序的测试数据。代码利用回溯法。
graph.h

1. #if !defined (GRAPH_H)
   
2. #define GRAPH_H
   
3. 
   
4. /************************************************************
   
5. 
   
6. Class Graph represents a Graph [V,E] having vertices V and
   
7. edges E.
   
8. 
   
9. ************************************************************/
   
10. class Graph {
    
11.     private:
    
12.         int    _n;  /// n is the number of vertices in the graph
    
13.         int ** _A;  /// A stores the edges between two vertices
    
14.         int  * color;
    
15.     public:
    
16.         Graph(int size = 2);
    
17.         ~Graph();
    
18.         bool isConnected(int, int);
    
19.         void addEdge(int x, int y);
    
20.         bool DFS(int);
    
21.                 bool isSafe(int, int);
    
22.         void GraphColoring();
    
23. };
    
24. 
    
25. #endif

复制代码

graph.cc

1. #include <iostream>
   
2. #include "graph.h"
   
3. 
   
4. Graph::Graph(int size) {
   
5.         int i, j;
   
6.         if (size < 2) _n = 2;
   
7.         else _n = size;
   
8.         _A = new int*[_n];
   
9.         for (i = 0; i < _n; ++i)
   
10.                 _A[i] = new int[_n];
    
11.         for (i = 0; i < _n; ++i)
    
12.                 for (j = 0; j < _n; ++j)
    
13.                         _A[i][j] = 0;
    
14. }
    
15. 
    
16. Graph::~Graph() {
    
17.         for (int i = 0; i < _n; ++i)
    
18.         delete [] _A[i];
    
19.         delete [] _A;
    
20. }
    
21. 
    
22. /******************************************************
    
23. Checks if two given vertices are connected by an edge
    
24. @param u vertex
    
25. @param v vertex
    
26. @return true if connected false if not connected
    
27. ******************************************************/
    
28. bool Graph::isConnected(int x, int y) {
    
29.         return (_A[x-1][y-1] == 1);
    
30. }
    
31. 
    
32. /*****************************************************
    
33. adds an edge E to the graph G.
    
34. @param u vertex
    
35. @param v vertex
    
36. *****************************************************/
    
37. void Graph::addEdge(int x, int y) {
    
38.         _A[x-1][y-1] = _A[y-1][x-1] = 1;
    
39. }
    
40. 
    
41. /*****************************************************
    
42. performs Depth First Search
    
43. @param x initial vertex
    
44. *****************************************************/
    
45. bool Graph::DFS(int v)
    
46. {
    
47.         if(v == _n+1) return true;
    
48.         for (int c = 1; c <= 4; c++)
    
49.         {
    
50.                 if(isSafe(v, c))
    
51.                 {
    
52.                         color[v] = c;
    
53.                         if(DFS(v+1)) return true;
    
54.                         color[v] = 0;
    
55.                 }
    
56.         }
    
57.         return false;
    
58. }
    
59. 
    
60. bool Graph::isSafe(int v, int c)
    
61. {
    
62.         for(int w = 1; w <= _n; ++w)
    
63.                 if(isConnected(v, w) && c == color[w])
    
64.                         return false;
    
65.         return true;
    
66. }
    
67. 
    
68. void Graph::GraphColoring()
    
69. {
    
70.         color = new int[_n+1];
    
71.         for (int i = 1; i <= _n; ++i)
    
72.                 color[i] = 0;
    
73.         DFS(1);
    
74.         for (int w = 1; w <= _n; ++w)
    
75.                 std::cout << color[w] << ' ';
    
76.         std::cout << std::endl;
    
77.         delete [] color;
    
78. }

复制代码

main.cpp

1. #include "graph.h"
   
2. 
   
3. int main(){
   
4.     /** Creates a graph with 8 vertices */
   
5.     Graph g1(8);
   
6. 
   
7.     /** Adds edges to the graph */
   
8.     g1.addEdge(1, 6); g1.addEdge(1, 3);
   
9.     g1.addEdge(1, 2); g1.addEdge(4, 7);
   
10.     g1.addEdge(4, 6); g1.addEdge(4 ,5);
    
11.     g1.addEdge(6, 5); g1.addEdge(7, 5);
    
12.     g1.addEdge(7, 1); g1.addEdge(4, 3);
    
13.     g1.addEdge(2, 5); g1.addEdge(1, 8);
    
14.     g1.addEdge(2, 8); g1.addEdge(5, 8);
    
15.     g1.addEdge(7, 8);
    
16. 
    
17.     /** Explores all vertices findable from vertex 1 */
    
18.     g1.GraphColoring();
    
19. }

复制代码

simple123

这个必须要看看那啊