https://www.youtube.com/watch?v=x8Zwup81DlA(참고 유튜브)

위 그래프에 대한 깊이 우선 탐색(DFS=Stack을 통해 구현)

class UndirectedGraph{
// 필드선언
int count; // 노드(vertex)의 수
int [][]vertexMatrix; //vertexMatrix는 노드와 노드간의 연결을 나타내는 이차원배열이다

//생성자 선언
public UndirectedGraph(int count){
					this.count = count;
					vertexMatrix = new int[count][count]
}

//메서드 선언
public void addEdges(int from, int to, int weight){ // 노드와 노드간의 연결, 간선을 그리는 이차원배열
		vertexMatrix[from][to]=weight;
		vertexMatrix[to][from]=weight;
		}
		
//게터 메서드
public int[][] getVertexMatrix(){
		return vertexMatrix;
		}

--->그래프를 그리는 클래스다.

Class DfsSearch{
  
  int count;// 노드의 개수
  int[][] vertexMatrix;// 노드와 노드간의 연결을 나타내는 이차원 배열
  boolean[] visited; // 방문처리하여 중복탐색을 막는 플래그 변수
  Stack<Integer> stack = new ArrayList<>(); // DFS에서는 주로 스택 자료구조를 사용한다.
  
  -->깊이 우선 탐색을 진행하기 위해 필요한 네 가지다.

public void DfsSearch(int count){
		this.count = count;
		visited = new boolean[count];
		stack = new stack<>();

}

public void dfsTraversal(){
     stack.push(0);
     visited[0] =true;
		 	
			while(stack.size !=0){

		         int node = stack.pop;
        
			         for(int j=0; j<count; j++){
				         if(vertexMatrix[node][j] !=0 && visited[j] =false){
		                      stack.push(j);
			                      visited(j)=true;

									}
							}
						}
			}
		

public static void main(String[] args){
						int count =8;
					UndirectedGrapgh grapg = new UndirectedGraph(count);
					DfsSearch dfsSearch = new DfsSearch(count);
					
			graph.addEdges(0,1,1);
			graph.addEdges(0,2,1);
			graph.addEdges(1,3,1);
			graph.addEdges(1,4,1);
			graph.addEdges(2,5,1);
			graph.addEdges(2,6,1);
			graph.addEdges(4,5,1);
			graph.addEdges(3,7,1);
			
		dfsSearch.matrix = graph.getVertexMatrix();
		dfsSearch.dfsTraveral();
		
	-->	실행하면, 0 2 6 5 4 1 3 7 순으로 깊이우선탐색이 완료된다.
	0 1 3 4 5 2 6 순으로도 DFS될 수 있지만 우리는 j=0부터 반복을 돌면서 스택의 특징인
	후입선출로 인해 나중에 들어온 값이 먼저 스택에 pop되고 pop된 요소와 연결된 node들을 또 스택
	에 넣고 함으로써 오른쪽부터 DFS가 진행되었음. 
			
}

위 그래프에 대한 너비우선탐색 진행(Bfs-Queue를 통해 구현)

class DfsSearch{
int count; //노드의 개수
int[][] vertexMatrix // 노드와 노드간의 연결을 나타내는 2차원 배열
boolean visited[]; // 방문처리를 담당하는 불린타입의 배열
Queue queue; //DFS는 자료구조로 큐를 이용한다.

-->너비 우선탐색에서 필요한 4가지 요소이고, 깊이 우선탐색과는 자료구조에서 차이가 난다.

public void BfsSearch(int count){
   this.count = count;
   vertexMatrix = new int[count][count];
   visited = new boolean[count];
   queue = new LinkedList<>();
   }
   
 
 public void bfsTraversal(){
       
       queue.add(0);
       visited[0]= true;
       
    while(q.size!=0){
			   
			   int node = queue.remove();
			   
			   for(int i =0; i<count; i++){
			     if(vertexMatrix[node][i]!=0 && !visited[i]){
			            queue.add(i);
			            visited[i] = true;}
			            }
			  }          
    
    }
 
 
 public static void main(String[] args){
						int count =8;
					UndirectedGrapgh grapg = new UndirectedGraph(count);
					BfsSearch bfsSearch = new bfsSearch(count);
					
			graph.addEdges(0,1,1);
			graph.addEdges(0,2,1);
			graph.addEdges(1,3,1);
			graph.addEdges(1,4,1);
			graph.addEdges(2,5,1);
			graph.addEdges(2,6,1);
			graph.addEdges(4,5,1);
			graph.addEdges(3,7,1);
			
		bfsSearch.matrix = graph.getVertexMatrix();
		bfsSearch.bfsTraveral();
 

재귀를 통한 DFS구현

참고(https://codingnojam.tistory.com/44)

위의 그래프를 스택 자료구조를 통해 DFS 통해 탐색을 진행한다면

• 1번 부터 시작.스택에 1번 넣고, 1번 방문처리 완. 그런 다음 while반복문 들어가서 출력→1
• 1번과 연결되어있는 2,3,8을 스택에 넣고 방문처리 완. 후입선출로 인해 8번 출력→1, 8
• 8번과 연결되어있는 1,2 모두 방문처리 이미 되어있음. 그러면 스택에 남아있던 2, 3중 3출력 →1, 8 , 3
• 3번과 연결되어있는 5번 스택에 넣고 방문처리완. (스택에 2,5번 있음) 후 5번 출력 →1, 8, 3, 5
• 5번과 연결되어있는 4번,7번 스택에 넣고 방문처리 완.(2,4,7) 후 7번 출력 →1, 8, 3, 5, 7
• 7번과 연결되어있는 것중 4,5는 이미 방문처리 되어서 탐색 불가. 스택에 남아있는 2,4 중 4번 출력 →1, 8, 3, 5, 7, 4
• 4번과 연결되어있는 것중 5,7이미 방문처리 되어서 탐색불가. 스택에 남아있는 2 출력 →1, 8, 3, 5, 7, 4, 2
• 2와 연결되어있는 1,6,8중 1,8은 이미 방문처리 완. 따라서 스택에 6을 넣고 6번 출력 후 스택의 사이즈가 0이 되면서 반복이 멈춘다. 최종적으로, →1, 8, 3, 5 , 7, 4, 2, 6 순으로 탐색이 완료된다.