暴力算法

a. 最接近点对问题的BF算法实现

#include <stdio.h>
#include <float.h>
#include <math.h>

struct Point {
	int x, y;
};

float calculateDistance(struct Point p1, struct Point p2) {
	return sqrt(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

void closestPair(struct Point points[], int n) {
	float minDistance = FLT_MAX;
	int a, b;
	for (int i = 0; i < n - 1; i++) {
		for (int j = i + 1; j < n; j++) {
			float distance = calculateDistance(points[i], points[j]);
			if (distance < minDistance) {
				minDistance = distance;
				a = i;
				b = j;
			}
		}
	}
	printf("最近点对的距离是 %f", minDistance);
	printf("最近点对是<%d,%d>,<%d,%d>", points[a].x, points[a].y, points[b].x, points[b].y);
}

int main() {
	struct Point points[] = {
		{8,-15},{9,-29},{29,-28},{-30,-13},{-3,45},{-33,-12},{-7,35},{47,-45},{43,-10},{24,-6},
	};
	int n = sizeof(points) / sizeof(points[0]);

	closestPair(points, n);
    
	return 0;
}

b. Hamilton回路问题的BF算法实现

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。

#include <stdio.h>  
#include <stdbool.h>  

#define V 4 // 图的顶点数  

void printSolution(int path[]);  

//pos:当前位置，表示当前在构建路径的过程中所处的位置
//函数用于检查在当前路径构建的情况下，是否可以安全地将指定的顶点 v 加入到路径中
bool isSafe(int v, bool graph[V][V], int path[], int pos) {  
	if (graph[path[pos - 1]][v] == 0) {  //前一个顶点到当前顶点是否有边相连
		return false;  
	}  
	
	for (int i = 0; i < pos; i++) {  
		if (path[i] == v) {  //检查路径中是否已经包含了顶点 v
			return false;  
		}  
	}  
	
	return true;  
}  

bool hamiltonianCycleUtil(bool graph[V][V], int path[], int pos) { //构建哈密尔顿回路的路径
	//最后一个点
	if (pos == V) {  
		if (graph[path[pos - 1]][path[0]] == 1) {  //最后一个点和起始点有连接，即构成回路
			return true;  
		} else {  
			return false;  
		}  
	}  
	
	for (int v = 1; v < V; v++) {  
		if (isSafe(v, graph, path, pos)) {  
			path[pos] = v;  
			
			if (hamiltonianCycleUtil(graph, path, pos + 1)) {  //构建哈密尔顿回路的路径
				return true;  
			}  
			
			path[pos] = -1; // 否则回溯
		}  
	}  
	
	return false;  
}  

bool hamiltonianCycle(bool graph[V][V]) {  
	int path[V];  
	for (int i = 0; i < V; i++) {  
		path[i] = -1;  
	}  
	
	path[0] = 0; // 从第一个顶点开始  
	
	if (!hamiltonianCycleUtil(graph, path, 1)) {  
		printf("No Hamiltonian Cycle exists");  
		return false;  
	}  
	
	printSolution(path);  
	return true;  
}  

void printSolution(int path[]) {  
	printf("Hamiltonian Cycle found: \n");  
	for (int i = 0; i < V; i++) {  
		printf("%d ", path[i]);  
	}  
	printf("%d", path[0]); //完成循环  
	printf("\n");  
}  

int main() {  
	bool graph[V][V] = {  
		{0, 1, 1, 1},
		{1, 0, 1, 1},
		{1, 1, 0, 1},
		{1, 1, 1, 0}
	};  
	
	hamiltonianCycle(graph);  
	return 0;  
}

Donate