C :: Depth-first Search Of A Graph
May 18, 2013
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???
View 1 Replies
ADVERTISEMENT
Mar 12, 2013
I'm having problems with implementing depth first search.
Code:
6 10 //6vertices 10edges
0 2 //vertex and its adjacent vertex
1 0
1 2
2 3
2 4
3 1
4 1
4 3
4 5
5 3
Output to terminal: 0 2 3 1 4 5
but it should be: 0 2 4 5 3 1
Here's my code:
#include<stdio.h>
#include<assert.h>
/* maxVertices represents maximum number of vertices that can be present in the graph. */
#define maxVertices 100
void Dfs(int graph[][maxVertices], int *size, int presentVertex,int *visited)
[Code] ....
View 1 Replies
View Related
Jan 13, 2013
I've been trying to implement this Depth First Search graph algorithm using STL, and I get some error from Visual C++ 2012 at compilation.
The code is:
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
[Code].....
And the error says something like this:
Debug Assertion Failed!
Program: C:WindowsSYSTEM32MSVCP110D.dll
File: d:...vs2012vcincludedeque
Line: 1497
Expression: deque empty before pop
View 1 Replies
View Related
Mar 15, 2014
I am not sure how to have to user input numbers into a tree and to have it print out the steps it takes to reach the goal
Header File
#include <iostream>
#include <stack>
using namespace std;
bool recursive_depth(int);
bool is_goal(int);
void input_tree();
void print_tree();
[Code] .....
View 4 Replies
View Related
Nov 1, 2014
What I have done : Created functions to accept inputs from user and read,print out adjacent matrix.
What I need : How do I start DFS in adjacent matrix so that I can output the vertices of each connected component of a graph? I'm confused with adjacent matrix and the term 'component'.
#include <stdio.h>
#include <iostream>
#define maxV 8
using namespace std;
int V,E,x,y;
int a[maxV][maxV];
[Code] .....
View 7 Replies
View Related
Mar 22, 2013
Any example of a graph search algorithm that uses a recursion and linked list based stacks to determine a route from a single point on a graph to another single point on a graph?
View 3 Replies
View Related
Mar 26, 2014
I'm new to program breadth first search and for my assignment we have to implement a breadth first search graph and output the order of the traversal. The problem is when I run my program I do not get any output from my traversal. All I get is "Breadth First Search Traversal starts at Vertex 2 and the order is: "
Here is my Queue class
//Declaration of node
struct node{
int info;
node *next;
};
//Defining Queue class
class Queue{
[Code] ....
View 4 Replies
View Related
Feb 23, 2014
I'm in interested to know what will be the height of binary tree with say 5 nodes (consider it balanced) is it 2 or 3?
9
/
5 13
/
3 7
and for following tree also:
2
/
7 5
/
2 6 9
/ /
5 11 4
is it 3 or 4?
i'm asking because, not able to find correct/one answer.
the algorithm i find is:
depth(struct tree*t) {
if ( t == NULL) return 0;
return max( depth(tree->left), depth(tree->right) ) + 1;
}
According to it, ans for second will be 4
But as per image on wikipedia [URL] .... the ans is 3
View 6 Replies
View Related
Feb 21, 2013
Write a program that displays n depth * pyramid.
For example,Input: 4
Output:
*
***
*****
*******
This is what i have so far but it not giving me what i want.
#include <iostream>
using namespace std;
int main() {
int star;
int count=1;
cout<<"Enter the number: ";
cin>>star;
[Code] ....
View 1 Replies
View Related
Apr 1, 2013
i have come across this code for calculating the depth of a binary tree.
int maxDepth(Node *&temp) {
if(temp == NULL)
return 0;
else {
int lchild = maxDepth(temp->left);
int rchild = maxDepth(temp->right);
[Code] ....
In these recursive calls i am really clue less about how the statements i numbered from 1 to 4 would be executed...in every recursive call...???
Lets temp has left depth of 3 and right depth of 100 then...in last 97 recursive calls max(temp->left) would be doing...????? how these recursive mechanism work here... I want to know specifically how these left node and right node recursive calls are co-ordinating with each other????
View 2 Replies
View Related
Jul 9, 2014
I wrote this code, but now need to apply a limit to the recursive depth. This is the format that I have to use. How would I pass a limit so that it stops after a given number? I'm just confused about where to apply it.
int compute_edit_distance(char *string1, char *string2, int i, int j, int limit) {
if (strlen(string1) == i) return strlen(string2) - j;
if (strlen(string2) == j) return strlen(string1) - i;
if (string1[i] == string2[j]) return compute_edit_distance(string1, string2, i + 1, j + 1, limit);
[Code] .....
View 4 Replies
View Related
Mar 5, 2013
Code:
/* Sudoku solver using dept-first search*/
#include <iostream>
#include <stack>
using namespace std;
struct valpos//structure which carries information about the position of the cell and its value {
int val;
int row;
int col;
[Code] ....
View 3 Replies
View Related
Mar 7, 2013
I am trying to implement a Task scheduler where i have n number of tasks. The Idea behind my task scheduler is that in a loop of queues of a vector, task should get enqueued to the shortest queue among the loop of queues, which is done by the following code.
#include <vector>
#include <queue>
std::vector<std::queue<int> > q
int min_index = 0;
task t // implemented in the other part of the program
[Code] ....
Next i am trying to extend this paradigm to reduce the overhead time of the scheduler, Instead of searching the shortest queue every time, search after some condition ie. search the shortest queue after 5 tasks gets enqueued to the shortest queue.
i need to do something like this
#include <vector>
#include <queue>
std::vector<std::queue<int> > q
task t // implemented in the other part of the program
while(q[min_index].size()!=q[min_index].size()+5) // check whether current min_index queue's size is increased 5 more times if not goto enqueue
[code].....
View 1 Replies
View Related
Sep 16, 2013
Write a program to find the number of comparisons using the binary search and sequential search algorithms
//main.cpp
#include <cstdlib>
#include <iostream>
#include "orderedArrayListType.h"
using namespace std;
int main() {
cout << "." << endl;
[code]....
View 4 Replies
View Related
Oct 7, 2014
inputting a search array. I tried putting a binary search but I can't get it to work. everything else works up until I put the value I am searching for in the array, then it just crashes.
How it suppose to work: input 2 coordinates with a value each then it calculates the distance between them then it suppose to let user search the coordinates for a value and state if found which coordinate it is at.
#include "stdafx.h"
#include <iostream>
#include <iomanip> //for setprecision
#include <math.h>
[Code].....
View 3 Replies
View Related
Feb 12, 2014
i have to make a programs that prompts the user to enter quiz grades and add them up. For examples the user enters 6 test grades they are out of 5 so he enters 0-5 and i store them in the array. This part works great but now i have to print out a bar of vertical asterisks for every part too. So if at the end we have one test grades that are 2 grades of 1 points, 1 grade of two point, 2 grades of three point and 1 grade of 5 point it will have to display them as this
There are 2 grades of 1
There are 1 grades of 2
There are 2 grades of 3
There are 1 grades of 5
i need to do for loops but i am stuck on what to count too and what to print i know i will need cout << "*" and a couple of spaces.
#include <iostream>
using namespace std;
int main (){
int size;
int tests;
int a[6]={0};
cout << "How many quiz scores will you enter: ";
cin >> size;
[code]....
View 1 Replies
View Related
Oct 29, 2013
this is my first year programming, and in my class, each week we have to write a program. last week we wrote a program in c that made random value point and made a graph of the random points that continued on forever. this week, we have to use statistical functions to find the sum, mean, max, and min of the graph. below is the code i have so far.
Code:
#include <stdlib.h>
#include <strings.h>
#include <stdio.h>
#include <stdbool.h>
#include "SwinGame.h"
[code]....
so, as you can see from the code, the parts i need are finding/ coming up with a function to find the max min sum and mean of the functions.
View 7 Replies
View Related
May 24, 2013
for an assignment we need to create basically a program that asks the user for the result of standard six-sided die rolls (numbers from 1 to 6). The program will prompt the user with "Enter a die roll or 0 to exit " for the first entry and Next die roll? for all subsequent entries. The program will continue reading die rolls from the user until the user enters 0. At this point, the program prints two newline characters (one blank line) and finally, the bar chart showing the number of times each die roll has been entered, and then terminates.If the user enters an invalid number, the program will just ignore it, and ask for another number. Only numbers 1-6 inclusive and 0 are valid.
Example output Enter a die roll or 0 to exit 6 Next die roll? 6 Next die roll? 7 Next die roll? 4 Next die roll? 0
[code].....
View 3 Replies
View Related
Apr 16, 2014
I am using koolplot plot graph and able to plot two lines in a graph. My question is how to fill between the lines? Is it possible to do so with koolplot? or i should use another library?
View 2 Replies
View Related
Jan 5, 2014
I am trying to compare two vectors and make a bar graph. I have tried sorting it and pushing it into another vector but this issue is when I go to output it. My logic is wrong.
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <iomanip>
int main(int argc, const char * argv[]) {
[Code] ....
Output
22 *
44 *
22 *
45 *
33 *
44 *
18 *
34 *
33 *
12 *
3 *
5 *
34 *
33 *
5 *
7 *
22 *
44 *
49 *
9 *
18 *
View 3 Replies
View Related
Mar 30, 2014
I used a BFS to simulate graph-join structure in a C++ code, and had a binary tree that asks the user e.g. to insert a node in the tree among other options, anyhow, I reached a point where I should pass a set of vertices from the graph to the tree, but how to do so. So I wanted to ask is such a thing possible? i.e. passing vertices from a graph to a tree automatically (no user involvement is needed)?
View 4 Replies
View Related
May 3, 2014
"My Programm is crashing and i dont know why?"
#include<iostream>
using namespace std;
int arr[3];
struct edges {
int edge_data;
edges *next;
[code]....
View 1 Replies
View Related
Apr 13, 2013
I need building a complete graph from a file. The format in the file is as follows.
[ vertex 1] [ x_coordinate 1] [ y_coordinate 1] [cityname 1]
[ vertex 2] [ x_coordinate 2] [ y_coordinate 2] [cityname 2]
. . .
[ vertex n] [ x_coordinate n] [ y_coordinate n] [cityname n]
What kind of data structure shall I use in order to store date in a complete graph so there is an edge between every pair?
View 7 Replies
View Related
Dec 29, 2013
I was asked to find the longest path in a graph. I was thinking about using Dijsktra's algorithm after multiplying all the weights with -1 and run the program in normal way and find the shortest path. And then I'll multiply with -1 again and get the longest path. I think this should give me the longest path, do you think it would work? And also, I'm dealing with considerably big data, such as 1.000.000 nodes and many more edges. etc. and I have a time limit of 2 seconds and memory limit of 128mb. Any other data structure instead of Adjacency Matrix? Because I'm pretty sure it will exceed the limits.
View 2 Replies
View Related
Apr 18, 2012
I wrote class DFS - Depth-first search. This algorithm check that this graph is consistent. Below is code of class
Code:
#ifndef DFS_H
#defineDFS_H
class DFS{
private:
std::stack<int, std::vector<int> > stos;//stos do przechowywania wezlow w dfs'ie
int *odwiedzony;
int liczbaWezlow;
[Code] ....
When i initialize dfs i use 2 parameters. On the next step i would like show all content array odwiedzony. Regardless of the given parameters of the array always has a value of zero. Where i made mistake and how to repair?
View 10 Replies
View Related
May 29, 2013
I have a 'Graph' class, which has derived classes for Adjacency Matrix and Adjacency List representations.
How do I provide iterators for traversing vertices and edges, when the iterator classes would have different implementations for the different derived classes ?
The following way is the only one I can think of, but seems quite cumbersome.
Code:
class Base {
public:
class BaseIterator {
};
virtual const BaseIterator& begin();
virtual const BaseIterator& end();
[Code] .....
Or is there a pattern for doing this that I'm not aware of ? Would composition be a better idea here compared to polymorphism ? I mean, I can think like..a Graph can 'have' several representation 'objects' within it.
All the involved classes are templates,not sure if that makes the situation different.
View 7 Replies
View Related
