※ 순회 종류
- 깊이 우선 탐색
- 너비 우선 탐색
※ 깊이 우선 탐색(DFS, Depth Frist Search)
- 한 방향으로 갈 수 있을 가장 먼 경로까지 깊이 탐색해가다가 더 이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길
간선이 있는 정점으로 되돌아와 다른 방향의 간선을 탐색을 계속 하므로써 모든 정점을 방문 순회하는 법.
- 가장 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가 다시 깊이 우선 탐색을 반복해야 하므로 후입 선출 구조의 스택을 사용한다.
※ 너비 우선 탐색(BFS, Breadth First Search)
- 시작 정점으로 부터 인접한 정점을 모두 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례대로 방문하는 방법
- 인접한 정점들에 대해 차례로 다시 너비를 우선 탐색을 반복해야 하므로 선입 선출의 구조를 갖는 큐를 사용한다.
※ 탐색 구현
Main
public class Main {
public static void main(String[] args) {
AdjList g = new AdjList();
for(int i=0; i<7; i++){
g.insertVertex(i);
}
g.insertEdge(0, 2);
g.insertEdge(0, 1);
g.insertEdge(1, 4);
g.insertEdge(1, 3);
g.insertEdge(1, 0);
g.insertEdge(2, 4);
g.insertEdge(2, 0);
g.insertEdge(3, 6);
g.insertEdge(3, 1);
g.insertEdge(4, 6);
g.insertEdge(4, 2);
g.insertEdge(4, 1);
g.insertEdge(5, 6);
g.insertEdge(6, 5);
g.insertEdge(6, 4);
g.insertEdge(6, 3);
System.out.println("\n 그래프 G의 인접리스트 : ");
g.printAdjList();
System.out.println("\n\n 깊이우선탐색 >>");
g.DES(0);
System.out.println("\n\n 너비우선탐색 >>");
g.BES(0);
}
}
AdjList
import Queue.LinkedQueue;
import stack.LinkedStack;
public class AdjList {
private GraphNode[] headList;
private int headListSize;
public AdjList() {
// TODO Auto-generated constructor stub
headList = new GraphNode[10];
headListSize = 0;
}
public void insertVertex(int i){
headListSize++;
}
public void insertEdge(int v1, int v2){
if(v1 >=headListSize || v2 >= headListSize){
System.out.println("vertex 값이 올바르지 않습니다.");
}else{
GraphNode gn = new GraphNode(v2);
gn.link=headList[v1];
headList[v1]= gn;
GraphNode temp = headList[v1];
int tempValue;
while(temp.link != null){
if(temp.getVertex() > temp.link.getVertex()){
tempValue = temp.link.getVertex();
temp.link.setVertex(temp.getVertex());
temp.setVertex(tempValue);
}
temp = temp.link;
}
}
}
public void printAdjList(){
for(int i =0; i <headListSize; i++){
GraphNode temp = headList[i];
System.out.printf("정점 %c 의 인접리스트 -> ",(i+65));
while(temp.link != null){
System.out.printf("%c -> ", temp.getVertex()+65);
temp = temp.link;
}
System.out.printf("%c\n",(temp.getVertex()+65));
}
}
public void DES(int v){
if(headListSize ==0){
System.out.println("graph is empty");
}else{
GraphNode visitedNode = new GraphNode();
LinkedStack st = new LinkedStack();
boolean visited[] = new boolean[10];
visited[v] = true;
st.push(v);
System.out.printf(" %c ", v+65);
while(!st.isEmpty()){
visitedNode = headList[st.pop()];
while(visitedNode != null){
if(visited[visitedNode.getVertex()]==false){
visited[visitedNode.getVertex()] = true;
st.push(visitedNode.getVertex());
System.out.printf(" %c ", visitedNode.getVertex()+65);
visitedNode = headList[visitedNode.getVertex()];
}else{
visitedNode = visitedNode.link;
}
}
}
}
}
public void BES(int v){
if(headListSize ==0){
System.out.println("graph is empty");
}else{
GraphNode visitedNode = new GraphNode();
LinkedQueue lq = new LinkedQueue();
boolean visited[] = new boolean[10];
visited[v] = true;
lq.enQueue(v);
System.out.printf(" %c " , v+65 );
for(int i =0; i<headListSize ; i++){
visitedNode = headList[lq.deQueue()];
while(visitedNode != null){
if(visited[visitedNode.getVertex()]==false){
lq.enQueue(visitedNode.getVertex());
visited[visitedNode.getVertex()] = true;
System.out.printf(" %c " , visitedNode.getVertex()+65 );
visitedNode = visitedNode.link;
}else{
visitedNode = visitedNode.link;
}
}
}
}
}
}
GraphNode
public class GraphNode {
GraphNode link;
private int vertex;
public GraphNode(int v) {
// TODO Auto-generated constructor stub
this.link = null;
vertex = v;
}
public GraphNode() {
// TODO Auto-generated constructor stub
this.link = null;
}
public int getVertex(){
return vertex;
}
public void setVertex(int v){
vertex = v;
}
}
StackNode
public class StackNode {
StackNode link;
int data;
public StackNode() {
// TODO Auto-generated constructor stub
this.link = null;
}
}
LinkedStack
public class LinkedStack {
StackNode top;
public LinkedStack(){
this.top = null;
}
public boolean isEmpty(){
return (top==null);
}
public void push(int item){
StackNode sn = new StackNode();
sn.data = item;
sn.link = top;
top = sn;
}
public int pop(){
if(isEmpty()){
System.out.println("stack is empty");
return 0;
}else{
int data = top.data;
top = top.link;
return data;
}
}
}
QueueNode
public class QueueNode {
QueueNode link;
int data;
public QueueNode() {
// TODO Auto-generated constructor stub
this.link = null;
}
}
LinkedQueue
public class LinkedQueue {
QueueNode front;
QueueNode rear;
public LinkedQueue() {
// TODO Auto-generated constructor stub
this.front = null;
this.rear = null;
}
public boolean isEmpty(){
return (front == null);
}
public void enQueue(int item){
QueueNode qn = new QueueNode();
qn.data = item;
if(isEmpty()){
front= qn;
rear = qn;
}else{
rear.link = qn;
rear = qn;
}
}
public int deQueue(){
int item = front.data;
front = front.link;
if(front == null){
rear =null;
}
return item;
}
}
'플밍 is 뭔들 > 자료구조' 카테고리의 다른 글
| 07-1 선택 정렬 (0) | 2016.11.30 |
|---|---|
| 06-4 신장 트리와 최소 비용 신장 트리 (0) | 2016.11.26 |
| 06-2 그래프의 구현 (0) | 2016.11.26 |
| 06-1 그래프의 구조 (0) | 2016.11.25 |
| 05-7 힙의 구현 (0) | 2016.11.25 |
