I am implementing graph structure for my path finding in a maze program. In some operation like: traversing graph, free the graph (which is malloc-ed before, or use breadth first search,... It is require to check if a vertex is visited or not.

This is vertex and edge struct:

typedef struct graph
{
    // val just use to label the vertex
    int val;

    // since the maze just has 4 directions,
    // I simplify vertex to just point to 4 other vertices
    edge up;
    edge down;
    edge left;
    edge right;
}vertex;

typedef struct Edge
{
    int weight;
    vertex *neighbour;
    bool visited;
}edge;

I have thought about 2 solutions. The first is add bool visited; in vertex or edge struct and initialize it to false, but it just able to use 1 time, because I don't know how to reinitialize the visited. The second approach is make a link list, put the visited vertex in that list and check for visited vertex in that list when required. But it costs so much work when there are hundred of vertices.

So what is the good mechanism to check a vertex is visited? What is the better way to implement this problem?

Any help would be appreciated.

CodePudding user response：

I have to ideas to improve your solutions, for your first solution you can add bool visited to edge and vertex, and whenever you visit something you add it to a linked list, so when you are done and you want to re-initialize them to false you make one pass on the linked list and update their values and then clear the linked list.

The other solution is that when you visit a node or an edge you put them in some balanced binary search tree (map, set ... or something that you implement on your own), these allow you to add an element or check for an existence of an element in O(log(n)) where n is the total number of elements.