도전 프로그래밍(알고리즘 및 데이터 구조) - DFS 및 BFS 및 일부 어플리케이션

기사 목록

DFS

BFS

어플리케이션

DFS의 어플리케이션

구도의 관절점

BFS의 어플리케이션

나무의 지름

DFS

제목 12.3 링크 Depth First Search DFS는 귀속과 창고를 사용하여 풀 수 있습니다.
다음 두 가지 방법은 모두 인접표를 인접 행렬로 바꾸어 그림의 인접 행렬에서 조작하는 것이다.반복 사용:

#include 
#include 
using namespace std;

const int Max = 105;
int G[Max][Max], color[Max], d[Max], f[Max];
int t, n;
//color -1   0 ，   1 ， 
void dfs_visit(int u)
{
    color[u] = 0;// 
    d[u] = ++t;// 
    for(int j=0; j> n;
    for(int i=0; i> u >> k;
        for(int j=0; j> v;
            G[u-1][v-1] = 1;
        }
    }
    dfs();
    return 0;
}

창고 사용:

#include 
#include 
#include 
using namespace std;

const int Max = 105;
int G[Max][Max], color[Max], d[Max], f[Max], nt[Max];//nt[i] i 
int t, n;

int next(int u)// u 
{
    for(int v=nt[u]; v S;
     S.push(r);
     color[r] = 0;
     d[r] = ++t;

     while(!S.empty())
     {
         int u = S.top();
         int v = next(u);// u 
         if(v!=-1)//u 
         {
             if(color[v]==-1)// 
             {
                 color[v] = 0;
                 d[v] = ++t;
                 S.push(v);
             }
         }
         else
         {
             S.pop();
             color[u] = 1;
             f[u] = ++t;
         }
     }
}

void dfs()
{
    memset(color, -1, sizeof(color));
    memset(nt, 0, sizeof(nt));
    t = 0;
    for(int i=0; i> n;
    for(int i=0; i> u >> k;
        for(int j=0; j> v;
            G[u-1][v-1] = 1;
        }
    }
    dfs();
    return 0;
}

BFS

제목 12.4 링크 Breadth First Search
BFS는 주로 대기열을 사용하여 풀며, 매번 모든 인접점을 대기열에 포함합니다.이 방법은 역시 인접 행렬, 복잡도 O(N^2) 를 채택했다

#include 
#include 
#include 
using namespace std;

const int Max = 105;
int G[Max][Max], color[Max], d[Max];//d 
int n;
//color -1   0 
void bfs(int u)
{
    memset(color, -1, sizeof(color));
    memset(d, -1, sizeof(d));
    queue Q;
    int v;
    Q.push(u);// 
    d[u] = 0;
    color[u] = 0;
    while(!Q.empty())
    {
        u = Q.front(); Q.pop();
        for(int i=0; i> n;
    for(int i=0; i> u >> k;
        for(int j=0; j> v;
            G[u-1][v-1] = 1;
        }
    }
    bfs(0);
    return 0;
}

활용단어참조

DFS 적용
구도의 관절점
제목 15.3 링크 Articulation Points 구관절점은 tarjan 알고리즘을 사용했습니다. 관련 설명은 tarjan 알고리즘 구관절점과 p291을 보십시오.변수 설정은 다음과 같습니다.
변수
함의
prenum[u]
그림의 임의의 점을 기점으로 DFS를 진행하여 각 정점 u의 접근(발견) 순서를 prenum[u], 즉 u가 DFS 과정 중의 깊이에 기록한다
parent[u]
DFS를 통해 트리를 생성하여 결점 u의 부모 노드를 parent[u]에 기록합니다.
lowest[u]
각 정점 u에 대해 u를 통해 도달할 수 있는 최저 깊이를 계산하고lowest[u]
(1) 점 u가 dfs 생성 나무의 뿌리라면 u는 적어도 두 명의 자녀가 있다.이유: u를 삭제하자마자 자녀가 있는 나무가 끊어졌기 때문이다.즉, 루트 u가 두 개 이상의 하위 노드가 있다면 루트 u는 관절점이다.
(2) 만약에 u가 dfs가 나무를 생성하는 뿌리가 아니라면 u의 한 자녀 w는 w나 w의 자손에서 출발하거나 돌아가서 u의 조상에 도착한다.만약 도착할 수 있다면 점 u는 관절점이 아니다.즉prenum[u]<=lowest[w], u는 관절점이다.
prenum과parent는 모두 DFS 프로세스에서 직접 구할 수 있기 때문에 lowest의 구해만 고려하면 된다

lowest[u]=min{

　　prenum[u] 

　　min（low[w]|w u ）  

　　min（prenum[x]|x u )

};

: 원래 그림에서 dfs 나무의 가장자리를 제외하고 다시 가장자리라고 부른다.예: 1->2,1->3,2->3 중, dfs시 1->2->3, 여기 dfs나무의 가장자리가 1->2,2->3이면 1->3이 리턴)
코드는 다음과 같습니다.

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int MAX = 100005;
int V, E, s, t, color[MAX], timer;
int prenum[MAX], parent[MAX], lowest[MAX];
vector G[MAX];

//color  0 ， 1 
void dfs(int current, int prev)
{
    prenum[current] = lowest[current] = timer;// prenum[current] = lowest[current]
    timer++;
    color[current] = 1;
    int next;

    for(int i=0; i S;// ， set 
    for(int i=1; i1) S.insert(0);
    set::iterator it;
    for(it=S.begin(); it!=S.end(); it++)
    {
        printf("%d
", *it);
    }
}
int main()
{
    scanf("%d %d", &V, &E);
    for(int i=0; i

BFS 적용
나무의 지름
제목 15.4 링크 Diameter of a Tree 이 문제는 BFS의 인접표 실현법을 사용하고 권무방향도를 가진 구조체를 정의했다.주요 사고방식은 1 - 한 노드 s를 선택하여 s의 가장 먼 결점 x를 구한다.2 - x에서 가장 먼 결점 y를 구한다.3 - 결점 x와 결점 y의 거리, 즉 나무의 지름을 보고합니다.트리이기 때문에 임의의 두 점 사이에는 하나의 경로만 있습니다. 즉, 가장 먼 경로입니다. BFS를 사용하여 모든 점에서 점 s까지의 경로 길이를 기록할 수 있습니다.

#include 
#include 
#include 
#include 
using namespace std;

struct Edge
{
    int t, w;
    //Edge(){}
    Edge(int t=-1, int w=-1): t(t), w(w){}
};
const int MAX = 100005;
const int INF = (1<<29);
int color[MAX], d[MAX];//d 
vector G[MAX];
int n;
//color -1   0 
void bfs(int u)
{
    memset(color, -1, sizeof(color));
    memset(d, -1, sizeof(d));
    queue Q;
    int v;
    Q.push(u);// 
    d[u] = 0;
    color[u] = 0;
    while(!Q.empty())
    {
        u = Q.front(); Q.pop();
        for(int i=0; i=0 && Max=0 && Max> n;
    if(n==1)
    {
        cout << 0 << endl;
        return 0;
    }
    for(int i=0; i> u >> k >> v;
        G[u].push_back(Edge(k, v));
        G[k].push_back(Edge(u, v));
    }
    solve();

    return 0;
}