Блог пользователя removeit

Список смежности
Автор removeit, 12 лет назад, По-русски

Объясните как реализовывать и пользоваться cписками смежности.

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
12 лет назад, # |
← Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

В списках смежности используется 3 массива ls, r, prev.

В ls[v] хранится номер последнего ребра с которым связана вершина v, r[i] будет хранить номер вершины на которую ведет ребро i, prev[i] хранит номер ребра с которым вершина v была связана до ребра i.

Реализация:

for (i = 1; i <= m; i++)	{
	cin>>v>>u;
	prev[i] = ls[v];
	ls[v] = i;
	r[i] = u;
}

m — кол-во ребер.

→ Ответить
  • »
    »
    12 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    Если честно, то я так и не понял в чем суть. Список смежности — это структурка, где для каждой вершины храним в динамическом списке смежные вершины. В C++ делается через std::vector.

    UPD:

    struct vertex
{
    vector<int> path;
};

vertex G[n];
    → Ответить
»
12 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Легче всего, мне кажется, так делается (на с++):

vector <vector <int> > graph(MaxN);
while (M--){
cin >> u >> v;
--u, --v; // если нумерация с 1 начинается
graph[u].push_back(v);
graph[v].push_back(u);
}

Получается, что graph[v] будет хранить список вершин связанных с вершиной v. Вот код:

cout << "Vertex " << v << " connected with: ";
for (int i = 0; i < graph[v].size(); i++) {
cout << graph[v][i] << " ";
}

И вот собственно dfs():

void dfs(int v){
was[v] = true;
for (int i = 0; i < graph[v].size(); i++) {
    int to = graph[v][i]; // to -- вершина, связанная с вершиной v
    if (!was[to])
       dfs(to);
  }
}
→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Мне кажется, или graph[v] будет хранить вектор векторов, а не список смежных вершин?

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      graph[][] сам по себе вектор векторов, а graph[v] -- это вектор (список вершин)

      → Ответить
      • »
        »
        »
        »
        12 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

        Я имею ввиду, что если объявлять:

        vector< vector<int> > graph[MaxN];

        То graph будет массивом, где в одной ячейке вектор векторов. graph получается трехмерным.

        → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
          ← Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

          Да, это неверно. Нужно просто 

          vector<vector<int> > g;

          или же 

          vector<int> g[MaxN];
          → Ответить
        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Да, точно! Просто я перепутал: вместо круглых скобок, написал квадратные)

          → Ответить
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

моё http://codeforces.net/blog/entry/5195 подробное объяснение на эту тему, если есть вопросы — задавай!

→ Ответить