andalousie 发表于 2014-4-17 13:07:18

地图染色问题(C++)


上面这张图就是这个程序的测试数据。代码利用回溯法。
graph.h
#if !defined (GRAPH_H)
#define GRAPH_H

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

Class Graph represents a Graph 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();
};

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

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

Graph::~Graph() {
      for (int i = 0; i < _n; ++i)
      delete [] _A;
      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 == 1);
}

/*****************************************************
adds an edge E to the graph G.
@param u vertex
@param v vertex
*****************************************************/
void Graph::addEdge(int x, int y) {
      _A = _A = 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 = c;
                        if(DFS(v+1)) return true;
                        color = 0;
                }
      }
      return false;
}

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

void Graph::GraphColoring()
{
      color = new int;
      for (int i = 1; i <= _n; ++i)
                color = 0;
      DFS(1);
      for (int w = 1; w <= _n; ++w)
                std::cout << color << ' ';
      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 发表于 2014-4-18 19:19:27

这个必须要看看那啊
页: [1]
查看完整版本: 地图染色问题(C++)