Реализация ориентированного взвешенного графика (смежная матрица) - PullRequest
Новая
       27

Реализация ориентированного взвешенного графика (смежная матрица)

2 голосов
/ 08 апреля 2020

Мне нужна помощь в реализации ориентированного взвешенного графа в java с использованием матрицы смежности. Не знаете, как проверить, есть ли соединенные ребра или как их удалить, знаете только, как добавить ребра. 

// Implementation of directed weighted Graph using Adjacent Matrix

public class Graph {
    private int size;
    private int adjacentMatrix[][];


public Graph (int size) {
    this.size = size;
    adjacentMatrix = new int [size][size];
}


public void addEdge (int source, int destination, int weight) {
    if (source < size && source >= 0 && destination < size && destination >= 0)
        adjacentMatrix [source][destination] = weight;
    }

// need help in this function for what to set second line equal to or new function in general
public void removeEdge (int source, int destination, int weight) {
    if (source < size && source >= 0 && destination < size && destination >= 0)
        adjacentMatrix [source][destination] = 0;  //(not sure)
    }


//need help with this entire function
//function to check if edges are connected
public boolean isEdge(int source, int destination) {
    if(size >= 0 && size < size && destination >= 0 && destination < size) {
        if(adjacentMatrix[source][destination] == 1)
            return true;
        else
            return false;
     }
  }
 }   
}

 // I'm not sure if I did this correct at all any help would be appreciated

Ответы [ 3 ]

0 голосов
/ 08 апреля 2020

Вы почти поняли это!

Предполагая, что в вашей матрице смежности значение 0 означает, что нет ребра, а значение больше 0 означает, что есть ребро с таким весом.

Метод removeEdge не нуждается в weight, поскольку он удаляет ребро. Установка в 0 здесь правильна, так как 0 означает «без края». 

public void removeEdge (int source, int destination) {
    if (source < size && source >= 0 && destination < size && destination >= 0)
        adjacentMatrix [source][destination] = 0;
    }
}

Поскольку вам сказали указать параметр weight, возможно, вы должен удалять ребро только в том случае, если вес соответствует переданному в весе?

Метод isEdge должен проверять adjacentMatrix[source][destination] > 0 вместо adjacentMatrix[source][destination] == 1, так как любое положительное значение означает «есть ребро». 

public boolean isEdge(int source, int destination) {
    if(size >= 0 && size < size && destination >= 0 && destination < size) {
        return adjacentMatrix[source][destination] > 0;
    } else {
        return false; // if out of range, no edge
    }
}
0 голосов
/ 08 апреля 2020

В addEdge нет ограничений по весу, поэтому вес может иметь любое значение, включая 0. Так что 0 - не лучший выбор для указания отсутствия грани.
Я бы порекомендовал установить вес на бесконечный. Имеет смысл применять бесконечный вес там, где нет ребра:

adjacentMatrix [source][destination] =Integer.MAX_VALUE;

Для этого может потребоваться инициализация всего массива adjacentMatrix[][] до Integer.MAX_VALUE при запуске: 

  for(int[] row : adjacentMatrix)
        Arrays.fill(row, Integer.MAX_VALUE);
  }

isEdge также становятся простыми и удобочитаемыми: 

public boolean isEdge(int source, int destination) {
       if(size >= 0  
            && destination >= 0 && destination < size
            && source >= 0 && source < size ) 
                    return adjacentMatrix[source][destination] != Integer.MAX_VALUE;                        
        return false;            
}
0 голосов
/ 08 апреля 2020

Чтобы удалить ребро, вы можете просто изменить эту ячейку соседней матрицы на 0 (что было на стадии по умолчанию).

...