Warm tip: This article is reproduced from serverfault.com, please click

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

发布于 2020-12-04 12:18:22

Thanks for looking into this, I was trying to make a visual simulation of Depth first search algorithm, using graphics.h in C++, Each of my graph nodes have 3 attributes, x_coordinate y_coordinate and a nodeId, also I have a separate Class for Graph Object which has the adjacentcy list graph, So As the following code was executed It gave The results as incomplete, one of the five edges in input ( Input given below ) edge ( 0 - 3 ) was not displayed See snap shot here , can you help me with this?

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

Nodes are 0 Indexed.

Input Format : Number of nodes Number of edges

Number of edges Lines follow node1_id node2_id node1_x_coordinate node1_y_coordinate node2_x_coordinate node2_y_coordinate

Test Input :

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
Questioner
Pawan Nirpal
Viewed
0
user13737299 2020-12-05 00:41:28

the (0-3) line never gets drawn because when you hit the condition if( not vis[nb->nodeId]){ node 3 was already visited through line (0-2-3-4)