Lưu vết quá trình tìm kiếm bằng DFS

Đề bài: Cho đồ thị G, tập đỉnh V và tập cạnh E. Tìm đường đi từ đỉnh S đến đỉnh T và in ra các đỉnh và trạng thái của chúng:
– Trạng thái 1: Những đỉnh thuộc đường đi từ S -> T (BELONG_TO_PATH)
– Trạng thái 2: Những đỉnh không thuộc đường đi từ S -> T nhưng được viếng thăm (ATTEMPTED)
– Trạng thái 3: Những đỉnh không được viếng thăm (UNVISITED)

Mã giả C++:

bool dfs(int U) {
    // U is visited    
    if (U == T) return true;
    for(options V) {	
	if (V is unvisited && dfs(V)) { 
	    state[V] = BELONG_TO_PATH;
	    return true;
	}	
    }
    state[U] = ATTEMPTED;
    return false;
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s