Jump to content

depth-first search of a graph

mathmari
in Homework Help

Featured Replies

Hi!!! I need some help...

The exercise is:

You have to implement a data structure to represent graphs,directed or undirected,that tries to avoid the wasted space in the representation of a graph with adjacency matrix and the difficulty of searching the edges with adjacency list representation.

We consider that the vertices are numbered from 1 to nverts and the exit degree of each vertex is at most MAXDEG. If deg is the exit degree of the vertex i then the neighbors of the vertex i can be saved at the matrix edge[j], 1<=j<=deg.

Write a program that reads the datas from a file: if the graph is directed or undirected(1 or 0), the number of vertices (nverts),the number of edges (nedges) and the first and the last vertex of each edge.

Write the function dfs that, with argument the data structure that you implemented before for the representation of a graph, prints the edges by the depth-first search of a graph.


What I've done so far is: I wrote a program that reads these information from a file, calculates the exit degree of each vertex and creates the matrix edge[j].


What data structure do I have to implement???

Archived

This topic is now archived and is closed to further replies.

Go to topic listing

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.

Configure browser push notifications
Chrome (Android)
  1. Tap the lock icon next to the address bar.
  2. Tap Permissions → Notifications.
  3. Adjust your preference.
Chrome (Desktop)
  1. Click the padlock icon in the address bar.
  2. Select Site settings.
  3. Find Notifications and adjust your preference.