깊이 인접 매트릭스에서 깊이 우선 검색

Question

이 프로그램의 경우, 인접 매트릭스에 저장해야하는 입력 세트가 제공됩니다. 나는 이것을 했으므로 인접 행렬 행렬 [11] [11]을가집니다. 이제이 행렬을 사용하여 깊이 우선 검색을 수행하고 pi 값을 반환해야합니다.

나는이 의사 코드를 가지고 있으므로 DFS (그래프)와 DFS-VISIT (노드)의 두 가지 방법이 필요하다고 생각합니다. 그러나 실제로 이것을 구현하는 데 문제가 있습니다. 인접 행렬을 직접 사용하여이 작업을 수행 할 수 있습니까? 아니면 어떻게 행렬을 사용하여 그래프를 만들어야합니까? 실제로 이것을 코딩하는 데 도움이 될 것입니다.

는

DFS(G) 
    for each u ∈ V[G] do 
     color[u] = WHITE 
     ∏[u] = NIL 
    time = 0 
    for each u ∈ V[G] do 
     if color[u] = WHITE then 
     DFS-VISIT(u) 

DFS-VISIT(u) 
    color[u] = GRAY 
    time++ 
    d[u] = time 
    for each v ∈ Adj[u] do 
     if color[v] = WHITE then 
     ∏[v] = u 
     DFS-VISIT(v) 
    color[u] = BLACK 
    time++ 
    f[u] = time 

Answer 1

당신이 의사 코드는 인접리스트를 가정하는 것 같다.

구체적 코드 :

for each v ∈ Adj[u] do 
    if color[v] = white then 
    ∏[v] = u 
    DFS-VISIT(v) 

차이는 (압입 상정 코드 블록에 대응하는) 인접성 매트릭스와 함께, 모든 정점이 있으며, 하나는 일반적으로있다 여부를 나타내는 0/1 플래그를 사용 현재 꼭지점과 대상 꼭지점 사이의 가장자리.

그래서, 당신은 인접 행렬의 해당 행에 대한 모든 정점을 통해 루프해야하고, 플래그가 1

에 같은 모양 의사 코드의 일부 설정 한 경우에만 뭔가를 할 :

를

for v = 1 to n do // assuming 1-indexed 
    if color[v] = white && AdjMatrix[u][v] == 1 then 
    ∏[v] = u 
    DFS-VISIT(v) 

내가 알 수있는 한, 나머지 psuedo-code는 똑같아 야합니다.

Answer 2

결과적으로 시간 복잡도가 O(|V| + |E|)이기 때문에 그래프가 인접성 목록으로 표시된다고 가정 할 때 DFS를 코딩하는 것이 일반적으로 바람직합니다. 그러나 인접 행렬을 사용하면 시간 복잡도는 O(|V|*|V|)이됩니다.

#define WHITE 0 
#define GRAY 1 
#define BLACK 2 
int time_; 
vector<int> color(n, WHITE), par(n, 0), strt(n, 0), fin(n, 0); 
vector<vector<int> > G(n, vector<int>(n, 0)); 
void dfs_visit(int); 
void DFS(){ 
    for(int i = 0; i < n; i++) 
     color[i] = 0, par[i] = -1; 
    time = 0; 
    for(int j = 0; j < n; i++) 
     if(color[j] == WHITE) 
      dfs_visit(j); 
    } 
} 
void dfs_visit(int u){ 
    time_++; 
    strt[u] = time_; 
    color[u] = GRAY; 
    for(int v = 0; v < n && v++) 
     if(G[u][v] && color[v] == WHITE){ 
      par[v] = u; 
      dfs_visit(v); 
     } 
    color[u] = BLACK; 
    time_++; 
    fin[u] = time_; 
} 

파 []를 행렬은 각 정점과 STRT []의 상위를 계산하고, [] 행렬 타임 스탬프 정점 지느러미 아래 인접 행렬 표현을 가정 DFS의 구현이다. 정점은 0부터 번호가 매겨집니다.