我一直试图在业余时间学习更多关于图遍历的知识，并且尝试使用深度优先搜索来查找无向强连接图中开始节点和结束节点之间的所有简单路径。到目前为止，我一直在使用Print all paths from a given source to a destination中的这段代码，它只用于有向图。
使用递归dfs的主要算法出现在这两个函数中：
void Graph::printAllPaths(int s, int d)
{
// Mark all the vertices as not visited
bool *visited = new bool[V];
// Create an array to store paths
int *path = new int[V];
int path_index = 0; // Initialize path[] as empty
// Initialize all vertices as not visited
for (int i = 0; i < V; i++)
visited[i] = false;
// Call the recursive helper function to print all paths
printAllPathsUtil(s, d, visited, path, path_index);
}
// A recursive function to print all paths from 'u' to 'd'.
// visited[] keeps track of vertices in current path.
// path[] stores actual vertices and path_index is current
// index in path[]
void Graph::printAllPathsUtil(int u, int d, bool visited[],
int path[], int &path_index)
{
// Mark the current node and store it in path[]
visited[u] = true;
path[path_index] = u;
path_index++;
// If current vertex is same as destination, then print
// current path[]
if (u == d)
{
for (int i = 0; i<path_index; i++)
cout << path[i] << " ";
cout << endl;
}
else // If current vertex is not destination
{
// Recur for all the vertices adjacent to current vertex
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (!visited[*i])
printAllPathsUtil(*i, d, visited, path, path_index);
}
// Remove current vertex from path[] and mark it as unvisited
path_index--;
visited[u] = false;
}
它对有向图很好，但对无向强连通图则不行。
我想知道他们是不是一种方法来调整这段代码，也适用于无向图我有一种感觉，需要更多的回溯来探索更多可能的路径，但不确定如何接近这一点。
任何帮助都将不胜感激。
最佳答案
RoadRunner，你确定你的“未定向问题”在你显示的代码中吗乍一看还行也许错误是由于您没有修复addEdge以使您创建的图形无方向性造成的，例如：
void Graph::addEdge(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u); // Fix: add back edge as well!
}
更新（C代码，但很难看）
好的，这是我试图将代码转换为纯C的尝试。显然代码样式很难看，根本没有错误检查，但您可以改进这一点，因为我希望您更精通C。此外，我刚刚推出了一个简单的自定义图形节点链表，其名称有点奇怪，即包含一个图形节点的list node。
图h
#pragma once
#ifdef __cplusplus
extern "C" { // only need to export C interface if
// used by C++ source code
#endif
typedef struct tagNodeListNode {
struct tagNodeListNode* next;
int index;
} NodeListNode;
typedef struct tagGraph {
int nodesCount;
NodeListNode** adjArr;
} Graph;
typedef void(*GraphPathVisitorFunc)(NodeListNode const* const path);
Graph GraphCreate(int nodesCount);
void GraphDestroy(Graph gr);
void GraphAddEdge(Graph gr, int u, int v);
void GraphVisitAllPaths(Graph gr, int s, int d, GraphPathVisitorFunc visitor);
void GraphPrintAllPaths(Graph gr, int s, int d);
#ifdef __cplusplus
}
#endif
图c
#include "Graph.h"
#include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
Graph GraphCreate(int nodesCount)
{
// calloc ensures zeroing array
NodeListNode** adjArr = (NodeListNode**)calloc(nodesCount, sizeof(NodeListNode*));
Graph gr = { nodesCount, adjArr };
return gr;
}
void GraphDestroy(Graph gr)
{
for (int i = 0; i < gr.nodesCount; i++)
{
for (NodeListNode* adj = gr.adjArr[i]; adj != NULL;)
{
NodeListNode* tmp = adj;
adj = adj->next; //first move on the free
free(tmp);
}
}
free(gr.adjArr);
}
void GraphAddEdgeImplFirst(Graph gr, int from, int to)
{
NodeListNode* adj = gr.adjArr[from];
NodeListNode* n = (NodeListNode*)malloc(sizeof(NodeListNode));
n->next = adj;
n->index = to;
gr.adjArr[from] = n;
}
void GraphAddEdgeImplLast(Graph gr, int from, int to)
{
NodeListNode* adj = gr.adjArr[from];
NodeListNode* n = (NodeListNode*)malloc(sizeof(NodeListNode));
n->next = NULL;
n->index = to;
if(adj == NULL)
{
gr.adjArr[from] = n;
}
else
{
while (adj->next != NULL)
adj = adj->next;
adj->next = n;
}
}
void GraphAddEdge(Graph gr, int u, int v)
{
GraphAddEdgeImplFirst(gr, u, v);
GraphAddEdgeImplFirst(gr, v, u);
// closer to https://ideone.com/u3WoIJ but slower and thus makes no sense
//GraphAddEdgeImplLast(gr, u, v);
//GraphAddEdgeImplLast(gr, v, u);
}
void GraphVisitAllPathsImpl(Graph gr, int cur, int dst, GraphPathVisitorFunc visitor, NodeListNode* pathFst, NodeListNode* pathLst, bool* visited)
{
if (cur == dst)
{
visitor(pathFst);
return;
}
NodeListNode* adj = gr.adjArr[cur];
for (NodeListNode const* tmp = adj; tmp != NULL; tmp = tmp->next)
{
int next = tmp->index;
if (visited[next])
continue;
visited[next] = true;
NodeListNode nextNode = { NULL,next };
pathLst->next = &nextNode;
GraphVisitAllPathsImpl(gr, next, dst, visitor, pathFst, &nextNode, visited);
pathLst->next = NULL;
visited[next] = false;
}
}
void GraphVisitAllPaths(Graph gr, int start, int dst, GraphPathVisitorFunc visitor)
{
bool* visited = calloc(gr.nodesCount, sizeof(bool));
visited[start] = true;
NodeListNode node = { NULL,start };
GraphVisitAllPathsImpl(gr, start, dst, visitor, &node, &node, visited);
free(visited);
}
void PrintPath(NodeListNode const* const path)
{
for (NodeListNode const* tmp = path; tmp != NULL; tmp = tmp->next)
{
printf("%d ", tmp->index);
}
printf("\n");
}
void GraphPrintAllPaths(Graph gr, int s, int d)
{
GraphVisitAllPaths(gr, s, d, PrintPath);
}
和使用示例，图形与您的ideaone示例相同。注意，要获得匹配的输出，应该使用
NodeListNode而不是GraphAddEdgeImplLast，否则结果将按相反的顺序排列。void testGraph()
{
Graph gr = GraphCreate(20);
GraphAddEdge(gr, 0, 1);
GraphAddEdge(gr, 0, 7);
GraphAddEdge(gr, 1, 2);
GraphAddEdge(gr, 1, 6);
GraphAddEdge(gr, 1, 5);
GraphAddEdge(gr, 2, 3);
GraphAddEdge(gr, 2, 5);
GraphAddEdge(gr, 3, 4);
GraphAddEdge(gr, 3, 5);
GraphAddEdge(gr, 4, 5);
GraphAddEdge(gr, 4, 10);
GraphAddEdge(gr, 4, 11);
GraphAddEdge(gr, 5, 6);
GraphAddEdge(gr, 5, 10);
GraphAddEdge(gr, 5, 11);
GraphAddEdge(gr, 6, 7);
GraphAddEdge(gr, 6, 8);
GraphAddEdge(gr, 6, 9);
GraphAddEdge(gr, 6, 10);
GraphAddEdge(gr, 7, 8);
GraphAddEdge(gr, 8, 9);
GraphAddEdge(gr, 8, 13);
GraphAddEdge(gr, 9, 10);
GraphAddEdge(gr, 9, 13);
GraphAddEdge(gr, 9, 12);
GraphAddEdge(gr, 10, 12);
GraphAddEdge(gr, 11, 12);
GraphAddEdge(gr, 12, 13);
GraphAddEdge(gr, 12, 14);
GraphAddEdge(gr, 12, 16);
GraphAddEdge(gr, 13, 14);
GraphAddEdge(gr, 14, 15);
GraphAddEdge(gr, 16, 17);
GraphAddEdge(gr, 15, 17);
GraphAddEdge(gr, 15, 19);
GraphAddEdge(gr, 17, 18);
GraphAddEdge(gr, 17, 19);
GraphAddEdge(gr, 18, 19);
GraphPrintAllPaths(gr, 12, 4);
GraphDestroy(gr);
}
希望这有帮助