地图染色问题(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();
}
这个必须要看看那啊
页:
[1]