DEV C++中EGE图库无法按照深度优先搜索顺序标注顶点，如何解决？

#DEV C++，正确安装了EGE图形库，但是这个代码中我输入了起始节点终止节点与权重后，输出的深度优先结果与EGE图库标注的顺序不符，例如：我输入的起点终点权重是：0 1 1
0 2 1
1 3 1
1 4 1
2 5 1
2 6 1
3 7 1
5 8 1
后输出的深度优先搜索结果是01374256，而EGE图库标注（蓝色）亮起的顺序是02561437，这是为什么？

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <graphics.h>
#include <math.h>
#include <conio.h>
#define MAX_VERTICES 100
#include <windows.h>

// 邻接表结构
typedef struct Node {
    int vertex;
    int weight;
    struct Node* next;
} Node;

typedef struct {
    int numVertices;
    Node** adjacencyList;
} Graph;

// 创建图
Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->adjacencyList = (Node**)malloc(numVertices * sizeof(Node*));
    
    for (int i = 0; i < numVertices; i++) {
        graph->adjacencyList[i] = NULL;
    }
    
    return graph;
}

// 添加边
void addEdge(Graph* graph, int startVertex, int endVertex, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = endVertex;
    newNode->weight = weight;
    newNode->next = NULL;
    
    // 如果链表为空，直接插入
    if (graph->adjacencyList[startVertex] == NULL) {
        graph->adjacencyList[startVertex] = newNode;
    } else {
        // 否则按顺序插入
        Node* currentNode = graph->adjacencyList[startVertex];
        Node* prevNode = NULL;
        while (currentNode != NULL && currentNode->vertex < endVertex) {
            prevNode = currentNode;
            currentNode = currentNode->next;
        }
        if (prevNode == NULL) {
            newNode->next = graph->adjacencyList[startVertex];
            graph->adjacencyList[startVertex] = newNode;
        } else {
            newNode->next = prevNode->next;
            prevNode->next = newNode;
        }
    }
}

// 打印图的结构
void printGraph(Graph* graph) {
    printf("图的结构：\n");
    for (int i = 0; i < graph->numVertices; i++) {
        Node* currentNode = graph->adjacencyList[i];
        printf("顶点 %d：", i);
        while (currentNode != NULL) {
            printf("(%d, %d) ", currentNode->vertex, currentNode->weight);
            currentNode = currentNode->next;
        }
        printf("\n");
    }
}

// 广度优先搜索
void breadthFirstSearch(Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    int* queue = (int*)malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }
    
    visited[startVertex] = 1;
    queue[rear++] = startVertex;
    
    printf("广度优先搜索结果：");
    
    while (front < rear) {
        int currentVertex = queue[front++];
        printf("%d ", currentVertex);
        
        Node* currentNode = graph->adjacencyList[currentVertex];
        while (currentNode != NULL) {
            if (visited[currentNode->vertex] == 0) {
                visited[currentNode->vertex] = 1;
                queue[rear++] = currentNode->vertex;
            }
            currentNode = currentNode->next;
        }
    }
    
    printf("\n");
    
    free(visited);
    free(queue);
}

// 深度优先搜索
void depthFirstSearchUtil(Graph* graph, int startVertex, int* visited, int* dfsOrder, int* dfsIndex) {
    visited[startVertex] = 1;
    dfsOrder[(*dfsIndex)++] = startVertex;
    
    Node* currentNode = graph->adjacencyList[startVertex];
    while (currentNode != NULL) {
        if (visited[currentNode->vertex] == 0) {
            depthFirstSearchUtil(graph, currentNode->vertex, visited, dfsOrder, dfsIndex);
        }
        currentNode = currentNode->next;
    }
}

void depthFirstSearch(Graph* graph, int startVertex) {
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    int* dfsOrder = (int*)malloc(graph->numVertices * sizeof(int));
    int dfsIndex = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }
    
    depthFirstSearchUtil(graph, startVertex, visited, dfsOrder, &dfsIndex);
    
    printf("深度优先搜索结果：");
    for (int i = 0; i < dfsIndex; i++) {
        printf("%d ", dfsOrder[i]);
    }
    printf("\n");
    
    free(visited);
    free(dfsOrder);
}

