edge가 주어질때, source -> destination 에대한 경로가 존재하면 true 아니면 false.
Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
Output: true
Explanation: There are two paths from vertex 0 to vertex 2:
- 0 → 1 → 2
- 0 → 2
https://leetcode.com/problems/find-if-path-exists-in-graph/
그래프 엣지를 표현하는 자료구조 생성(2차원배열로 graph map 생성)
이 방법은, 노드가 많은데 연결이 적은 그래프에서 2차원 배열사이즈가 과도하게 크고, 메모리를 많이 차지한다는 단점이있다.
제출해보면, 답은 맞는데 ,22/26
Test Case에서 Memory Limit Exceeded 가 발생.
int *visit;
int **map;
int dest;
int nr;
bool dfs(int **m, int row)
{
if (row == dest)
return true;
if (visit[row])
return false;
visit[row] = 1;
for (int i = 0; i < nr; i++) {
if (m[row][i] == 1) {
if (dfs(m, i))
return true;
}
}
return false;
}
bool validPath(int n, int** edges, int edgesSize, int* edgesColSize, int source, int destination)
{
bool ret = false;
dest = destination;
nr = n;
map = (int **)calloc(n, sizeof(int *));
for (int i = 0; i < n; i++)
map[i] = (int *)calloc(n, sizeof(int *));
visit = (int *)calloc(n, sizeof(int));
/* generate graph map */
for (int i = 0; i < edgesSize; i++)
map[edges[i][0]][edges[i][1]] = map[edges[i][1]][edges[i][0]] = 1;
ret = dfs(map, source);
for (int i = 0; i < n; i++)
free(map[i]);
free(map);
return ret;
}
그래프 엣지를 표현하는 자료구조 생성(인접 리스트 방식) 가령, 엣지가 [[0,1],[0,2],[3,5],[5,4],[4,3]]
로 주어질때, 엣지를 표현하는 링크드 리스트는 아래와 같다.
[0] -> 1 -> 2
[1] -> 0
[2] -> 0
[3] -> 4 -> 5
[4] -> 3 -> 5
[5] -> 3 -> 4
Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
Output: false
링크드 리스트를 생성할때 주의점. 이 그래프는 방향이 없는 그래프 이기 때문에, [a,b] 일때 a->b 그리고 b->a두개를 malloc해서 추가해야한다.
DFS구현은 visit[] 배열이 1로 바뀌느 시점 확인.
struct node {
int val;
struct node *next;
};
struct node **map;
bool *visit;
bool dfs(struct node **m, int curr, int dest)
{
if (curr == dest)
return true;
if (visit[curr])
return false;
visit[curr] = 1;
struct node *node = m[curr];
for (;node != NULL; node = node->next)
if (dfs(m, node->val, dest))
return true;
return false;
}
bool validPath(int n, int** edges, int edgesSize, int* edgesColSize, int source, int destination)
{
map = (struct node **)calloc(n, sizeof(struct node *));
visit = (bool *)calloc(n, sizeof(bool));
/* generate graph map */
for (int i = 0; i < edgesSize; i++) {
// a -> b
struct node *newnode = (struct node *)malloc(sizeof(struct node));
newnode->val = edges[i][1];
newnode->next = map[edges[i][0]];
map[edges[i][0]] = newnode;
// b -> a
newnode = (struct node *)malloc(sizeof(struct node));
newnode->val = edges[i][0];
newnode->next = map[edges[i][1]];
map[edges[i][1]] = newnode;
}
return dfs(map, source, destination);
}