Ajuda em grafos/recursividade

[Miguel M.]

Boas pessoal, estou de momento a aprender Grafos/recursividade e não consigui fazer um exercicio, vou deixar ai o que pretendia e o que fiz ate agora para me poderem ajudarem.

Eu queria basicamente ver quantos numeros 1 existe, mas queria usar o metodo: Depth-First Search.

#include <cstdlib>
#include <vector>
#include <cmath>
#include <iostream>
using namespace std;
bool visited[6];
void dfs (int node)
{
  if (visited[node] == true)
	return;
  visited[node] = true;
  for (i = 0; i < 6; i ++)
	if (ligacoes[node][i] == 1)
	  dfs(i);
}


int main()
{  
	vector<int> id_val_vec; // guardar o ID da respectiva bola
	vector< pair<int,int> > ligacoes;  //ligacoes entre os ID's das bolas
	int num,x,y,bola;
	// leitura
	for(int i=0;i<6;i++){
	cin>>bola; id_val_vec.push_back(bola);
	cin>>x>>y; ligacoes.push_back( pair<int,int>(x,y) );
	}

	for (int i=0;i<6;i++)
	visited[i] = false;

system("pause");
	return 0;
}
[/Code]

[pikax]

nao testei mas a variavel "ligacoes" nao esta declarada na funcao dfs

[pedrosorio]

Não estás a chamar a função dfs em nenhum momento.

Dentro da função dfs estás a usar uma notação para as "ligacoes" como se tivesses uma matriz, na realidade tens um vector de pairs, portanto claramente não podes fazer isso dessa forma.

Qual é o problema que estás a resolver de facto? Contar quantas bolas têm id=1? O grafo é sempre conexo? Porquê dfs?

[Miguel M.]

O exercicio era ter as bolas e as ligaçoes entre as bolas e queria ver quantidade de bolas com o ID 1.

Estava a seguir esta parte de DFS por aqui:

http://i45.tinypic.com/den3ty.jpg

falta esta parte:

  for (int i = 0; i < 7; i ++)
    if (ligacoes[node][i] == 1){
	 soma++;
	  dfs(i);}
...
...
    for (int i=0;i<6;i++)
    visited[i] = false;
[u][b]    dfs(soma);[/b][/u]
[/Code]

Devo ter ai muitos erros e é bem normal visto que estou a pegar em grafos com recursividade pela primeira vez 😕

[pikax]

Não estás a chamar a função dfs em nenhum momento.

Nao estas a chamar a funcao dfs na main!!