int main() {
    int numVertices;
    printf("请输入图的顶点个数：");
    scanf("%d", &numVertices);
    Graph* graph = createGraph(numVertices);

    printf("请输入带权边的起始顶点、结束顶点和权重：\n");
    printf("（输入-1 -1 -1结束）\n");

    while (true) {
        int startVertex, endVertex, weight;
        scanf("%d %d %d", &startVertex, &endVertex, &weight);

        if (startVertex == -1 && endVertex == -1 && weight == -1) {
            break;
        }

        addEdge(graph, startVertex, endVertex, weight);
    }

    printGraph(graph);

    breadthFirstSearch(graph, 0);
    depthFirstSearch(graph, 0);

    // 使用EGE图库绘制图形并标注搜索顺序
    initgraph(640, 480);
    setbkcolor(BLACK);
    cleardevice();

    int radius = 100;
    int centerX = 320;
    int centerY = 240;
    int startAngle = 0;
    int endAngle = 360;

    // 绘制顶点
    for (int i = 0; i < graph->numVertices; i++) {
        int x = centerX + radius * cos(i * 2 * M_PI / graph->numVertices);
        int y = centerY + radius * sin(i * 2 * M_PI / graph->numVertices);
        circle(x, y, 30);

        char vertexLabel[2];
        sprintf(vertexLabel, "%d", i);
        outtextxy(x - 5, y - 5, vertexLabel);
    }

    // 标注广度优先搜索顺序
    int* bfsOrder = (int*)malloc(graph->numVertices * sizeof(int));
    int bfsIndex = 0;

    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }

    int* queue = (int*)malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;

    visited[0] = 1;
    queue[rear++] = 0;

    while (front < rear) {
        int currentVertex = queue[front++];
        bfsOrder[bfsIndex++] = currentVertex;

        Node* currentNode = graph->adjacencyList[currentVertex];
        while (currentNode != NULL) {
            if (visited[currentNode->vertex] == 0) {
                visited[currentNode->vertex] = 1;
                queue[rear++] = currentNode->vertex;
            }
            currentNode = currentNode->next;
        }
    }

    // 绘制广度优先搜索顺序
    for (int i = 0; i < bfsIndex; i++) {
        int x = centerX + radius * cos(bfsOrder[i] * 2 * M_PI / graph->numVertices);
        int y = centerY + radius * sin(bfsOrder[i] * 2 * M_PI / graph->numVertices);
        setcolor(RED);
        circle(x, y, 30);
        Sleep(500);
    }

    // 标注深度优先搜索顺序
    int* dfsOrder = (int*)malloc(graph->numVertices * sizeof(int));
    int dfsIndex = 0;

    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }

    int* stack = (int*)malloc(graph->numVertices * sizeof(int));
    int top = -1;

    stack[++top] = 0;

    while (top >= 0) {
        int currentVertex = stack[top--];

        if (visited[currentVertex] == 0) {
            visited[currentVertex] = 1;
            dfsOrder[dfsIndex++] = currentVertex;

            Node* currentNode = graph->adjacencyList[currentVertex];
            while (currentNode != NULL) {
                if (visited[currentNode->vertex] == 0) {
                    stack[++top] = currentNode->vertex;
                }
                currentNode = currentNode->next;
            }
        }
    }

    // 绘制深度优先搜索顺序
    for (int i = 0; i < dfsIndex; i++) {
        int x = centerX + radius * cos(dfsOrder[i] * 2 * M_PI / graph->numVertices);
        int y = centerY + radius * sin(dfsOrder[i] * 2 * M_PI / graph->numVertices);
        setcolor(BLUE);
        circle(x, y, 30);
        Sleep(500);
    }

    getch();
    closegraph();

    free(bfsOrder);
    free(dfsOrder);
    free(visited);
    free(queue);
    free(stack);

    return 0;
}

以下答案参考newbing,回答由博主波罗歌编写：
问题出现的原因是深度优先搜索的递归调用顺序与EGE图库绘制顺序不同导致的。在深度优先搜索中，我们是根据邻接表的顺序进行递归调用的，而在EGE图库中，我们是按照顶点的顺序进行绘制的。因此，当顶点的邻接表中的顶点的顺序与它们在图中的顺序不一致时，深度优先搜索的结果与EGE图库绘制顺序不一致。

