그래프

[윤은주]

ch09.ppt

//그래프

/////////////////////////
//그래프의 행렬 표현 방식
////////////////////////

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50
typedef struct GraphType {
 int n;
 int adi_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;

void Graph_Init(GraphType *);
void Insert_Vertex(GraphType *);
void Insert_Edge(GraphType *, int , int);
void Graph_Display(GraphType *);
int main(void)
{
 int i; GraphType g;
 Graph_Init(&g); 
 for(i=0;i<4;i++) Insert_Vertex(&g);
 Insert_Edge(&g,0,1);
 Insert_Edge(&g,0,2);
 Insert_Edge(&g,0,3);
 Insert_Edge(&g,1,2);
 Insert_Edge(&g,2,3);
 Graph_Display(&g);
}
void Graph_Display(GraphType *g)
{
 int i,j;
 printf("   ");
 for(i=0;i<g->n;i++) printf("%2d", i);
 printf("\n-----------\n");
 
 for(i=0;i<g->n;i++){
  printf("%2d|", i);
  for(j=0;j<g->n;j++) printf("%2d", g->adi_mat[i][j]);
  printf("\n");
 }
}

void Graph_Init(GraphType *g)
{
 int r,c;
 g->n=0;
 for(r=0;r<MAX_VERTICES;r++)
  for(c=0;c<MAX_VERTICES;c++)
   g->adi_mat[r][c] = 0;
}
void Insert_Vertex(GraphType *g)
{
 if( ((g->n)+1) > MAX_VERTICES ) {
  fprintf(stderr, "그래프:정점의 개수 초과\n");
  return;
 }
 g->n++;
}
void Insert_Edge(GraphType *g, int start, int end)
{
 if(start>=g->n || end>=g->n) {
  fprintf(stderr, "그래프:정점 번호 오류\n");
  return;
 }
 g->adi_mat[start][end] = 1;
 g->adi_mat[end][start] = 1;
}

/////////////////////////////////
// 링크리스트를 이용한 그래프 ADT
/////////////////////////////////
#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 50

typedef struct GraphNode {
 int vertex;
 struct GraphNode *link;
} GraphNode;

typedef struct GraphType {
 int n;
 GraphNode *adj_list[MAX_VERTICES];
} GraphType;

void Graph_Init(GraphType *);
void Insert_Vertex(GraphType *);
void Insert_Edge(GraphType *, int, int);
void Graph_Display(GraphType *);

int main(void)
{
 int i;
 GraphType g;
 Graph_Init(&g);
 for(i=0;i<4;i++) Insert_Vertex(&g);

 Insert_Edge(&g, 0,1);
 Insert_Edge(&g, 0,2);
 Insert_Edge(&g, 0,3);
 //Insert_Edge(&g, 1,0);
 //Insert_Edge(&g, 2,0);
 //Insert_Edge(&g, 3,0);
 Insert_Edge(&g, 1,2);
 //Insert_Edge(&g, 2,1);
 Insert_Edge(&g, 2,3); 
 //Insert_Edge(&g, 3,2);

 Graph_Display(&g);

 return 0;
}

void Graph_Init(GraphType *g)
{
 int v;
 g->n = 0;
 for(v=0;v<MAX_VERTICES;v++)
  g->adj_list[v]=NULL;
}
void Insert_Vertex(GraphType *g)
{
 if( ((g->n)+1) > MAX_VERTICES ) {
  fprintf(stderr, "그래프:정점의 개수 초과\n");
  return;
 }
 g->n++;
}
void Insert_Edge(GraphType *g, int u, int v)
{
 GraphNode *unode, *vnode;
 if(u>=g->n || v>=g->n) {
  fprintf(stderr, "그래프:정점 번호 오류\n");
  return;
 }

 unode = (GraphNode*)malloc(sizeof(GraphNode));
 unode->vertex = v;
 unode->link = g->adj_list[u];
 g->adj_list[u]=unode;

 vnode = (GraphNode*)malloc(sizeof(GraphNode));
 vnode->vertex = u;
 vnode->link = g->adj_list[v];
 g->adj_list[v]=vnode;

}
void Graph_Display(GraphType *g)
{
 int i;
 GraphNode *tmp;
 for(i=0;i<g->n;i++) {
  tmp = g->adj_list[i];
  printf("%d -> ", i);
  while(tmp!=NULL) {
   printf("%2d", tmp->vertex);
   tmp = tmp->link;
  }
  printf("\n"); 
 }
} 

0 ->  3 2 1
1 ->  2 0
2 ->  3 1 0
3 ->  2 0
Press any key to continue
//////////////////////////////////
//
/////////////////////////////////
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#define MAX_VERTEX 10
#define FALSE 0
#define TRUE  1

typedef struct graphNode{
 int vertex;
 struct graphNode* link;
} graphNode;

typedef struct graphType{
 int n;
 graphNode* adjList_H[MAX_VERTEX];
 int visited[MAX_VERTEX];
} graphType;

////////  << 스택 연산
typedef struct stackNode {   
 int data;
 struct stackNode *link;
}stackNode;

stackNode* top;

void push(int item)
{ 
 stackNode* temp=(stackNode *)malloc(sizeof(stackNode));
 temp->data = item;
 temp->link = top; 
 top = temp;
}

int pop()
{
 int item;
 stackNode* temp=top;

 if(top == NULL) {  
  printf("\n\n Stack is empty !\n"); 
  return 0;
 }
 else {
  item = temp->data; 
  top = temp->link; 
  free(temp); 
  return item;
 }
}
////////  스택 연산 >>

void createGraph(graphType* g)
{
 int v;
 g->n = 0;
 for(v=0; v<MAX_VERTEX; v++){
  g->visited[v] = FALSE;
  g->adjList_H[v]=NULL;
 }
}

void insertVertex(graphType* g, int v)
{
 if(((g->n)+1)>MAX_VERTEX){
  printf("\n 그래프 정점의 개수를 초과하였습니다!");
  return;
 }
 g->n++;
}

void insertEdge(graphType* g, int u, int v)
{
 graphNode* node;
 if(u>=g->n || v>=g->n) {
  printf("\n 그래프에 없는 정점입니다!");
  return;
 }
 node = (graphNode *)malloc(sizeof(graphNode));
 node->vertex = v;
 node->link = g->adjList_H[u];
 g->adjList_H[u] = node;
}

void print_adjList(graphType* g)
{
 int i;
 graphNode* p;
 for(i=0; i<g->n; i++){
  printf("\n\t\t정점%c의 인접리스트", i +65);
  p= g->adjList_H[i];
  while(p){
   printf(" -> %c", p->vertex +65);
   p = p->link;  
  }
 }
}

void DFS_adjList(graphType* g, int v)
{
 graphNode* w; 
 top = NULL;  // 스택 top
 push(v);
 g->visited[v] = TRUE;
 printf(" %c", v +65);
 while(top != NULL){  
  w=g->adjList_H[v];
  while(w){   // 인접정점이 있는 동안 수행
   if (!g->visited[w->vertex]){ // 방문안한 인접정점에 대해서 수행
    push(w->vertex);
    g->visited[w->vertex] = TRUE;
    printf(" %c", w->vertex +65);  // 정점 0~6을 A~G로 바꾸어서 출력
    v = w->vertex; 
    w=g->adjList_H[v];    
   } 
   else w= w->link;
  }
  v = pop(); // 방문안한 인접정점이 없으면 스택 pop !
 }
}

void main()
{
 int i;
 graphType *G9;
 G9 = (graphType *)malloc(sizeof(graphType));
 
 createGraph(G9);
 for(i=0; i<7; i++)
  insertVertex(G9, i);
 insertEdge(G9, 0, 2);
 insertEdge(G9, 0, 1);
 insertEdge(G9, 1, 4);
 insertEdge(G9, 1, 3);
 insertEdge(G9, 1, 0);
 insertEdge(G9, 2, 4);
 insertEdge(G9, 2, 0);
 insertEdge(G9, 3, 6);
 insertEdge(G9, 3, 1);
 insertEdge(G9, 4, 6);
 insertEdge(G9, 4, 2);
 insertEdge(G9, 4, 1);
 insertEdge(G9, 5, 6);
 insertEdge(G9, 6, 5);
 insertEdge(G9, 6, 4);
 insertEdge(G9, 6, 3);
 printf("\n G9의 인접 리스트 ");
 print_adjList(G9);

 printf("\n\n///////////////\n\n깊이우선탐색 >> "); 
 DFS_adjList(G9, 0);  

 getchar();
}
//////////////////////////////////////////
///
//////////////////////////////////////////
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
#define MAX_VERTEX 10
#define FALSE 0
#define TRUE  1

typedef struct graphNode{
 int vertex;
 struct graphNode* link;
} graphNode;

typedef struct graphType{
 int n;
 graphNode* adjList_H[MAX_VERTEX];
 int visited[MAX_VERTEX];
} graphType;

////////  << 큐 연산
typedef struct QNode{
 int data;
 struct QNode *link;
} QNode;

typedef struct{ 
 QNode *front, *rear;
} LQueueType;

LQueueType *createLinkedQueue()
{
 LQueueType *LQ;
 LQ = (LQueueType *)malloc(sizeof(LQueueType));
 LQ->front=NULL;
 LQ->rear=NULL;
 return LQ;
}

int isEmpty(LQueueType *LQ)
{
 if (LQ->front == NULL) {
  printf("\n Linked Queue is empty! \n");
  return 1; 
 }
  else return 0;
}

void enQueue(LQueueType *LQ, int item)
{
  QNode *newNode=(QNode *)malloc(sizeof(QNode));
  newNode->data = item;
  newNode->link = NULL;
  if(LQ->front == NULL) {
   LQ->front = newNode;
   LQ->rear = newNode;  
  }
  else {
  LQ->rear->link = newNode;
  LQ->rear = newNode;
  }
}

int deQueue(LQueueType *LQ)
{
 QNode *old = LQ->front;
 int item;
  if (isEmpty(LQ)) return 0;
  else {
   item = old->data;
   LQ->front = LQ->front->link;
   if(LQ->front == NULL)
   LQ->rear = NULL;
   free(old);
   return item;
  }
}
////////  큐 연산 >>

void createGraph(graphType* g)
{
 int v;
 g->n = 0;
 for(v=0; v<MAX_VERTEX; v++){
  g->visited[v] = FALSE;
  g->adjList_H[v]=NULL;
 }
}

void insertVertex(graphType* g, int v)
{
 if(((g->n)+1)>MAX_VERTEX){
  printf("\n 그래프 정점의 개수를 초과하였습니다!");
  return;
 }
 g->n++;
}

void insertEdge(graphType* g, int u, int v)
{
 graphNode* node;
 if(u>=g->n || v>=g->n) {
  printf("\n 그래프에 없는 정점입니다!");
  return;
 }
 node = (graphNode *)malloc(sizeof(graphNode));
 node->vertex = v;
 node->link = g->adjList_H[u];
 g->adjList_H[u] = node;
}

void print_adjList(graphType* g)
{
 int i;
 graphNode* p;
 for(i=0; i<g->n; i++){
  printf("\n\t\t정점 %c의 인접리스트", i +65);
  p= g->adjList_H[i];
  while(p){
   printf(" -> %c", p->vertex +65);
   p = p->link;  
  }
 }
}

void BFS_adjList(graphType* g, int v)
{
 graphNode* w; 
 LQueueType* Q;  // 큐
 Q = createLinkedQueue();
 g->visited[v] = TRUE;
 printf(" %c", v +65);
 enQueue(Q, v);
 while(! isEmpty(Q)){  
  v=deQueue(Q);
  for(w=g->adjList_H[v]; w; w=w->link)   // 인접정점이 있는 동안 수행
   if (!g->visited[w->vertex]){      // 방문안한 인접정점에 대해서 수행
    g->visited[w->vertex] = TRUE;
    printf(" %c", w->vertex +65);  // 정점 0~6을 A~G로 바꾸어서 출력
    enQueue(Q, w->vertex);    
   }        
 }
}

void main()
{
 int i;
 graphType *G9;
 G9 = (graphType *)malloc(sizeof(graphType));
 
 createGraph(G9);
 for(i=0; i<7; i++)
  insertVertex(G9, i);
 insertEdge(G9, 0, 2);
 insertEdge(G9, 0, 1);
 insertEdge(G9, 1, 4);
 insertEdge(G9, 1, 3);
 insertEdge(G9, 1, 0);
 insertEdge(G9, 2, 4);
 insertEdge(G9, 2, 0);
 insertEdge(G9, 3, 6);
 insertEdge(G9, 3, 1);
 insertEdge(G9, 4, 6);
 insertEdge(G9, 4, 2);
 insertEdge(G9, 4, 1);
 insertEdge(G9, 5, 6);
 insertEdge(G9, 6, 5);
 insertEdge(G9, 6, 4);
 insertEdge(G9, 6, 3);
 printf("\n G9의 인접 리스트 ");
 print_adjList(G9);

 printf("\n\n///////////////\n\n너비우선탐색 >> "); 
 BFS_adjList(G9, 0);  

 getchar();
}
////////////////////////////////////////////////////////////////////////////////////////////////////////////

최소비용신장트리 알고리즘

CODE.zip