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