#include <stdio.h>
#include <stdlib.h>
//인접행렬 만들기
int arr[100][100];
int allVisited(int* visited, int row) //모든 vertex가 방문되었다면 1을 반환, 그렇지 않다면 0을 반환
{
int flag = 1;
for (int i = 0; i < row; i++)
{
if (!visited[i])
flag = 0;
}
if (flag == 1)
return 1;
else
return 0;
}
void dfs(int arr[][7], int* visited, int* stack, int top, int vertex, int row)
{
visited[vertex] = 1;
printf("%d ", vertex+1);
int i;
for (i = 0; i < row; i++)
{
if (arr[vertex][i] == 1 && visited[i] == 0)
dfs(arr, visited, stack, top, i, row);
}
}
int main()
{
int vertex, edge;
int arr[7][7] = { { 0, 1, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 1, 1, 0, 0 },
{ 1, 0, 0, 0, 1, 0, 0 },
{ 0, 1, 0, 0, 0, 0, 1 },
{ 0, 1, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 1, 1, 1, 0 } };
vertex = 7;
//인접 행렬 출력
for (int i = 0; i < vertex; i++)
{
for (int j = 0; j < vertex; j++)
{
printf("%d ", arr[i][j]);
}
printf("\n");
}
printf("\n\n");
//visited 배열 만들기
int* visited = (int*)malloc(sizeof(int) * vertex);
for (int i = 0; i < vertex; i++)
*(visited + i) = 0; //내부를 0으로 초기화
//비어있는 스택 만들기
int top = -1; //stack 의 top
int stack[50] = { 0 };
//dfs 시작! 맨 처음 vertex보낸다.
dfs(arr, visited, stack, top, 0, vertex);
}
대학교 자료구조 강의 듣고 없는 실력 있는 실력 다 끌어모아서 어떻게든 혼자 그래프 구현해보려고 안간힘....
인접행렬 구현은 너무 쉬웠는데 dfs 탐색은 혼자 아무리 해도 원하는 출력 결과가 나오지 않아서 결국 교수님께 질문....
교수님 피드백을 약간 받아서 겨우겨우 완성....ㅠㅠ
혹시 개선되어야 할 점이 있다면 언제든지 댓글 달아주세요! 감사합니다.
'Data Structure & Algorithm' 카테고리의 다른 글
동적 프로그래밍 (DP) 해결 방법 (0) | 2022.02.06 |
---|---|
파이썬으로 연결 리스트(Linked List) 구현해보기 (0) | 2020.03.25 |
python 을 활용한 자료구조와 알고리즘 공부 - (5) (0) | 2020.03.10 |
python 을 활용한 자료구조와 알고리즘 공부 - (4) (0) | 2020.03.09 |
python 을 활용한 자료구조와 알고리즘 공부 - (3) (0) | 2020.03.05 |