Algorytm DFS i BFS modyfikacja

0

Witam

Nie jestem za dobry w C. Pytanie 1 Czy biblioteka STL jest instalowana standardowo przy instalacji czy trzeba ją pobrać z internetu?
Program który umieściłem poniżej przeszukuje graf metodą BFS i DFS. Korzysta jednak z amcierzy sąsiedztwa której struktura wygląda tak:

6 / gdzie 6 to liczba wierzchołków poniżej połączenia pomiędzy wierzchołkami

0 1 1 0 0 0
0 0 0 1 1 0
0 0 0 1 0 1
1 0 0 0 0 0
0 0 0 1 0 0
0 0 0 0 0 0

Chciałbym przerobić to tak żeby program korzystał z danych opisujących połączenie między danymi wierzchołkami czyli

6
0 1
0 2
1 3
1 4
2 3
2 5
3 0
4 3
3 5

W jaki sposób przerobić zamieszczony kod ?
Proszę o pomoc

Swoje rozwiązanie chciałbym testować na ideone.com . Jak zmodyfikować wejście i wyjście( powinno być standardowe)
Pozdr

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <vector.h>    	//STL
#include <list.h>    	//STL
#include <stack.h>      //STL
#include <queue.h>      //STL


#define Max_Nodes 10		//Maksymalna liczba wierzcholkow w macierzy
using namespace std;

int Macierz[Max_Nodes][Max_Nodes];
int Odwiedzony[Max_Nodes];
int LiczbaWierzcholkow;
//Stos do przechowywania wierzcholkow w DFS
stack<int,vector<int> > stos;
//Kolejka do przechowywania wierzcholkow w BFS
queue<int, list<int> > kolejka;

//Funkcja zwraca OSTATNI nieodwiedzony nastepnik wierzcholka v
int nastepnik_dfs(int v)
{
int i;

for (i=LiczbaWierzcholkow-1;i>=0;i--)
if ((Macierz[i][v]==1)&&(Odwiedzony[i]==0))
  {
  Odwiedzony[i]=1;
  return(i);
  }

//Wierzcholek v nie ma juz nastepnikow do odwiedzenia
return(-1);
}


//Funkcja zwraca PIERWSZY nieodwiedzony nastepnik wierzcholka v
int nastepnik_bfs(int v)
{
int i;

for (i=0;i<LiczbaWierzcholkow;i++)
if ((Macierz[i][v]==1)&&(Odwiedzony[i]==0))
  {
  Odwiedzony[i]=1;
  return(i);
  }

//Wierzcholek v nie ma juz nastepnikow do odwiedzenia  
return -1;
}

void dfs(int v)
{
int u;
int nastepny;
printf("%d ",v+1);
Odwiedzony[v]=1;
nastepny=nastepnik_dfs(v);
while (nastepny!=-1)
 {
 stos.push(nastepny);
 nastepny=nastepnik_dfs(v);
 }
if (!stos.empty())
 {
 u=stos.top();
 stos.pop();
 dfs(u);
 }
}

void bfs(int v)
{
int u;
int nastepny;
printf("%d ",v+1);
Odwiedzony[v]=1;
nastepny=nastepnik_bfs(v);
while (nastepny!=-1)
 {
 kolejka.push(nastepny);
 nastepny=nastepnik_bfs(v);
 }
if (!kolejka.empty())
 {
 u=kolejka.front();
 kolejka.pop();
 bfs(u);
 }
}

void main(void)
{
FILE *Plik_We;
int i,j;

for (i=0;i<Max_Nodes;i++)
  Odwiedzony[i]=0;

Plik_We=fopen("graf.txt","rt");
fscanf(Plik_We,"%d",&LiczbaWierzcholkow);

for (j=0;j<LiczbaWierzcholkow;j++)
 for (i=0;i<LiczbaWierzcholkow;i++)
   fscanf(Plik_We,"%d",&Macierz[i][j]);

//DFS
printf("Przeszukiwanie DFS: ");
dfs(0);

for (i=0;i<Max_Nodes;i++)
  Odwiedzony[i]=0;

//BFS
printf("\nPrzeszukiwanie BFS: ");
bfs(0);
printf("\n\n\nDowolny klawisz...");
getch();
fclose(Plik_We);
return;
}

 
0

Obsługa tego formatu różni się tym że nie wczytujesz po kolei do elementów macierzy a to, gdzie mają być jedynki (w tym wypadku i,j).

1 użytkowników online, w tym zalogowanych: 0, gości: 1