그래프 알고리즘.

<그래프 구현>

MAXV : vertex의 최대 개수

MAXDEGREE : 차수의 최대 값

 

typedef struct

{

                  int edges[MAXV+1][MAXDEGREE];   //연결상태

                  int degree[MAXV+1];              // 각 차수

                  int nvertices;            // vertex의 개수

                  int nedges;                // edge의 개수

}

BFS ( 너비 우선 탐색 qseudo code )

BFS(G, s)         // G 그래프 객체 , S 스타트 vertex

 

for each vertex u ∈ V – {s}

do color[u] ← GRAY

d[u] ← ∞

π[u] ← NIL

 

color[s] ← BLUE

d[s] ← 0

π[s] ← NIL

ENQUEUE(Q, s)

 

while (Q ≠ φ)

do u ← DEQUEUE(Q)

for each v ∈ Adj[u]

do if color[v] ← GRAY

then color[v] ← BLUE

d[v] ← d[v] + 1

π[v] ← u

ENQUEUE(Q, v)

color[u] ← GREEN