깊이 첫 번째 검색을 사용하여 인접 꼭지점 만 가져 오기

Question

깊이 우선 검색을 사용하여 인접 꼭지점을 얻는 방법?

우선 그래프를 검색하기 위해 깊이 우선 검색 알고리즘을 사용하고 있습니다. 문제는 내 시작점의 이웃 노드 만 반환하려는 것입니다. 대신에 막 다른 곳에 도달 할 때까지 계속 수행합니다.

그래서 vertex (A, B, C, D)가 있다고 가정합시다 그리고 가장자리 ((A -> B), (A -> C), (C - D)) 그리고 모든 이웃 Vertex A의 B와 C를 얻는 대신에 D가 A에 인접하지 않더라도 D를 포함합니까?

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

나는 그것을 만들 때 난 그냥 정점의 이웃을 저장할 수 이해하지만 그게 내가 미래에 변경을해야한다면 다른 사람이 어떤 아이디어가 있으면 내가 많은 변화를해야 할 것이다 의미 나는 올바른 방향으로 인도하는 법을 매우 감사하게 생각합니다 !! 당신이 adjecency 행렬로 그래프를 나타낼 경우

Answer 1

당신은 너무 당신이 그것에 대해 DFS가 필요하지 않습니다 버텍스 A.

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

에 해당하는 행에서 비 제로 모든 항목을 취할 수 있습니다.