僅使用深度優先搜索獲取相鄰頂點

如何僅使用深度優先搜索獲取相鄰頂點？僅使用深度優先搜索獲取相鄰頂點

我正在使用深度優先搜索算法來搜索定向圖，我的問題是我想讓它只返回我的開始頂點的鄰居，而不是繼續進行直到它到達死衚衕。（A - > B），（A - > C），（C - > D））我希望所有的鄰居都有頂點（A，B，C，D）的頂點A，而不是獲得B和C，它也包括D，儘管D不是與A相鄰？

public void dfs(int x) // depth-first search 
    {         // begin at vertex 0 
    vertexList[x].wasVisited = true; // mark it 
    displayVertex(x);     // display it 
    theStack.push(x);     // push it 

    while(!theStack.isEmpty())  // until stack empty, 
    { 
    // get an unvisited vertex adjacent to stack top 
    int v = getAdjUnvisitedVertex(theStack.peek()); 
    if(v == -1)     // if no such vertex, 
     theStack.pop(); 
    else       // if it exists, 
     { 
     vertexList[v].wasVisited = true; // mark it 
     displayVertex(v);     // display it 
     theStack.push(v);     // push it 
     } 
    } // end while 

    // stack is empty, so we're done 
    for(int j=0; j<nVerts; j++)   // reset flags 
    vertexList[j].wasVisited = false; 
    } // end dfs 
    // ------------------------------------------------------------ 
    // returns an unvisited vertex adj to v 
public int getAdjUnvisitedVertex(int v) 
    { 
    for(int j=0; j<nVerts; j++) 
    if(adjMat[v][j]==1 && vertexList[j].wasVisited==false) 
     return j; 
     System.out.println("Found unvisited vertex"); 
    return -1; 
    } // end getAdjUnvisitedVertex()

我瞭解創建時，我可以只存儲一個頂點的鄰居，那麼這意味着我將不得不做出了很大的改動，如果我不得不在將來的變化，如果任何人有任何想法如何引導我在正確的方向我將非常感激！

來源

2013-12-14 DanBarber

如果您確實需要使用深度優先搜索，我會假設所有相鄰頂點都有一定的深度，即當您到達它們時，堆棧具有一定的大小。 – andi5

如果你代表你的圖形作爲adjecency矩陣，那麼你應該只是正好可以是從對應於頂點A.

for(int j=0; j<nVerts; j++) 
if(adjMat[v][j]==1) System.out.println("vertex " + j);

，所以你不需要爲DFS行非零的所有條目。

來源

2013-12-14 18:43:15 gregory561

非常感謝它的完美運作。 – DanBarber

稍微挑剔（對不起），但即使OP明確提到他的設置並且頂點之間的邊數爲1，但在更一般的情況下，如果兩個頂點之間的邊多於1，上述_code_將不起作用。例如，如果A-> B和B-> A，但是使用不同的邊緣，則它們共有的鄰接矩陣條目都將具有2而不是1，並且if條件將失敗。當然你的描述是正確的 - 「從行中取出所有非零的條目......」 –

僅使用深度優先搜索獲取相鄰頂點

回答

相關問題