그림 없 이 두 점 사이 의 가장 짧 은 경 로 를 찾 습 니 다.
5205 단어 데이터 구조
무방 향 도 는 도 구조의 일종 이다.이번 프로그램 은 인접 표를 이용 하여 무방 향 도 를 실현 하고 광 도 를 통 해 두 점 사이 의 가장 짧 은 경 로 를 우선적으로 찾 습 니 다.
2. 넓이 우선 옮 겨 다 니 기
폭 우선 스 트 리밍 (BFS) 과 깊이 우선 스 트 리밍 (DFS) 은 그림 구조 에서 가장 많이 사용 되 는 스 트 리밍 방식 이다.그 중에서 넓 은 범위 가 우선 대열 에 맞 춰 두 점 사이 의 가장 짧 은 경 로 를 찾 을 수 있 고 다른 문제 도 해결 할 수 있다 (예 를 들 어 미로 의 가장 짧 은 탈출 로 를 찾 는 것).두 점 사이 의 가장 짧 은 경 로 를 찾 는 작업 은 다음 과 같은 몇 단계 로 나 뉜 다.
1. 먼저 시작 점 과 종점 src 와 dst 를 정의 합 니 다.이 어 하나의 배열 distance [] 를 정의 하여 각 점 에서 src 까지 의 거 리 를 저장 합 니 다.초기 화 할 때 각 점 에서 src 까지 의 거 리 는 INF (무한 함 을 표시 합 니 다. 여기 서 스스로 정의 할 수 있 습 니 다. 이 점 에서 src 까지 의 거 리 를 얻 지 못 했다 는 것 을 의미 합 니 다). distance [src] = 0.그리고 src 를 대기 열 에 넣 습 니 다.
2. 추출 대기 열의 첫 번 째 결점 (처음에 대기 열 은 src 만 있 었 고 여 기 는 src 를 추출 하 는 것) 을 변수 top 에 두 었 습 니 다.
3. 이 노드 의 모든 인접 점 을 획득 하고 distance [] 배열 의 각 인접 점 이 INF 인지 판단 합 니 다.이 노드 에 아직 접근 하지 않 았 다 는 설명 이 라면 distance [] 의 해당 위 치 를 distance [top] + 1 로 설정 합 니 다.INF 가 아니라면 이미 방문 했다 는 의미 로 건 너 뛰 었 다.
4. top 변수 가 dst 와 같 을 때 까지 2 - 3 단 계 를 반복 합 니 다.대기 열 이 비어 있 을 때 까지 두 점 사이 에 경로 가 존재 하지 않 는 다 는 것 을 설명 합 니 다.
요약 하면 노드 를 src 부터 순서대로 대기 열 에 넣 는 것 이 고 이미 대기 열 에 넣 은 노드 는 표 시 될 수 있 기 때문에 dst 를 찾 을 때 까지 반복 적 으로 대기 열 에 넣 지 않 습 니 다.이런 방법 으로 얻 은 경 로 는 반드시 가장 짧 은 길이 다.
3. 출력 최 단 경로
위 에서 광 도 를 우선 사용 하여 두 점 사이 의 가장 짧 은 경로 의 길 이 를 찾 았 고 distance [dst] 에 저장 되 었 으 며 이 가장 짧 은 경 로 를 출력 하려 면 다른 방법 이 있 습 니 다.본인 이 여기 서 사용 하 는 방법 은 먼저 dst 를 창고 에 넣 은 다음 에 dst 의 인접 결점 중 어느 결점 이 distance 수조 에 있 는 값 이 distance [dst] - 1 인지 찾 아서 창고 에 넣 는 것 입 니 다.이 어 앞의 결산 점 을 계속 찾 아 창고 에 넣 었 다.이 동작 을 반복 해서 마지막 으로 src 를 찾 은 다음 스 택 에 있 는 요 소 를 순서대로 pop 합 니 다.창고 가 먼저 들 어간 후에 나 오 는 성질 때문에 이 경 로 를 얻 을 수 있다.
4. 코드 구현
구체 적 인 코드 는 다음 과 같다.
#ifndef _GRAPH_H
#define _GRAPH_H
#include
#include
#include
#define ERROR -1
#define V_E_INFO 1
#define FIND 1
#define PATH 2
#define MAX 100
using namespace std;
class ArcNode
{
private:
int value;
ArcNode *next;
public:
ArcNode(int , ArcNode * = nullptr);
void set_next(ArcNode *);
ArcNode *get_next() const;
int get_value() const;
void set_value(int);
};
class List
{
private:
int value;
ArcNode *firstnode;
public:
List(int = 0,ArcNode * = nullptr);
~List();
ArcNode *Pop();
void Push(int);
int get_value() const;
int is_exist(int) const;
ArcNode *get_firstnode() const;
void set_value(int);
void dfs_find_path() const;
void set_firstnode(ArcNode *);
void print() const;
};
class Graph
{
private:
List list[MAX];
int vertices_num;
int edge_num;
public:
Graph(int,int,int []);
~Graph();
int get_vertices_num() const;
int get_edge_num() const;
List *get_list(int);
void print() const;
void dfs_print_path(int,int) const;
void dfs_find_path(int,int,int [],stack & ,int &) const;
void dfs(int src,int visited[],int &count) const;
void dfs_print(int) const;
void dfs_non_recursive() const;
int find_shortest_path(int,int) const;
void dfs(int,int []) const;
};
#endif
BFS 최 단 경로 코드 찾기:
int Graph::find_shortest_path(int src,int dst) const
{
queue myQ;
int value[vertices_num];/ src
int head = 0;
int output[10];
for(int i = 0;i < vertices_num;i++)
{
value[i] = -1;//-1
}
value[src] = 0;
myQ.push(src);
while(myQ.size())
{
head = myQ.front();
myQ.pop();
if(head == dst)
{
int find = dst;
stack myS;
myS.push(dst);
while(find != src)
{
for(int j = 0; j < vertices_num; j++)
{
if((list[j].is_exist(find) == 1) && (value[find] == value[j] + 1))
{
myS.push(j);
find = j;
break;
}
}
}
int count = myS.size();
for(int j = 0;j < count;j++)
{
if(j == count - 1)
cout << myS.top() << endl;
else
{
cout << myS.top() << "-";
myS.pop();
}
}
return FIND;
}
ArcNode *a = list[head].get_firstnode();
while( a != nullptr)
{
if(value[a -> get_value()] == -1)
{
value[a -> get_value()] = value[head] + 1;
myQ.push(a -> get_value());
}
a = a -> get_next();
}
}
cout << "Error: no path between " << src << " and " << dst << endl;
return ERROR;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.