Zliczanie "głębokości" z każdego wierzchołka w grafie.

Witam.
Ciężko mi było sensownie nazwać temat, ale chodzi o to, by dla wierzchołka w grafie zliczyć odległość / liczbę wierzchołków do dowolnego końca grafu. Może lepiej na przykładzie rysunku:

Biorę sobie konkretny wierzchołek, dla tego przypadku będzie to wierzchołek nr. 3. Wiem, jak zliczyć wychodzące od niego wierzchołki (4), ale chciałbym znaleźć odpowiednio odległości do końca grafu. Np. kolejno od lewej strony to: 2, 2, 2, 3. Bardzo dziękuję za pomoc :)
Na razie zakodziłem coś takiego:

typedef std::vector<std::set<int> > Graph;

class MyGraph
{
public:
    Graph graph;

    void addEdge(int vertex1, int vertex2)
    {
        graph[vertex1].insert(vertex2);
        graph[vertex2].insert(vertex1);
    }

    void printList()
    {
        for(size_t vertex = 0; vertex < graph.size(); ++vertex)
        {
             std::cout << "vertex " << vertex << ": ";
             for(std::set<int>::const_iterator ad_vertex = graph[vertex].begin(); ad_vertex != graph[vertex].end(); ++ad_vertex)
             {
                  std::cout << *ad_vertex << " ";
             }
             std::cout << std::endl;
        }
    }

    int getConn(int &vertex)
    {
        int connections = 0;
        for(std::set<int>::const_iterator ad_vertex = graph[vertex].begin(); ad_vertex != graph[vertex].end(); ++ad_vertex)
        {
            connections++;
        }
        return connections;
    }

    void letsgo()
    {
        int connections = getConn(3); // wynik: 4

        // jak wyszukiwać dla wierzchołka 3 odległości do końca grafu.
    }
};

int main()
{
    MyGraph x;

    x.graph.resize(10);

    x.addEdge(0, 1);
    x.addEdge(1, 2);
    x.addEdge(2, 7);
    x.addEdge(7, 8);
    x.addEdge(5, 6);
    x.addEdge(6, 2);
    x.addEdge(2, 3);
    x.addEdge(3, 4);
    x.addEdge(9, 10);
   
    return 0;
}

Algorytm Dijsktry?

Jeżeli ten graf będzie zawsze wyglądał tak jak ten na rysunku (czyli będzie to drzewo), to wystarczy DFS. W przeciwnym wypadku musisz użyć przynajmniej Dijkstry co zasugerował @Shalom.

Jeżeli masz graf nieskierowany, spójny (istnieje drogę pomiędzy dowolną parą wierzchołków) oraz ilość krawędzi równa n-1 gdzie n - ilość wierzchołków to DFS jest wystarczający jak to napisał wyżej @winerfresh

Dzięki za odpowiedzi. Graf jest nieskierowany, nie zawiera cykli, spójny oraz ilość krawędzi jest równa ilości wierzchołków - 1. W sumie ten program jest moim pierwszym wyzwaniem dotyczącym grafów i nie za bardzo rozumiem jak się za tego DFSa zabrać. Moglibyście mi jakoś nakreślić, co mam dalej zrobić, w jaki sposób do tego podejść, by uzyskać możliwe drogi do ostatnich wierzchołków?

http://pl.wikipedia.org/wiki/Przeszukiwanie_w_głąb

Coś w tym stylu:

    int deep(int vertex)const
      {
       int deepcount=0;
       std::set<int> mark;
       mark.insert(vertex);
       std::list<std::pair<int,int> > Q;
       Q.push_back(std::pair<int,int>(vertex,0));
       while(!Q.empty())
         {
          vertex=Q.front().first;
          int deep=Q.front().second;
          Q.pop_front();
          if(deepcount<deep) deepcount=deep;
          for(std::set<int>::const_iterator i=graph[vertex].begin();i!=graph[vertex].end();++i)
            {
             if(mark.find(*i)==mark.end())
               {
                mark.insert(*i);
                Q.push_back(std::pair<int,int>(*i,deep+1));
               }
            }
         }
       return deepcount;
      }

Dzięki wielkie. Tak to przeanalizowałem i ta funkcja zwraca możliwie "najdłuższą" drogę. W jaki sposób mogę ją zmienić, by zwracał najkrótszą? Kombinuję, kombinuję i albo zwraca mi 0 albo wysypuje program.

pablo7890 napisał(a):

W jaki sposób mogę ją zmienić, by zwracał najkrótszą?

Jedno z dwóch:

1. jeżeli akceptowana droga do samego siebie:

    int shortest_deep(int vertex)const
      {
       return 0;
      }

2. jeżeli NIE akceptowana droga do samego siebie:

    int shortest_deep(int vertex)const
      {
       return graph[vertex].begin()!=graph[vertex].end();
      }