要解决这个问题，需要修改广度优先搜索和深度优先搜索的实现，以便按照EGE图库的顺序进行搜索。具体实现如下：

1. 修改广度优先搜索函数breadthFirstSearch，将深度优先搜索的结果保存到bfsOrder数组中。

void breadthFirstSearch(Graph* graph, int startVertex, int* bfsOrder) {
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    int* queue = (int*)malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }
    
    visited[startVertex] = 1;
    queue[rear++] = startVertex;
    
    int index = 0;
    
    while (front < rear) {
        int currentVertex = queue[front++];
        bfsOrder[index++] = currentVertex;
        
        Node* currentNode = graph->adjacencyList[currentVertex];
        while (currentNode != NULL) {
            if (visited[currentNode->vertex] == 0) {
                visited[currentNode->vertex] = 1;
                queue[rear++] = currentNode->vertex;
            }
            currentNode = currentNode->next;
        }
    }
    
    free(visited);
    free(queue);
}

2. 修改深度优先搜索函数depthFirstSearch，将深度优先搜索的结果保存到dfsOrder数组中。

void depthFirstSearchUtil(Graph* graph, int startVertex, int* visited, int* dfsOrder, int* dfsIndex) {
    visited[startVertex] = 1;
    dfsOrder[(*dfsIndex)++] = startVertex;
    
    Node* currentNode = graph->adjacencyList[startVertex];
    while (currentNode != NULL) {
        if (visited[currentNode->vertex] == 0) {
            depthFirstSearchUtil(graph, currentNode->vertex, visited, dfsOrder, dfsIndex);
        }
        currentNode = currentNode->next;
    }
}

void depthFirstSearch(Graph* graph, int startVertex, int* dfsOrder) {
    int* visited = (int*)malloc(graph->numVertices * sizeof(int));
    int dfsIndex = 0;
    
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = 0;
    }
    
    depthFirstSearchUtil(graph, startVertex, visited, dfsOrder, &dfsIndex);
    
    free(visited);
}

3. 在主函数中，调用修改后的广度优先搜索和深度优先搜索函数，并分别绘制广度优先搜索顺序和深度优先搜索顺序。

int main() {
    // ...
    
    // 广度优先搜索
    int* bfsOrder = (int*)malloc(graph->numVertices * sizeof(int));
    breadthFirstSearch(graph, 0, bfsOrder);

    // 绘制广度优先搜索顺序
    for (int i = 0; i < graph->numVertices; i++) {
        int x = centerX + radius * cos(bfsOrder[i] * 2 * M_PI / graph->numVertices);
        int y = centerY + radius * sin(bfsOrder[i] * 2 * M_PI / graph->numVertices);
        setcolor(RED);
        circle(x, y, 30);
        Sleep(500);
    }

    // 深度优先搜索
    int* dfsOrder = (int*)malloc(graph->numVertices * sizeof(int));
    depthFirstSearch(graph, 0, dfsOrder);

    // 绘制深度优先搜索顺序
    for (int i = 0; i < graph->numVertices; i++) {
        int x = centerX + radius * cos(dfsOrder[i] * 2 * M_PI / graph->numVertices);
        int y = centerY + radius * sin(dfsOrder[i] * 2 * M_PI / graph->numVertices);
        setcolor(BLUE);
        circle(x, y, 30);
        Sleep(500);
    }

    // ...
    
    return 0;
}

这样，广度优先搜索和深度优先搜索的结果将按照EGE图库的顺序进行搜索和绘制，解决了顶点标注顺序与EGE图库绘制顺序不一致的问题。

希望这个解答对你有帮助！如果还有其他问题，请随时提问。
如果我的回答解决了您的问题，请采纳！

TechWhizKid参考GPT回答：

代码和EGE图形库在表示深度优先搜索（DFS）的 "顺序" 上存在差异，主要在遍历相邻节点时所采用的顺序不同。

