C언어 그래프 구현

(C언어 그래프 (인접행렬)에서 넘어옴)

1 예시 1[ | ]

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

typedef struct { 
	int vertexCount; 
	int **matrix; 
} graphType;

graphType *createGraph(int vertexCount) {
	int i;
	graphType *graph = (graphType *)malloc(sizeof(graphType) * vertexCount);
	graph->matrix = (int **)malloc(sizeof(int *) * vertexCount);
	graph->vertexCount = vertexCount;
	for (i = 0; i < vertexCount; i++) {
		graph->matrix[i] = (int *)malloc(sizeof(int) * vertexCount);
		memset(graph->matrix[i], 0, sizeof(int) * vertexCount);
	}
	return graph;
}

void addEdge(graphType *graph, int start, int goal) {
	graph->matrix[start - 1][goal - 1] = 1;	
}

void printGraph(graphType *graph) {
	int i, j;
	for (i = 0; i < graph->vertexCount; i++) {
		printf("start %d ->", i);
		for (j = 0; j < graph->vertexCount; j++) {
			printf(" %d", graph->matrix[i][j]);
		}
		printf("\n");
	}
}

int main() {
	graphType *graph;
	graph = createGraph(5);
	addEdge(graph, 1, 2);
	addEdge(graph, 1, 3);
	addEdge(graph, 1, 4);
	addEdge(graph, 1, 5);
	addEdge(graph, 2, 3);
	addEdge(graph, 2, 5);
	addEdge(graph, 5, 4);
	printGraph(graph);
}

2 예시 2[ | ]

#include <stdio.h>
#include <malloc.h>

// 그래프의 노드 구조체
typedef struct node {
    int vertex;
    struct node* next;
} Node;

// 그래프 구조체
typedef struct {
    int numVertices;
    Node** adjLists;
} Graph;

Node* createNode(int v) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;

    graph->adjLists = malloc(vertices * sizeof(Node*));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    // src에서 dest로 가는 간선 추가
    Node* newNode = createNode(dest);
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 무향 그래프인 경우, dest에서 src로 가는 간선도 추가
    newNode = createNode(src);
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

void printGraph(Graph* graph) {
    for (int v = 0; v < graph->numVertices; v++) {
        Node* temp = graph->adjLists[v];
        printf("Adjacency list of vertex %d: ", v);
        while (temp) {
            printf("%d ", temp->vertex);
            temp = temp->next;
        }
        printf("\n");
    }
}

int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);
}

3 예시 3[ | ]

#include <stdio.h>
#include <malloc.h>
 
typedef struct adjlistNode {
    int vertex;
    struct adjlistNode* next;
} AdjlistNode;
 
typedef struct {
    int num_members;
    AdjlistNode* head;
    AdjlistNode* tail;
} AdjList;
 
typedef struct {
    int numVertices;
    AdjList* adjListArr;
} Graph;

Graph* graph;
 
AdjlistNode* _newNode(int v) {
    AdjlistNode* node = (AdjlistNode *)malloc(sizeof(AdjlistNode));
    node->vertex = v;
    node->next = NULL;
    return node;
}
 
void init(int numVertices) {
    graph = (Graph *)malloc(sizeof(Graph));
    graph->numVertices = numVertices;
    graph->adjListArr = (AdjList *)malloc(numVertices * sizeof(AdjList));
    for (int i=0; i<numVertices; i++) {
        graph->adjListArr[i].head = graph->adjListArr[i].tail = NULL;
        graph->adjListArr[i].num_members = 0;
    }
}
 
void destroy() {
    if (!graph) return;
    if (graph->adjListArr) {
        for (int v = 0; v < graph->numVertices; v++) {
            AdjlistNode* adjListPtr = graph->adjListArr[v].head;
            while (adjListPtr) {
                AdjlistNode* temp = adjListPtr;
                adjListPtr = adjListPtr->next;
                free(temp);
            }
        }
        free(graph->adjListArr);
    }
    free(graph);
}
 
void add(int src, int dest) {
    AdjlistNode* node = _newNode(dest);
    if (graph->adjListArr[src].tail != NULL) {
        graph->adjListArr[src].tail->next = node;
        graph->adjListArr[src].tail = node;
    } else {
        graph->adjListArr[src].head = graph->adjListArr[src].tail = node;
    }
    graph->adjListArr[src].num_members++;
    node = _newNode(src);
    if (graph->adjListArr[dest].tail != NULL) {
        graph->adjListArr[dest].tail->next = node;
        graph->adjListArr[dest].tail = node;
    } else {
        graph->adjListArr[dest].head = graph->adjListArr[dest].tail = node;
    }
    graph->adjListArr[dest].num_members++;
}
 

int main(int argc, char* argv[]) {
    init(7);
    add(1, 2);
    add(1, 5);
    add(2, 3);
    add(2, 5);
    add(3, 4);
    add(4, 5);
    add(4, 6);

    for (int i = 0; i < 6; i++) {
        printf("%d -> ", i);
        AdjlistNode * adjListPtr = graph->adjListArr[i].head;
        while (adjListPtr) {
            printf("%d ", adjListPtr->vertex);
            adjListPtr = adjListPtr->next;
        }
        printf("\n");
    }
}

4 같이 보기[ | ]

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}