Nano Hash - криптовалюты, майнинг, программирование

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

Допустим, у нас есть матрица смежности 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 
                    }
                }
            }
        }
graph algorithm matrix
12.01.2017

Ответы:


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 
    }
}
12.01.2017

2

Если A — матрица смежности, рассмотрите A^2, построенный умножением матриц с AND для скалярного произведения и суммированием с OR. Стоимость члена

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

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

12.01.2017
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..