그래프 G =(V,E)
V: 노드 node , 정점vertex
E: 노드쌍을 연결하는 edge 혹은 link
n=|V| = 8
m=|E| = 11
방향 그래프 directed Graph
가중치(Weighted) 그래프 : 에지마다 가중치가 지정된다
인접행렬 adjacency matrix
당연히 대칭 행열
n*n 행렬
A = (a ij)
edge있으면 1 없으면 0
저장공간 O(n^2)
어떤 노드 v에 인접한 모든 노드 찾기 O(n)
어떤 에지 (u,v)가 존재하는지 검사 O(1)
인접 리스트 (adjacency list)
정점 집합을 표현하는 하나의 배열과
각 정점마다 인접한 정점들의 연결리스트
비대칭
저장공간 O(n+m)
어떤 노드 v에 인접한 모든 노드 찾기 O(degree(V)) degree(v): 최악의 경우 n ,행렬보다 더좋음
어떤 에지 (u,v)가 존재하는지 검사 O(degree(U)) O(n) ,행렬보다 더 나쁨
가중치 그래프의 인접 행렬 표현
에지의 존재를 나타내는 값으로 에지의 가중치를 저장 1대신에
경로와 연결성
무방향 그래프 G = (V,E)에서 노드 u와 노드 v를 연결하는 경로 path가 존재할때 v와 u는 서로 연결되어 있다
노드 쌍들이 서로 연결된 그래프를 연결된 그래프라고 한다
연결 요소 connected component
그래프 순회 - 모든 노드들을 방문하는 일
너비우선순회 - BFS (Breadth First Search)
동심원의 형태로 순회
L0 = {s} 여기서 s는 출발노드
L1 = L0의 모든 이웃 노드들
L2 = L1의 이웃들 중 L0에 속하지 않는 노드들
1.check the start node
2. insert the start node into the queue.
while the queue is not empty do
remove a node v from queue
for each unchecked neighbour w of v do
check and insert w into the queue
노드 방문 순서 : 1 2 3 4 5 7 8 6 (유일하지않음)
BFS(G,s)
Q <- 공집합
Enqueue (Q,s); //출발노드를 Q에 넣는다
while Q!=공집합 do
u <- Dequeue(Q) // Q에서 꺼내기
for each v adjacent to u do
if v is unvisited then
mark v as visited;
Enqueue(Q,v);
end
end
end
최단 경로
S에서 Li에 속한 노드까지의 최단경로의 길이는 i이다
경로의 길이는 경로에 속한 edge의 개수를 의미한다
BFS를 하면서 각 노드에 대해서 최단 경로의 길이를 구할 수 있다
방향/무방향그래프, 출발노드s
모든 노드 v에대해
d[v] = s로부터 v까지의 최단 경로의 길이(edge의 개수)
ㅠ[v] = s로부터 v까지의 최단 경로상에서 v의 직전노드 , predecessor
BFS(G,s)
Q <- 공집합;
d[s] <- 0; //출발점으로부터 s까지감
ㅠ[s] = null; // 그 경로상에서 나한테 도착하기 직전 노드
Enqueue (Q,s); //출발노드를 Q에 넣는다
while Q!=공집합 do
u <- Dequeue(Q) // Q에서 꺼내기
for each v adjacent to u do
if v is unvisited then
mark v as visited;
d[v] = d[u] + 1; // distance to v
ㅠ[v] = u; // u는 v의 predecessor이다
Enqueue(Q,v);
end
end
end
BFS(G,s)
Q <- 공집합;
for each node u do //o(n)
d[u] <- -1;
ㅠ[u] <- null;
end
d[s]=0;
ㅠ[s] = null;
Enqueue (Q,s); //출발노드를 Q에 넣는다
while Q!=공집합 do // while문 한번돌때마다 큐에서 하나씩 꺼내므로 while문은 최대 n번 돈다
u <- Dequeue(Q) // Q에서 꺼내기
for each v adjacent to u do // 인접리스트로 구현할경우 for문은 각 노드 v에 대해서 degree(v)=한노드의 실제로 인접한 노드개수 번 돈다 , 2m이다! o(n+m), 인접 행렬 o(n) 전체 o(n^2)
if(d[v]==-1)then
d[v] = d[u] + 1; // distance to v
ㅠ[v] = u; // u는 v의 predecessor이다
Enqueue(Q,v);
end.
end.
학교 ppt 수도코드는 다음과 같다~~~~~ > <
BFS(G,s)
for each node u < V-{s} do
color [u] <- WHITE;
d[u] <- 무한대;
ㅠ[u] <- null;
end
color[s] <- GRAY;
d[s]=0;
ㅠ[s] = null;
Q <- {s} // Enqueue (Q,s); //출발노드를 Q에 넣는다
while Q!=공집합 do // while문 한번돌때마다 큐에서 하나씩 꺼내므로 while문은 최대 n번 돈다
u <- head[Q] // u <- Dequeue(Q) // Q에서 꺼내기
for each v adjacent to u do // 인접리스트로 구현할경우 for문은 각 노드 v에 대해서 degree(v)=한노드의 실제로 인접한 노드개수 번 돈다 , 2m이다! o(n+m), 인접 행렬 o(n) 전체 o(n^2)
if(color[v] = WHITE)then
d[v] = d[u] + 1; // distance to v
ㅠ[v] = u; // u는 v의 predecessor이다
Enqueue(Q,v);
Dequeue(Q)
color[u] <- BLACK //큐에서 나갔다는 정점임을 표시해주기위해서 블랙으로??
깊이우선순회 (DFS) - inroder preorder postorder 은 dfs의 이진트리방법임
1. 출발점 s에서 시작한다
2. 현재노드를 visited로 mark하고 인접한 노드들 중 unvisited노드가 존재하면 그 노드로 간다
3. 2번 계속 반복한다
4. 만약 unvisited 인 이웃노드가 존재하지않으면 계속해서 직전노드를 되돌아 간다
되돌아갈 노드는 그 노드에 처음 도착할때 누구로부터 왔는냐가 바로 되돌아갈 노드이다~~~!!!!
5. 다시 2번을 반복한다
6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다
1 -> 3 -> 7 -> 8 -> 막혔네 마치 leaf node에 도달한거랑 비슷 -> 5 -> 2 -> 4 -> 6 ->
DFS(G,v)
visited[v] <-YES
for each node u adjacent to v do
if visited[u] = NO then
DFS(G,u);
//이미 다 방문한 상태면 종료됨. 그러면 이미 그전에 있는 재귀함수 DFS가 수행됨. 이때 u로 되돌아 감
disconnected이거나 방향그래프라면 dfs에 의해서 모든 노드가 방문되지않을 수 있다
DFS를 반복하여 모든 노드 방문
DFS-ALL(G,v)
for each v < V //o(n) n: 노드개수
visited[v] <- no;
for each v < V
if visited[v] = NO then
DFS(G,v); //위의 코드!! //edge 1개당 1개의 recursion 호출! v에대해서 정점 u, u에대해서 v도 탐색 가능//인접리스트 o(m)-> 시간복잡도!o(n+m)
//시간 복잡도 o(n+m)
학교 ppt 수도코드는 다음과 같다~~~~~ > <
DFS(G)
for each u < V do
color[u] <- white
ㅠ[u] <- NIL
time <-0
for each u < V
if color[u] = white then
DFS_visit(G,u); //위의 코드!! //edge 1개당 1개의 recursion 호출! v에대해서 정점 u, u에대해서 v도 탐색 가능//인접리스트 o(m)-> 시간복잡도!o(n+m)
//시간 복잡도 o(n+m)
DFS-visit(G,u)
color[u]<- gray
d[u] <- time <- time+1
for each v < Adj[u] do
if color[v] = white them
ㅠ[v] <- u
DFS-visit(G,v)
color[u] <- black
f[u] <- time <- time+1
codecodecode
'정보통신공학' 카테고리의 다른 글
11장 Local area network overview 1~ 25 (0) | 2023.06.05 |
---|---|
10. Celluar Wireless Networks (0) | 2023.05.22 |
chap 9 WAN Circuit switching / packet switching (0) | 2023.05.21 |
정통공 용어 정리 (0) | 2023.05.21 |