如何从邻接矩阵获得前任和后继者

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

我相信这个功能是错误的：

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()）。

Answer 2

Look here。

If v is reachable from u, then u is a predecessor of v and v is a successor of u. If there is an arc from u to v, then u is a direct predecessor of v, and v is a direct successor of u.

它应该是微不足道的实现这一点，因为你似乎已经建立了邻接矩阵和遍历函数。因此，只需运行BFS/DFS并找到您感兴趣的内容即可。

请注意，除非您的图形是定向的，否则讨论前辈和后继是没有意义的，因为边是双向的。你的图似乎是无向的，所以你确定分配不是要找到一个节点是否可以从另一个节点到达？