Thread: depth-first search of a graph

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[i] is the exit degree of the vertex i then the neighbors of the vertex i can be saved at the matrix edge[i][j], 1<=j<=deg[i].
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[i][j].
What data structure do I have to implement???

Originally Posted by evinda

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[i] is the exit degree of the vertex i then the neighbors of the vertex i can be saved at the matrix edge[i][j], 1<=j<=deg[i].

Maybe an example helps.

Assume you have NVERTS=16 vertices, and maximum exit degree of each vertex is MAXDEG=5.

If the graph is a directed graph, then that means you have 16 vertices, and each vertex can have up to five outgoing edges. (If it is undirected, each vertex has at most five edges total; any other interpretation of the limits is not practical.)

The adjacency matrix is then a 16-by-16 array, with each cell containing just a boolean value: either "connected with an edge" (true, 1) or "not connected" (false, 0). Each row in the matrix corresponds to source vertices, and each column to target vertices. Undirected graphs have a symmetric adjacency matrix (just as if each edge was defined both ways -- although the undirected graph is fully defined using the triangle above or below the diagonal).

The edge array is an array of 16 entries, one entry per vertex. Each entry is a list (an array) that defines the edges, by listing the vertices at the other ends of each edge. That list can have zero, one, two, three, four, or five entries.

I take it you already have written the code to read and fill the edge array, edge[16][5] in my example?

You're almost done. You see, the requested data structure must define not only the edge array, but also the exit degree for each vertex (so that you know which entries in edge[][] have valid values).

There are three typical approaches:

1. Use separate arrays for the edges and exit degrees
2. Use a struct to describe the exit degree, and an array of target vertex identifiers
3. Fill the unused edge array entries with a sentinel value, often -1, which your code checks and interprets as "no edge"
   In this case it is good policy to provide a helper function to return the number of edges (0 to MAXDEG) a vertex has

The first one is the simplest. Your data structure then consists of two arrays. (I don't know whether you're supposed to define a C struct or whether just describing the data structure is enough.)

The second one is better, because it allows you to increase the number of vertices dynamically. (If the target vertex identifiers are also dynamically allocated -- a pointer instead of a fixed-size array --, you can make it very flexible, with a cost of two words per vertex (a pointer and a number describing the allocated size.)

The third one uses the least memory, but finding out the number of edges a vertex has becomes slower. Fortunately, it is rarely needed. Iterating over the target vertices for a vertex is at least as fast as in the other two cases, as long as you have the sentinels ("no vertex" values) all at one end of each list, not scattered between valid values.

Originally Posted by evinda

I wrote a program that reads these information from a file, calculates the exit degree of each vertex and creates the matrix edge[i][j].

Does that array contain boolean (true/1/edge or false/0/no-edge) values, or does it specify target vertices at the other end of each edge? If former, you have an adjacency matrix.

If latter, you have an edge array -- and an edge array does save memory compared to an adjacency matrix.

The exercise asks for a data structure. Your edge[][] array is such a data structure, if you use sentinel values. Otherwise, you also need to describe the exit degree of each vertex.