c - 带叉的哈密顿循环
问题描述
朋友们好,我想用 fork 为 5 个顶点编写哈密顿循环。我想为每个顶点创建一个进程来检查它是(hamCycleUtil 函数)中的真正顶点还是否。所以我写了这段代码,但它有错误的输出。我无法解决问题。请帮助。我怎样才能把这段代码写成真的?我只想创建 5 个进程来检查顶点。
/*
* C Program to Find Hamiltonian Cycle
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include<sys/types.h>
#include<unistd.h>
#define V 5
void printSolution(int path[]);
/*
* check if the vertex v can be added at index 'pos' in the Hamiltonian Cycle
*/
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)
return false;
return true;
}
/* solve hamiltonian cycle problem */
bool hamCycleUtil(bool graph[V][V], int path[], int pos)
{
int pid;
int s=-1;//counter
if (pos == V)
{
if (graph[ path[pos-1] ][ path[0] ] == 1)
return true;
else
return false;
}
for (int v = 1; v < V; v++)
{
pid=fork();
s++;
if(s<V)// to control the number of fork
{
if(v==1)
{
pid=1;}
pid=fork();
s++;
if(pid < 0) {
printf("Error");
}
else if (pid == 0){
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
if (hamCycleUtil (graph, path, pos+1) == true)
return true;
path[pos] = -1;
}
}
else {
if (isSafe(v, graph, path, pos))
{
path[pos] = v;
if (hamCycleUtil (graph, path, pos+1) == true)
return true;
path[pos] = -1;
}
}
}
}
return false;
}
/* solves the Hamiltonian Cycle problem using Backtracking.*/
bool hamCycle(bool graph[V][V])
{
int *path = malloc(V*sizeof(int));
for (int i = 0; i < V; i++)
path[i] = -1;
path[0] = 0;
if (hamCycleUtil(graph, path, 1) == false)
{
printf("\nSolution does not exist");
return false;
}
printSolution(path);
return true;
}
/* Main */
void printSolution(int path[])
{
printf("Solution Exists:");
printf(" Following is one Hamiltonian Cycle \n");
for (int i = 0; i < V; i++)
printf(" %d",path[i]);
printf(" %d",path[0]);
}
int main()
{
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3)-------(4) */
bool graph1[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
};
{ hamCycle(graph1);
/* Let us create the following graph
(0)--(1)--(2)
| / \ |
| / \ |
| / \ |
(3) (4) */
bool graph2[V][V] = {{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 1, 0, 0},
};
hamCycle(graph2);
return 0;
}}
解决方案
推荐阅读
- c++17 - 如何根据模板参数是否为 const 将成员函数声明为 const
- python - 如何替换 infs 以避免 PyTorch 中的 nan 梯度
- r - 如何在闪亮中对齐 checkBoxGroupInput 和 rendertext OUTPUTS?
- catia - 通过 CAA 打开 CATPart 并提取特征
- c# - 通过一个角度和轴的给定方向矢量旋转矢量,并且有一个轴的点。(3 个维度)
- css - Ctrl + / 在 SCSS/SASS 文件中无法在 Visual Studio 2017 中注释代码
- unity3d - Unity PhotonView 是我的检查
- r - 从两个数据框的列中匹配和提取值
- wpf - 如何让这个 drop overlay 的淡入动画效果很好?
- typescript - 如何强制使用 ts-jest 执行的测试在另一个文件夹中使用 node_modules?