depth-first search of a graph
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 5 of 5

Thread: depth-first search of a graph

  1. #1
    Join Date
    Apr 2013
    Posts
    45

    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???

  2. #2
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,003

    Re: depth-first search of a graph

    Quote Originally Posted by mathmari View Post
    What data structure do I have to implement???
    Sounds to me like your matrix is your data structure.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  3. #3
    Join Date
    Apr 2013
    Posts
    45

    Re: depth-first search of a graph

    So do I have only to implement the matrix edge[i][j], 1<=j<=deg[i], and then write the function dfs that has as argument this matrix (void dfs(int edges[][])) ?
    Last edited by mathmari; May 19th, 2013 at 05:30 AM.

  4. #4
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,003

    Re: depth-first search of a graph

    Quote Originally Posted by mathmari View Post
    So do I have only to implement the matrix edge[i][j], 1<=j<=deg[i], and then write the function dfs that has as argument this matrix (void dfs(int edges[][])) ?
    It's actually not correct to call this a matrix, because it may not have the same number of columns in each row. The correct term would be jagged array. This also means that you cannot create it as a static array (at least, not easily); you'll have to make a dynamic array or (better) use a std::vector. Then you can pass it to a function.
    Cheers, D Drmmr

    Please put [code][/code] tags around your code to preserve indentation and make it more readable.

    As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky

  5. #5
    Join Date
    Apr 2013
    Posts
    45

    Re: depth-first search of a graph

    Ok.. Thank you very much!!!!!!

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center