홈>
그래프를 작성하는 JAVA 프로그램이 있고 너비 우선 검색이 있지만 깊이 우선 검색으로 변경하고 싶습니다. 코드에서 어떤 변경을해야합니까? 미리 도움을 주셔서 감사합니다.
public class ConnectedComponents
{
static final int MAXV = 100;
static boolean processed[] = new boolean[MAXV];
static boolean discovered[] = new boolean[MAXV];
static int parent[] = new int[MAXV];
static void bfs(CCGraph g, int start)
{
Queue<Integer> q = new LinkedList<Integer>();
int i, v;
q.offer(start);
discovered[start] = true;
while (!q.isEmpty())
{
v = q.remove();
process_vertex(v);
processed[v] = true;
for (i = g.degree[v] - 1; i >= 0; i--)
{
if (!discovered[g.edges[v][i]])
{
q.offer(g.edges[v][i]);
discovered[g.edges[v][i]] = true;
parent[g.edges[v][i]] = v;
}
}
}
}
- 답변 # 1
- 답변 # 2
기본 차이점은 꼭지점을 테스트하는 순서입니다. BFS는 대기열 (FIFO : First In First Out)을 사용하지만 DFS는 스택 (LIFO : Last In First Out)을 사용합니다.
LinkedList
를 사용하여 스택을 구현할 수 있습니다 :LinkedList<Integer> stack = new LinkedList<Integer>(); stack.pop(); //returns the top of the stack
자세한 내용은 테스트 데이터를 포함한 mcve를 게시하십시오.
- 답변 # 3
프로그램의 전체 코드. 목표는 bfs를 dfs로 변경하는 것입니다.
import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class CCGraph { static final int MAXV = 100; static final int MAXDEGREE = 50; public int edges[][] = new int[MAXV + 1][MAXDEGREE]; public int degree[] = new int[MAXV + 1]; public int nvertices; public int nedges; CCGraph() { nvertices = nedges = 0; for (int i = 1; i <= MAXV; i++) degree[i] = 0; } void read_CCGraph(boolean directed) { int x, y; Scanner sc = new Scanner(System.in); System.out.println("Enter the number of vertices: "); nvertices = sc.nextInt(); System.out.println("Enter the number of edges: "); int m = sc.nextInt(); System.out.println("Enter the edges: <from> <to>"); for (int i = 1; i <= m; i++) { x = sc.nextInt(); y = sc.nextInt(); insert_edge(x, y, directed); } sc.close(); } void insert_edge(int x, int y, boolean directed) { if (degree[x] > MAXDEGREE) System.out.printf( "Warning: insertion (%d, %d) exceeds max degree\n", x, y); edges[x][degree[x]] = y; degree[x]++; if (!directed) insert_edge(y, x, true); else nedges++; } void print_CCGraph() { for (int i = 1; i <= nvertices; i++) { System.out.printf("%d: ", i); for (int j = degree[i] - 1; j >= 0; j--) System.out.printf(" %d", edges[i][j]); System.out.printf("\n"); } } } public class ConnectedComponents { static final int MAXV = 100; static boolean processed[] = new boolean[MAXV]; static boolean discovered[] = new boolean[MAXV]; static int parent[] = new int[MAXV]; static void bfs(CCGraph g, int start) { LinkedList<Integer> q = new LinkedList<Integer>(); int i, v; q.offer(start); discovered[start] = true; while (!q.isEmpty()) { v = q.remove(); process_vertex(v); processed[v] = true; for (i = g.degree[v] - 1; i >= 0; i--) { if (!discovered[g.edges[v][i]]) { q.offer(g.edges[v][i]); discovered[g.edges[v][i]] = true; parent[g.edges[v][i]] = v; } } } } static void initialize_search(CCGraph g) { for (int i = 1; i <= g.nvertices; i++) { processed[i] = discovered[i] = false; parent[i] = -1; } } static void process_vertex(int v) { System.out.printf(" %d", v); } static void connected_components(CCGraph g) { int c; initialize_search(g); c = 0; for (int i = 1; i <= g.nvertices; i++) { if (!discovered[i]) { c++; System.out.printf("Component %d:", c); bfs(g, i); System.out.printf("\n"); } } } static public void main(String[] args) { CCGraph g = new CCGraph(); g.read_CCGraph(false); g.print_CCGraph(); connected_components(g); } }
관련 자료
- 자바 스크립트를 사용하여 앵커 제목 속성 검색
- python - 와일드 카드를 사용하여 특정 문자열에 대한 DataFrame을 검색하는 방법
- sql - MSSQL에서 여러 검색 문자열을 사용하여 여러 필드 필터링
- python - (AoC Day 5) 이진 검색을 사용하여 문자열을 디코딩하는 것이 이진 변환만큼 빠릅니까?
- Python을 사용하여 Python을 사용하여 CLI 프로그램을 실행하는 방법
- Installing program - 프로그램 설치 - vuze 토렌트 클라이언트 :tarbz2 사용 :vol 2
- tkinter에서 버튼을 사용하여 별도의 파이썬 프로그램을 어떻게 호출합니까?
- networking - 라우터 대신 레이어 3 스위치 사용
- Julia에서`/`대신`\`사용
- python - while 루프를 사용하여 프로그램 반복 실패
- c# - 왜 내 작은 프로그램이 점점 더 많은 RAM과 CPU의 많은 부분을 계속 사용합니까?
- GCC에서 limitsh 헤더 파일을 사용하지 않고 C 프로그램을 컴파일하는 방법은 무엇입니까?
- function - 괄호 대신 $를 사용하는 Haskell은 유효하지 않습니다
- javascript - 객체 생성을 위해 forEach 대신 map () 사용
- elasticsearch - JsonNetSerializer를 사용할 때 선택한 필드 대신 모든 필드를 매핑합니다
- php, sql을 이용한 검색 조건
- linux 유틸리티 (예 - grep)를 사용하여 파일 0x1f (단위 구분 기호)에서 검색
트렌드
- OpenCv의 폴더에서 여러 이미지 읽기 (python)
- 파이썬 셀레늄 모든 "href"속성 가져 오기
- html - 자바 스크립트 - 클릭 후 변경 버튼 텍스트 변경
- javascript - 현재 URL에서 특정 div 만 새로 고침/새로 고침
- JSP에 대한 클래스를 컴파일 할 수 없습니다
- JavaScript 변수를 HTML div에 '출력'하는 방법
- git commit - 자식 - 로컬 커밋 된 파일에 대한 변경을 취소하는 방법
- jquery - JavaScript로 현재 세션 값을 얻으시겠습니까?
- javascript - swiperjs에서 정지, 재생 버튼 추가
- python - 화면에서 찾은 요소를 찾을 수없는 경우 셀레늄
깊이 우선 검색과 너비 우선 검색의 차이점을 이해해야한다고 생각합니다. 심도 우선 검색 코드는 다음과 같습니다.