3

经过一段时间的阅读和搜索，我仍然无法理解多重图的深度优先遍历（或搜索）（两个顶点可以有多个边）。

我在另一个 SO 问题上找到了这个答案：

查找两个任意顶点之间所有连接的图算法

这是一个很好的答案，但它仅适用于简单图。

所以简而言之，我需要Multigraph中从顶点 A 到顶点 B 的所有简单路径（不重复顶点） ，而不仅仅是最短路径。

如果有帮助的话，我正在使用 JGraphT 在 Java 中实现它。我不介意另一种语言的解决方案。如果这也有帮助的话，该图是有向的和加权的。

PS我不关心算法的运行时间（我会缓存结果）。

我正在寻找类似于链接问题中的输出（我在边缘附加了一些更多信息，但这与遍历没有太大关系：

All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E

谢谢你。

4

2 回答 2

2

多重图和普通图实际上不应该需要不同的代码。在这两种情况下，您都需要知道您过去是否访问过此特定路径上的给定节点。无论有多少边可以连接两个顶点，这都有效。

因此，您要做的是，对于每条路径，保留您已经访问过的顶点的列表，并且永远不要到达已经访问过的顶点。因此，一些伪代码：

function DFSHelper(vertex v, array visited):
    for edge in v.edges:
        if edge.vertex_at_end not in visited:
            DFSHelper(edge.vertex_at_end, visited + [edge.vertex_at_end])
    for v in visited:
        print v + "->"

function DFS(vertex v):
    DFSHelper(v, [])

适当调整（例如，当前打印给定路径的所有子路径，如“A”、“A->B”、“A->B->C”等）。

另请注意，这将打印一些路径两次（如果同一对顶点之间有多个边）。您可以通过在给定函数中仅从顶点 B 向顶点 A 移动一次来调整以消除此行为（即，如果多条边连接两者，则仅在第一条边上递归，而忽略其余边）。

于 2013-07-18T16:50:06.773 回答
0

这是 C 中 DFS 搜索的实现。可以修改为与 MultiGraphs imo 一起使用。

如果这是您正在寻找的，我可以修改它以使用“MultiGraphs”..

#include <stdio.h>
#include <malloc.h>
#include <conio.h>

typedef struct AdjacencyList
{
    char VertexID;
    int *IncidenceList;
}AdjList;

typedef struct Graph
{
    int VertexCount, Status;
    char VertexName;
    AdjList List;
    struct Graph *Next;
}Graph;

Graph* InitializeGraph();
Graph *InitGraphNode(int cnt);
void PerformDepthFirstSearch(Graph *graph);

int main()
{
    Graph *graph;
    graph = InitializeGraph();
    PerformDepthFirstSearch(graph);
    return 0;
}

Graph *InitGraphNode(int cnt)
{
    Graph *node = ((Graph*)malloc(sizeof(Graph)));
    node->List.IncidenceList = ((int*)malloc(sizeof(int)*cnt));
    node->Next = NULL;
    return node;
}

Graph* InitializeGraph()
{
    Graph *graphHead = NULL, *node, *tmp, *tmp2;
    char vname;
    int cnt, i, j, isIncident = 0;
    printf("Enter the number of vertices : ");
    scanf("%d", &cnt);
    if (cnt == 0)
    {
        printf("Number of vertices cannot be ZERO!!\n\n");
        return graphHead;
    }
    graphHead = InitGraphNode(1);
    graphHead->VertexCount = cnt;
    for(i = 0; i < cnt; i++)
    {
        printf("VertexName : ");
        vname = getche();
        printf("\n");
        node = InitGraphNode(cnt);
        node->VertexName = vname;
        node->Next = NULL;
        node->Status = 1;
        if (graphHead->Next == NULL)
        {
            graphHead->Next = node;
        }
        else
        {
            tmp = graphHead;
            while (tmp->Next != NULL)
            {
                tmp = tmp->Next;
            }
            tmp->Next = node;
        }
    }
    tmp = graphHead->Next;
    printf("Prepare to input the adjacent elements of corresponding vertices...\n\n");
    for(i = 0; i < cnt; i++)
    {
        vname = tmp->VertexName;
        tmp2 = graphHead->Next;
        for(j = 0; j < cnt; j++)
        {
        here :
            printf("%c incident on %c :: (1 for YES)(0 for NO) ::-> ",vname, tmp2->VertexName);
            scanf("%d", &isIncident);
            if ((isIncident < 0)||(isIncident > 1))
            {
                printf("Wrong Input!! Try again!!\n\n");
                goto here;
            }
            tmp->List.IncidenceList[j] = isIncident;
            tmp2 = tmp2->Next;
        }
        tmp = tmp->Next;
    }
    return graphHead;
}

void PerformDepthFirstSearch(Graph *graph)
{
    Graph *Stack[100], *Copy = graph->Next, *node, *tmp = graph->Next;
    int top = 0, i, cnt = 0;
    Stack[top++] = Copy;
    Copy->Status++;
    while(top != 0)
    {
        node = Stack[--top];
        node->Status++;
        printf("%c, ", node->VertexName);
        for(i = 0; i < graph->VertexCount; i++)
        {
            if(node->List.IncidenceList[i] == 1)
            {
                while (cnt < i)
                {
                    tmp = tmp->Next;
                    cnt++;
                }
                if (tmp->Status == 1)
                {
                    Stack[top++] = tmp;
                    tmp->Status++;
                }
            }
        }
    }
}
于 2013-07-18T16:33:02.860 回答