如何從鄰接矩陣獲得前任和後繼者

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並找到您感興趣的內容即可。

請注意，除非您的圖形是定向的，否則討論前輩和後繼是沒有意義的，因爲邊是雙向的。你的圖似乎是無向的，所以你確定分配不是要找到一個節點是否可以從另一個節點到達？