Как получить предшественника и преемников из матрицы смежности

Question

Привет. Я пытаюсь выполнить задание, где можно проконсультироваться с онлайн-сообществом. Я должен создать класс графика, который в конечном итоге может выполнять поиск в ширину и вначале поиск по глубине. Я смог успешно реализовать эти алгоритмы, однако еще одно требование - уметь получать преемников и предшественников и определять, являются ли две вершины предшественниками или преемниками друг друга. У меня проблемы с поиском способа сделать это. Я опубликую свой код ниже, если у кого-то есть какие-либо предложения, это будет с благодарностью.

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;


public class Graph<T> 
{
 public Vertex<T> root;
 public ArrayList<Vertex<T>> vertices=new ArrayList<Vertex<T>>();
 public int[][] adjMatrix;
 int size;
 private ArrayList<Vertex<T>> dfsArrList;
 private ArrayList<Vertex<T>> bfsArrList;

 public void setRootVertex(Vertex<T> n)
 {
  this.root=n;
 }

 public Vertex<T> getRootVertex()
 {
  return this.root;
 }

 public void addVertex(Vertex<T> n)
 {
  vertices.add(n);
 }

 public void removeVertex(int loc){
  vertices.remove(loc);
 }

 public void addEdge(Vertex<T> start,Vertex<T> end)
 {
  if(adjMatrix==null)
  {
   size=vertices.size();
   adjMatrix=new int[size][size];
  }

  int startIndex=vertices.indexOf(start);
  int endIndex=vertices.indexOf(end);
  adjMatrix[startIndex][endIndex]=1;
  adjMatrix[endIndex][startIndex]=1;
 }

 public void removeEdge(Vertex<T> v1, Vertex<T> v2){

  int startIndex=vertices.indexOf(v1);
  int endIndex=vertices.indexOf(v2);
  adjMatrix[startIndex][endIndex]=1;
  adjMatrix[endIndex][startIndex]=1;
 }

 public int countVertices(){
  int ver = vertices.size();
  return ver;
 }


 /*
 public boolean isPredecessor( Vertex<T> a, Vertex<T> b){

  for()

  return true;
 }*/

 /*
 public boolean isSuccessor( Vertex<T> a, Vertex<T> b){

  for()

  return true;
 }*/

 public void getSuccessors(Vertex<T> v1){

 }

 public void getPredessors(Vertex<T> v1){

 }




 private Vertex<T> getUnvisitedChildNode(Vertex<T> n)
 {

  int index=vertices.indexOf(n);
  int j=0;
  while(j<size)
  {
   if(adjMatrix[index][j]==1 && vertices.get(j).visited==false)
   {
    return vertices.get(j);
   }
   j++;
  }
  return null;
 }

 public Iterator<Vertex<T>> bfs()
 {

  Queue<Vertex<T>> q=new LinkedList<Vertex<T>>();
  q.add(this.root);
  printVertex(this.root);
  root.visited=true;
  while(!q.isEmpty())
  {
   Vertex<T> n=q.remove();
   Vertex<T> child=null;
   while((child=getUnvisitedChildNode(n))!=null)
   {
    child.visited=true;
    bfsArrList.add(child);
    q.add(child);
   }
  }
  clearVertices();
  return bfsArrList.iterator();
 }

 public Iterator<Vertex<T>> dfs()
 {

  Stack<Vertex<T>> s=new Stack<Vertex<T>>();
  s.push(this.root);
  root.visited=true;
  printVertex(root);
  while(!s.isEmpty())
  {
   Vertex<T> n=s.peek();
   Vertex<T> child=getUnvisitedChildNode(n);
   if(child!=null)
   {
    child.visited=true;
    dfsArrList.add(child);
    s.push(child);
   }
   else
   {
    s.pop();
   }
  }
  clearVertices();
  return dfsArrList.iterator();
 }


 private void clearVertices()
 {
  int i=0;
  while(i<size)
  {
   Vertex<T> n=vertices.get(i);
   n.visited=false;
   i++;
  }
 }

 private void printVertex(Vertex<T> n)
 {
  System.out.print(n.label+" ");
 }

}

Answer 1

Смотрите здесь .

Если v достижимо от u, то u является предшественником v, а v является преемником u.Если есть дуга от u до v, то u является прямым предшественником v, а v является прямым преемником u.

Это должно быть тривиально, поскольку вы уже, кажется, имеетепостроена матрица смежности, а также функции обхода.Так что просто запустите BFS / DFS и найдите то, что вас интересует.

Обратите внимание, что, если ваш граф не направлен, нет смысла говорить о предшественниках и преемниках, поскольку ребра двунаправлены.Ваш график кажется ненаправленным, поэтому вы уверены, что задание не позволяет определить, доступен ли один узел другому или нет?

Answer 2

Я считаю, что эта функция ошибочна:

 public void addEdge(Vertex<T> start, Vertex<T> end) {
    if (adjMatrix == null) {
        size = vertices.size();
        adjMatrix = new int[size][size];
    }

    int startIndex = vertices.indexOf(start);
    int endIndex = vertices.indexOf(end);
    adjMatrix[startIndex][endIndex] = 1;
    adjMatrix[endIndex][startIndex] = 1;
}

Второе задание фактически говорит о том, что края не имеют направления. Если я уберу второе задание, то этот тест

import junit.framework.TestCase;

public class GraphTest extends TestCase {
    public void testIsPredecessor() throws Exception {
        Graph<Integer> graph = new Graph<Integer>();
        Vertex<Integer> zero = new Vertex<Integer>(0, "zero");
        Vertex<Integer> one = new Vertex<Integer>(1, "one");
        Vertex<Integer> two = new Vertex<Integer>(2, "two");
        graph.addVertex(zero);
        graph.addVertex(one);
        graph.addVertex(two);
        graph.addEdge(zero, one);
        graph.addEdge(one, two);
        assertTrue(graph.isPredecessor(zero, one));
        assertFalse(graph.isPredecessor(one, zero));
    }
}

может быть передано следующей реализацией:

 public boolean isPredecessor( Vertex<T> a, Vertex<T> b){
      int startIndex=vertices.indexOf(a);
      int endIndex=vertices.indexOf(b);
      return adjMatrix[startIndex][endIndex]==1;
 }

isSuccessor() имеет очевидную реализацию - просто вызовите isPredecessor(b, a). Кстати, метод deleteEdge(), вероятно, должен присваивать 0, а не 1 (и должен делать это только один раз, как addEdge()).