地图染色问题(C++)

andalousie

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

#if !defined (GRAPH_H)
#define GRAPH_H

/************************************************************

Class Graph represents a Graph [V,E] having vertices V and
edges E.

************************************************************/
class Graph {
    private:
        int    _n;  /// n is the number of vertices in the graph
        int ** _A;  /// A stores the edges between two vertices
        int  * color;
    public:
        Graph(int size = 2);
        ~Graph();
        bool isConnected(int, int);
        void addEdge(int x, int y);
        bool DFS(int);
                bool isSafe(int, int);
        void GraphColoring();
};

#endif

graph.cc

#include <iostream>
#include "graph.h"

Graph::Graph(int size) {
        int i, j;
        if (size < 2) _n = 2;
        else _n = size;
        _A = new int*[_n];
        for (i = 0; i < _n; ++i)
                _A[i] = new int[_n];
        for (i = 0; i < _n; ++i)
                for (j = 0; j < _n; ++j)
                        _A[i][j] = 0;
} 

Graph::~Graph() {
        for (int i = 0; i < _n; ++i)
        delete [] _A[i];
        delete [] _A;
} 

/******************************************************
Checks if two given vertices are connected by an edge
@param u vertex
@param v vertex
@return true if connected false if not connected
******************************************************/
bool Graph::isConnected(int x, int y) {
        return (_A[x-1][y-1] == 1);
} 

/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y) {
        _A[x-1][y-1] = _A[y-1][x-1] = 1;
}

/*****************************************************
performs Depth First Search
@param x initial vertex
*****************************************************/
bool Graph::DFS(int v)
{
        if(v == _n+1) return true;
        for (int c = 1; c <= 4; c++)
        {
                if(isSafe(v, c))
                {
                        color[v] = c;
                        if(DFS(v+1)) return true;
                        color[v] = 0;
                }
        }
        return false;
}

bool Graph::isSafe(int v, int c)
{
        for(int w = 1; w <= _n; ++w)
                if(isConnected(v, w) && c == color[w])
                        return false;
        return true;
}

void Graph::GraphColoring()
{
        color = new int[_n+1];
        for (int i = 1; i <= _n; ++i)
                color[i] = 0;
        DFS(1);
        for (int w = 1; w <= _n; ++w)
                std::cout << color[w] << ' ';
        std::cout << std::endl;
        delete [] color;
}

main.cpp

#include "graph.h"

int main(){
    /** Creates a graph with 8 vertices */
    Graph g1(8);

    /** Adds edges to the graph */
    g1.addEdge(1, 6); g1.addEdge(1, 3);
    g1.addEdge(1, 2); g1.addEdge(4, 7);
    g1.addEdge(4, 6); g1.addEdge(4 ,5);
    g1.addEdge(6, 5); g1.addEdge(7, 5);
    g1.addEdge(7, 1); g1.addEdge(4, 3);
    g1.addEdge(2, 5); g1.addEdge(1, 8);
    g1.addEdge(2, 8); g1.addEdge(5, 8);
    g1.addEdge(7, 8);

    /** Explores all vertices findable from vertex 1 */
    g1.GraphColoring();
}

simple123

这个必须要看看那啊