你的代码中用的是邻接表来存储图的信息，每次添加一条边时，都会将其插入到邻接表中的适当位置，以保证每个顶点的邻接列表按照顶点的值升序排列。因当进行深度优先搜索时，你会先遍历数值较小的顶点。

EGE图形库在显示图形并进行DFS遍历时，可能并未按照顶点的数值进行排序，而是按照你添加边的顺序来遍历。这是你看到的DFS遍历顺序与代码输出不符的原因。

如果希望你的代码输出的DFS顺序与EGE图形库的可视化结果一致，那么你可能要调整你的代码，使得它在进行DFS遍历时按照你添加边的顺序，而不是顶点的数值来遍历相邻的顶点。具体来说，你可以在添加边的时候，总是将新的边添加到邻接列表的末尾，而不是按照顶点的值插入到适当的位置。

这里是修改后的addEdge函数：

// 添加边
void addEdge(Graph* graph, int startVertex, int endVertex, int weight) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = endVertex;
    newNode->weight = weight;
    newNode->next = NULL;
    
    // 如果链表为空，直接插入
    if (graph->adjacencyList[startVertex] == NULL) {
        graph->adjacencyList[startVertex] = newNode;
    } else {
        // 否则插入到链表的末尾
        Node* currentNode = graph->adjacencyList[startVertex];
        while (currentNode->next != NULL) {
            currentNode = currentNode->next;
        }
        currentNode->next = newNode;
    }
}

在使用DEV C++中的EGE图库进行深度优先搜索时，输出的顶点顺序与EGE图库标注的顺序不符的问题可能是由于以下原因导致的：

1. 图的存储方式：深度优先搜索算法的顺序依赖于图的存储方式。如果图以邻接矩阵或邻接表的形式存储，可能会导致顶点的访问顺序不同。请确保你的代码和EGE图库使用相同的图存储方式。

2. 算法实现：你使用的深度优先搜索算法的实现可能与EGE图库中的实现有所不同。确保你的深度优先搜索算法是正确的，并按照预期的顺序访问和标注顶点。

要解决这个问题，你可以尝试以下方法：

1. 检查图的存储方式：确保你的代码和EGE图库使用相同的图存储方式，比如邻接矩阵或邻接表。

2. 检查深度优先搜索算法的实现：仔细检查你的深度优先搜索算法的实现是否正确。确保你按照深度优先的原则访问和标注顶点，即先访问一个节点的所有邻居节点，再递归地访问邻居节点的邻居节点。

3. 对比结果：将你的代码输出的深度优先搜索结果与EGE图库标注的顺序进行对比。检查是否有任何错误或缺失的节点。如果有差异，试着找到造成差异的具体原因并进行调试。

最后，需要注意的是，深度优先搜索在不同的图中可能会产生不同的顶点访问顺序。这是由于图的结构以及算法的实现方式所决定的。因此，得到不同的顶点访问顺序并不一定是错误的，只要算法的实现是正确的，结果也是有效的。

C/C++语言：图的遍历之深度优先搜索 代码实现

//
// Created by dong on 2022-03-16.
//
#include "home10.h"

int main(){
   AMGraph G;
   G.vernum = 8;//8个顶点
   G.arcnum = 9;
   //
   char test[8]={'a','b','c','d','e','f','g','h'};
   for(int i = 0; i < 8; i++)
       G.vertexs[i] = test[i];
   //
   int a[8][8]={0,1,1,0,0,0,0,0,
                1,0,0,1,1,0,0,0,
                1,0,0,0,0,1,1,0,
                0,1,0,0,0,0,0,1,
                0,1,0,0,0,0,0,1,
                0,0,1,0,0,0,1,0,
                0,0,1,0,0,1,0,0,
                0,0,0,1,1,0,0,0};
   for(int i = 0; i < 8; i++)
       for(int j = 0; j < 8; j++)
           G.arcs[i][j] = a[i][j];
   //
    Function(G,'a');

    return 0;
}

仔细检查您的输入与EGE图库的表示方式是否一致，确保输入的节点编号、边权重等与图库中的表示方式相同。
检查您的DFS算法的实现方式是否与EGE图库中的实现方式相同。您以尝试使用不同的DFS算法实现，例如非递归的深度优先搜索，以查看结果是否一致。