Flash Website Builder- Trendy Site Builder is a Flash Site Building tool that helps users build stunning websites. Check Out Custom Custom Logo Design by LogoBee. Website Design and Free Logo Templates available.
 CodingForums.com depth-first search of a graph

Before you post, read our: Rules & Posting Guidelines

Enjoy an ad free experience by logging in. Not a member yet? Register.
 05-19-2013, 01:03 AM PM User | #1 mathmari New to the CF scene   Join Date: May 2013 Posts: 5 Thanks: 0 Thanked 0 Times in 0 Posts 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???
 05-20-2013, 10:11 AM PM User | #2 yourveins New Coder   Join Date: May 2013 Posts: 13 Thanks: 1 Thanked 0 Times in 0 Posts It depends. You can do it with an array, if you want to make simple things. Each node has an array, called for example SUCCESSORS, that has MAXDEG elements. As you can imagine it's easy but it's a huge waste of space. If your root node has 10k elements, and his sons are leaves, you'll have an array of 10k elements for each node, even if the one of leaves will be always empty. I'd do it with lists, to gain a dynamical allocation of space for a function that is generic and can be applied successfully to each graph structure.
 05-21-2013, 12:47 AM PM User | #3 mathmari New to the CF scene   Join Date: May 2013 Posts: 5 Thanks: 0 Thanked 0 Times in 0 Posts Ok...Thank you very much!!!

 Bookmarks

 Thread Tools Rate This Thread Rate This Thread: 5 : Excellent 4 : Good 3 : Average 2 : Bad 1 : Terrible

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home :: Client side development     JavaScript programming         DOM and JSON scripting         Ajax and Design         JavaScript frameworks         Post a JavaScript     HTML & CSS     XML     Flash & ActionScript         Adobe Flex     Graphics and Multimedia discussions     General web building         Site reviews         Building for mobile devices :: Server side development     Apache configuration     Perl/ CGI     PHP         Post a PHP snippet     MySQL         Other Databases     Ruby & Ruby On Rails     ASP     ASP.NET     Java and JSP     Other server side languages/ issues         ColdFusion         Python :: Computing & Sciences     Computer Programming     Computer/PC discussions     Geek News and Humour Web Projects and Services Marketplace     Web Projects         Small projects (quick fixes and changes)         Medium projects (new script, new features, etc)         Large Projects (new web application, complex features etc)         Unknown sized projects (request quote)         Vacant job positions         Looking for work/ for hire         Project collaboration/ partnership         Paid work offers and requests (Now CLOSED)     Career, job, and business ideas or advice     Domains, Sites, and Designs for sale         Domains for sale         Websites for sale         Design templates and graphics for sale :: Other forums     Member Offers     Forum feedback and announcements

All times are GMT +1. The time now is 06:28 AM.