Member Avatar for Spinz

Hi! I am a beginner in C++, I hope that anyone can advice me on approaching this problem. I would like to implement a class graph that uses breath-first search in order to remove a chosen vertice as well as its corresponding edges.

I want to:
*add or remove edges
*check whether a particular edge is present
*search for unmarked neighbouring vertices that may be deleted

My dilemma right now is figuring which structures to use and how to use them, for example:
-BFS needs a Queue to keep track of unmarked vertices and its neighbours.
-For a weighted graph (edges have values), it might be best to use a linked list representation (i.e edge list)
-is a matrix appropriate

or is it possible to use all of these??? Any help is appreciated!

  • 2 Contributors
  • 1 Reply
  • 72 Views
  • 6 Days Discussion Span
  • Latest Post Latest Post by alwaysLearning0
Member Avatar for alwaysLearning0

Use matrix, for any graph matrix is the best structure to use, you can easily find the edges in O(1).

For BFS, you need to implement a queue to do the BFS on the graph matrix.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.