В матрице смежности, как найти соседние соседние вершины?

Question

Допустим, мы имеем матрицу 4x4 смежности так:

и данную вершину, скажем int v=1

как я нахожу сосед вершины 1 в сосед, и добавить их в список ? Например, если я хочу перейти от вершины 1 к вершине 4, сначала нужно перейти к вершине 2, а затем от вершины 2 до вершины 4, так как нет прямого пути от 1 до 4. И я хочу добавить вершину 4 и как список.

Прямо сейчас вот что я получил:

int v=1; 
for(int i=0;i<adjmat.length;i++){ 
      if (i==v){ 
       for(int j=0;j<adjmat[i].length;j++){ 
        if (j!=i){ // self loops do not count 
         // if adjmat[i][j] has a neighbor, add the neighbor to a list 
        } 
       } 
      } 
     } 

Answer 1

То, что вы, кажется правильным.

Всего несколько заметок: В вашей графической информации есть индексы, начинающиеся с 1, когда ваши циклы начинаются с 0. Вы, вероятно, не беспокоитесь об этом, но в любом случае предположим, что вершины названы, начиная с 1, и что ваши массивы начинаются с 0.

Тогда единственная реальная проблема - ваш самый дальний цикл. Если вам нужно только, чтобы найти соседей соседей одной вершины V (ваш пример, v = 1)

int v_i = v-1; 
for(int j=0;j<adjmat[v_i].length;j++){ 
    if (v_i!=j){ // self loops do not count 
     // if adjmat[i][j] has a neighbor, add the neighbor to a list 
     //*NOTE maybe only if that neighbor is also not a self loop, one of v's first neighbors, or v 
    } 
} 

Answer 2

Если А является матрица смежности, рассмотрим А^2 построены матрицы умножения и для внутреннего продукта и суммирование с помощью OR. Значение члена

A^2(i,j) = OR(k){ A(i,k) AND A(k,j) } 

Это говорит i подключен к j, если существует k таким образом, что i подключен к k и k подключен к j. Таким образом, эта матрица представляет собой график, образованный путем соединения каждой пары вершин, которые могут быть связаны двумя ребрами в исходном графике.