How to generate Adjacent Matrix of a BFS from a txt file? C++

Asked

Viewed 794 times

2

I’m using the Codeblocks.

I have a. txt file that represents a maze, everything that is after the : are rooms: inserir a descrição da imagem aqui

The first line of the file shows the start coordinate, which in this case is AS. Every letter w represents a wall. So my BFS has as initial node (or initial root) the AS.

To represent this labyrinth in a graph would look like this:

inserir a descrição da imagem aqui

I have to represent this graph in an adjacency matrix. And I stuck to this part, that I have to generate this matrix, because to make the BFS the code needs to know the graph. I couldn’t think of a way to represent this adjacent matrix by reading this file, please, any suggestions, ideas, material, would help me a lot.

Note: My code can already obtain and store the maze in an array, without the letters before the : and without the initial coordinate. I have the complete labyrinth in a matrix. Telling who is next door to whom and generating the graph is what I’m not able to do.

c++ filing-cabinet matrix graph

  • @nbro, your assumption is correct, are just names for each of the rooms of the labyrinth. The acronyms before the : It is like a numbering, because in this problem there are rooms that contain jewels, and to indicate that a room contains a jewel the following is done: ;AN: AO S AM BI *AO: AP T AN BJ AP: w U AO BK *AO: there is the character *, and it indicates that in all subsequent rooms of name AO there are jewels. w. Continues...

  • Continuation of the... However, to make the BFS I have to have the graph, which says who is next door to whom, and this part that I cannot solve, how can I create the graph, that is, the adjacent matrix, with all the relationships of the rooms? Please, any hint or suggestion will help me a lot.

  • @All the graphs that I worked, applied in the search algorithms, were informed by hand, because they were small. I’ve never worked with search algorithms where we should generate the graph from the algorithm. I’m not familiar with the "Adjacent list".

  • @nbro, Interesting, I will follow your suggestion. I will search for Nodes and adjacent lists and try this. Thanks for the suggestion and the tip, as soon as I get results I update the post here.

1 answer

1

My tip is to create your adjacency matrix as a 150x150 size matrix and use the ASCII value of the characters as positions in the matrix.

Picking up the line A: B W W V of your file as an example, your first step is to ignore the W, after all it does not add any information to the graph. Then you convert the letters to their respective values in the ascii table. A flipped 65, B 66 and V 86. Then you use these values as indexes in your adjacency matrix: the line 65 the matrix would have all its values as 0 (indicating no connection with other nodes), except for the columns 66 and 86, where the value would be 1, indicating connection with nodes B and V, respectively.

And to treat special cases where the "name" of the node is the set of two letters, simply add the ASCII value of both. Example: AS flipped 148 (65 + 83).

Browser other questions tagged c++ filing-cabinet matrix graph

You are not signed in. Login or sign up in order to post.