인접 행렬 형태로 구현한 그래프.
class GraphMatrix{
//######################################################//
//인접행렬로 표현한 그래프 row & col 크기가 같아야 한다.#########//
//#####################################################//
int[][] graph={
{0, 1, 1, 1, 0, 0, 0},
{1, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 0, 1, 1, 0},
{1, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 0, 0, 0, 1},
{0, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 0, 1, 1, 0}
};
int nodeNum= graph.length; //노드의 갯수. 인접행렬(변수명:graph)의 사이즈에 의존한다.
boolean[] visited= new boolean[nodeNum]; //방문했는지 아직 방문하지 않았는지 체크한다.
//###############################################################//
//그닥 필요는 없으나 일관성을 위해 적어 둠. 본 클래스 내의 함수 호출시 매개변수로 사용.
//###############################################################//
public final int BFS= 11; //너비 우선 탐색
public final int DFS= 12; //깊이 우선 탐색
public final int MATRIX= 21; //인접행렬 형태로 그래프 출력
public final int EDGE= 22; //연결된 간선 형태로 그래프 출력
//###############################################################//
//그래프를 탐색한다. 매개변수 : sWay-탐색 방법(BFS, DFS), firstNode-처음 방문할 노드 번호
//###############################################################//
public void search(int sWay, int firstNode){
for(int i=0;i<nodeNum;i++){
visited[i]=false;
}
switch(sWay){
case BFS:
BFS(firstNode);
break;
case DFS:
DFS(firstNode);
break;
default:
System.out.println("정의 되지 않은 매개 변수입니다.");
}
}
//#######################################################//
//그래프를 출력한다. 그래픽 형태로 출력하면 아주 멋지겠으나, 능력 부족.
//매개변수 : sWay-출력 방법(Matrix, Edge)
//######################################################//
public void print(int sWay){
switch(sWay){
case MATRIX:
printMatrix();
break;
case EDGE:
printEdge();
break;
default:
System.out.println("정의 되지 않은 매개 변수입니다.");
}
}
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//
//--------------------------< 탐색 부분 >-------------------------//
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//
//######################################################//
//너비 우선 탐색##########################################//
//#####################################################//
private void BFS(int sNode){
if(visited[sNode]==false){
System.out.print("\n//------ Breadth Fitst Search -----//\n");
visited[sNode]=true;
System.out.print(sNode+", ");
}
for(int i=0;i<nodeNum;i++){
for(int j=0;j<nodeNum;j++){
if(graph[i][j]==1 && visited[j]==false){ //현재 방문한 노드의 인접 노드 중 방문하지 않은 노드
System.out.print(j+", ");
visited[j]=true;
}
}
}
}
//###############################################################//
//깊이 우선 탐색#################################################//
//###############################################################//
private void DFS(int sNode){
if(visited[sNode]==false){ //첫 노드 방문시 한번만 실행된다.
System.out.print("\n//------ Depth Fitst Search -----//\n");
System.out.print(sNode+", ");
visited[sNode]=true;
}
for(int i=0;i<nodeNum;i++){
if(graph[sNode][i]==1 && visited[i]==false){ //현재 방문한 노드의 인접 노드 중 방문하지 않은 노드
visited[i]=true;
System.out.print(i+", ");
DFS(i); //recurrence
}
}
}
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//
//---------------------< 그래프 출력 부분 >----------------------//
//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@//
//######################################################//
//인접 행렬 형태로 출력. 즉, graph[][]를 그대로 출력.############//
//#####################################################//
private void printMatrix(){
System.out.println("//------ Matrix 형태로 출력 -----//");
for(int i=0;i<nodeNum;i++){
for(int j=0;j<nodeNum;j++){
System.out.print(graph[i][j]);
}
System.out.println();
}
}
//###############################################################//
//연결된 간선 형태로 출력 ex) (v1, v2)##########################//
//###############################################################//
private void printEdge(){
System.out.println("//----- Edge 형태로 출력 -----//");
for(int i=0;i<nodeNum;i++){
for(int j=i+1;j<nodeNum;j++){ //방향그래프 이므로 (v1, v2), (v2, v1)형태의 중복 회피.
if(graph[i][j]==1){
System.out.println("("+i+", "+j+")");
}
}
}
}
};
public class Test{
public Test(){
GraphMatrix graph= new GraphMatrix();
graph.print(graph.MATRIX);
graph.print(graph.EDGE);
graph.search(graph.BFS, 0);
graph.search(graph.DFS, 0);
}
public static void main(String args[]){
Test t= new Test();
}
};
'Computer > Java' 카테고리의 다른 글
java RMI, Exception:Connection refused to host... (0) | 2012.03.08 |
---|---|
Programming Language.... (0) | 2007.08.17 |
Static on Java- Speed Test (0) | 2006.10.09 |
[Data Structure2] Binary Tree (Linked List) (0) | 2006.10.09 |
[Data Structure2] Max Heap (for int array) (0) | 2006.10.09 |