1) 무방향 그래프
노드의 개수가 적고 간선의 수가 많을 때 유리하다
노드의 개수가 많고 간선의 수가 적을 때 유리하다
// 인접 행렬을 이용한 그래프 구현
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
class MyGraphMatrix {
char[] vertices; //정점(노드)
int[][] adjMat; //간선
int elemCnt; //현재 정점의 개수
public MyGraphMatrix(){}
public MyGraphMatrix(int size){
this.vertices = new char[size];
this.adjMat = new int[size][size];
this.elemCnt = 0;
}
//그래프가 꽉 찼는지 확인해주는 메소드
public boolean isFull(){
return this.elemCnt == this.vertices.length;
}
//정점을 추가해주는 메소드
public void addVertex(char data){
if(isFull()){ //배열이 다 차있으면 추가 못하고 메소드 종료
System.out.println("Graph is full!");
return;
}
//현재 elemCnt에 data를 넣고 elemCnt의 값을 +1
this.vertices[this.elemCnt++] = data;
}
//x와 y사이에 간선을 추가해주는 메소드
public void addEdge(int x, int y){
//무방향 그래프일때는 이렇게 (x,y) (y,x) 2가지의 간선을 추가해주어야 한다
this.adjMat[x][y] = 1;
this.adjMat[y][x] = 1;
}
public void addDirectedEdge(int x, int y){
//방향 그래프일때는 입력받은 방향대로 1가지의 간선만 추가해주면 된다
this.adjMat[x][y] = 1;
}
//x와 y 사이의 간선을 삭제해주는 메소드
public void deleteEdge(int x, int y){
//무방향 그래프일때는 2가지를 삭제
this.adjMat[x][y] = 0;
this.adjMat[y][x] = 0;
}
public void deleteDirectedEdge(int x, int y){
//방향 그래프일때는 1가지 삭제
this.adjMat[x][y] = 0;
}
//인접 행렬을 출력하는 메소드
public void printAdjacentMatrix(){
System.out.print(" ");
for(char item : this.vertices){
System.out.print(item + " ");
}
System.out.println();
for (int i = 0; i < this.elemCnt; i++) {
System.out.print(this.vertices[i] + " ");
for (int j = 0; j < this.elemCnt; j++) {
System.out.print(this.adjMat[i][j] + " ");
}
System.out.println();
}
}
//DFS 깊이우선탐색
//id부터 탐색시작
public void dfs(int id){
boolean[] visited = new boolean[this.elemCnt];
Stack<Integer> stack = new Stack<>();
//스택에 탐색을 시작할 값 넣고 시작
stack.push(id);
visited[id] = true;
while(!stack.isEmpty()){ //스택이 빌떄까지
int curId = stack.pop(); //값을 뽑고
System.out.print(this.vertices[curId] + " ");
for (int i = this.elemCnt - 1; i >= 0; i--) { //방문을 어디서부터 할지 기준에 따라 초기값 설정
if(this.adjMat[curId][i] == 1 && visited[i] == false){ //인접행렬이고 아직 방문을 안했으면
stack.push(i); //스택에 집어넣음
visited[i] = true; //스택에 넣으면서 방문 체크
}
}
}
System.out.println();
}
//BFS 넓이우선탐색
//id부터 탐색시작
public void bfs(int id){
boolean[] visited = new boolean[this.elemCnt];
Queue<Integer> queue = new LinkedList<>();
//큐에 탐색을 시작할 값 넣고 시작
queue.offer(id);
visited[id] = true;
while(!queue.isEmpty()){ //큐가 빌때까지
int curId = queue.poll(); //값을 뽑고
System.out.print(this.vertices[curId] + " ");
for (int i = this.elemCnt - 1; i >= 0; i--) { //방문을 어디서부터 할지 기준에 따라 초기값 설정
if(this.adjMat[curId][i] == 1 && visited[i] == false){ //인접행렬이고 아직 방문을 안했으면
queue.offer(i); //큐에 집어넣음
visited[i] = true; //큐에 넣으면서 방문 체크
}
}
}
System.out.println();
}
}
public class Main {
public static void main(String[] args) {
// Test code
MyGraphMatrix graph = new MyGraphMatrix(7);
graph.addVertex('A'); // 0
graph.addVertex('B'); // 1
graph.addVertex('C'); // 2
graph.addVertex('D'); // 3
graph.addVertex('E'); // 4
graph.addVertex('F'); // 5
graph.addVertex('G'); // 6
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
graph.addEdge(4, 6);
graph.addEdge(5, 6);
graph.printAdjacentMatrix();
graph.dfs(0);
graph.bfs(0);
}
}