因此，我需要对给定的图进行深度优先搜索遍历，然而，如果图中的一个 node 有多个相邻的邻居，我需要 Select 值最低的 node .因此，我实现了以下递归深度优先搜索函数:
void DFS(struct Graph *graph, int vertex) {
struct node *adjList = graph->adjLists[vertex];
struct node *temp = adjList;
graph->visited[vertex] = 1;
printf("Visited %d \n", vertex);
int neighbouring_nodes[graph->numVertices];
while (temp != NULL) {
int count = 0;
struct node *temp_cpy = temp;
while (temp_cpy != NULL) {
neighbouring_nodes[count] = temp_cpy->vertex;
count++;
temp_cpy = temp_cpy->next;
}
int smallest_node = neighbouring_nodes[0];
for (int i = 0; i < count; i++) {
if (neighbouring_nodes[i] < smallest_node) {
smallest_node = neighbouring_nodes[i];
}
}
if (graph->visited[smallest_node] == 0) {
DFS(graph, smallest_node);
} else if (graph->visited[smallest_node] == 1 && count == 1) {
//if the node is visited but is it the only neighbour
DFS(graph, smallest_node);
}
temp = temp->next;
}
}
但当我运行程序时，它会导致无限循环.我想我知道为什么我得到了一个无限循环，可能是因为从来没有返回条件，所以递归函数一直在运行？
这种深度优先搜索是否可以使用递归函数？如果是，我错在哪里？如果没有，我将如何迭代？
下面是我没有DFS功能的完整程序:
// DFS algorithm in C
#include <stdio.h>
#include <stdlib.h>
struct node {
int vertex;
struct node *next;
};
struct node *createNode(int v);
struct Graph {
int numVertices;
int *visited;
struct node **adjLists;
};
// Create a node
struct node *createNode(int v) {
struct node *newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}
// Create graph
struct Graph *createGraph(int vertices) {
struct Graph *graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;
graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph->adjLists[i] = NULL;
graph->visited[i] = 0;
}
return graph;
}
// Add edge
void addEdge(struct Graph *graph, int src, int dest) {
// Add edge from src to dest
struct node *newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
// Add edge from dest to src
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
// Print the graph
void printGraph(struct Graph *graph) {
int v;
for (v = 0; v < graph->numVertices; v++) {
struct node *temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp) {
printf("%d -> ", temp->vertex);
temp = temp->next;
}
printf("\n");
}
}
int main() {
struct Graph *graph = createGraph(4);
addEdge(graph, 0, 1);
addEdge(graph, 0, 2);
addEdge(graph, 1, 2);
addEdge(graph, 2, 3);
printGraph(graph);
DFS(graph, 2);
return 0;
}