使用 graphics.h C++ 库刺激深度优先搜索算法时，深度优先搜索算法无法按预期工作

Question

感谢您对此进行调查，我试图在 C++ 中使用 graphics.h 对深度优先搜索算法进行可视化模拟，我的每个图形节点都有3 个属性，x_coordinate y_coordinate 和一个 nodeId，我还有一个单独的 Class 用于 Graph 具有相邻列表图的对象，因此当执行以下代码时它给出了不完整的结果，输入中的五个边之一（下面给出的输入）边（0-3）未显示See snap shot here ，你能帮我吗？

#include <iostream>
#include <vector>
#include <graphics.h>
using namespace std;

int WINHEIGHT = 900;
int WINWIDTH = 1600;
void StartGraphics(int winx = WINWIDTH,int winy = WINHEIGHT){
    // int gd = DETECT,gm;
    // initgraph(&gd,&gm,NULL);
    initwindow(winx,winy);
}

class Node{
    public:
        int xpos;
        int ypos;
        int nodeId;
    Node(){
        xpos =0;
        ypos =0;
        nodeId =0;
    }
    Node(int x,int y , int nid){
        xpos = x;
        ypos = y;
        nodeId = nid;
    }

    Node* getNewNode(int x,int y,int nid){
        return new Node(x,y,nid);
    }

    int GetNodeId(Node* nd){
        return nd->nodeId;
    }

};

class Graph {
    private:


    public:
        int Nofnodes;
        int Nofedges;
        vector<pair<Node*,vector<Node*>>>graph;
        Graph(int n,int e){
            Nofnodes = n;
            Nofedges = e;
            graph.resize(n);
        }
        
        void FillCircle(int x,int y, int radius,int color = WHITE){
            circle(x,y,radius);
            fillellipse(x,y,radius,radius);
            
        }


        void Draw(Node* u,Node* v){
            FillCircle(u->xpos,u->ypos,20);
            setlinestyle(0, 0, 5); 
            line(u->xpos,u->ypos,v->xpos,v->ypos);
            FillCircle(v->xpos,v->ypos,20);
            delay(2000);
        }
        
        void CreateGraph(){
            for(int e =0;e<Nofedges;e++){
                int u,v;
                cin>>u>>v;
                int ux,uy,vx,vy;
                cin>>ux>>uy>>vx>>vy;
                Node U,V;
                graph[u].first = U.getNewNode(ux,uy,u);
                graph[v].first = V.getNewNode(vx,vy,v);
                graph[u].second.push_back(graph[v].first);
                graph[v].second.push_back(graph[u].first);
            }
        }

        void DepthFirstSearchUtil(vector<pair<Node*,vector<Node*>>>g,vector<bool>&vis,int cnode){
            if( not vis[cnode]){
                vis[cnode] =1;
                for(auto nb : g[cnode].second){
                    if( not vis[nb->nodeId]){
                        Draw(g[cnode].first,nb);
                        
                        DepthFirstSearchUtil(g,vis,nb->nodeId);
                    }
                }
            }
        }

        void DepthFirstSearch(){
            vector<bool>vis(Nofnodes,0);
            for(int n =0;n<Nofnodes;n++){
                if(not vis[n]){
                   DepthFirstSearchUtil(graph,vis,n);
                }
            }
        }
};




int main(){
    
    int n,m;
    cin>>n>>m;
    Graph g(n,m);
    g.CreateGraph();
    
    
    StartGraphics();
    g.DepthFirstSearch();
    closegraph();
    return 0;
}

节点索引为 0。

输入格式： Number of nodes Number of edges

Number of edges 行如下 node1_id node2_id node1_x_coordinate node1_y_coordinate node2_x_coordinate node2_y_coordinate

测试输入：

5 5
0 2 50 50 20 250
0 1 50 50 250 80
0 3 50 50 200 230 // Not displayed edge
2 3 20 250 200 230
3 4 200 230 170 300

Answer 1

永远不会绘制 (0-3) 线，因为当您遇到条件时 if( not vis[nb->nodeId]){ 已经通过 (0-2-3-4) 线访问了节点 3

使用 graphics.h C++ 库刺激深度优先搜索算法时，深度优先搜索算法无法按预期工作

Depth First Search Algorithm not working as expected when stimulating it with graphics.h C++ library

c++

depth-first-search

bgi