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

Question

#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;
}

Answer 1

以下答案参考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);
}

1. 修改深度优先搜索函数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);
}

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

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图库绘制顺序不一致的问题。

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