[Đồ thị] Lý thuyết đồ thị - Đường đi, Chu trình, Đồ thị liên thông

Đồ thị: là một cấu trúc dữ liệu rời rạc bao gồm các đỉnh và các cạnh nối các cặp đỉnh này. Chúng ta phân biệt đồ thị thông qua kiểu và số lượng cạnh nối giữa các cặp đỉnh của đồ thị.
Dưới đây là một ví dụ về mạng máy tính bao gồm: mỗi máy tính là một đỉnh, mỗi kênh điện thoại kết nối là cạnh của đồ thị

Đồ thị: Mạng máy tính

Trong mạng máy tính trên, mỗi máy tính là một đỉnh của đồ thị, các kênh điện thoại là cạnh của đồ thị, không có hai cặp cạnh nào nối cùng một cặp đỉnh. Ta gọi đây là đơn đồ thị vô hướng.
Đơn đồ thị vô hướng: Đơn đồ thị vô hướng G = <V,E> bao gồm V là tập các đỉnh, E là tập các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh.
Trong trường hợp giữa máy tính nào đó thường xuyên phải truyền tải thông tin nên người ta xây dựng thêm một kênh điện thoại nữa để tăng khả năng truyền tải thông tin, khi đó hai máy tính sẽ có nhiều hơn một kênh điện thoại kết nối. Ta gọi đây là đa đồ thị vô hướng.

Mạng máy tính đa kênh thoại

Đa đồ thị vô hướng: G = <V, E> bao gồm V là tập các đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là tập các cạnh. e1, e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh.

Mạng máy tính đa kênh thoại có khuyên

Giả đồ thị vô hướng: G = <V, E> bao gồm V là tập đỉnh, E là họ các cặp không có thứ tự gồm hai phần tử (hai phần tử không nhất thiết phải khác nhau) trong V được gọi là các cạnh. Cạnh e được gọi là khuyên nếu có dạng e =(u, u), trong đó u là đỉnh nào đó thuộc V.

Trong nhiều mạng, các kênh kết nối giữa hai máy tính chỉ có thể truyền tải thông tin theo một chiều.Chẳng hạn máy tính đặt tại Hà Nội có thể truy cập dữ liệu của máy tính đặt tại Hải Phòng, nhưng máy tính ở Hải Phòng không thể truy cập dữ liệu của máy tính ở Hà Nội. Để mô tả mạng máy tính này chúng ta dùng khái niệm đồ thị có hướng.

Mạng máy tính có hướng

Đơn đồ thị có hướng G = <V, E> bao gồm V là tập các đỉnh, E là tập các cặp có thứ tự gồm hai phần tử của V gọi là các cung.
Trong trường hợp có nhiều hơn một kênh có hướng kết nối giữa hai đỉnh của đồ thị, để mô tả mạng máy tính này ta dùng khái niệm đa đồ thị có hướng.

Mạng máy tính đa kênh một chiều 

Đa đồ thị có hướng G = <V, E> bao gồm V là tập đỉnh, E là cặp có thứ tự gồm hai phần tử của V được gọi là các cung. Hai cung e1, e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.

Loại đồ thị	Cạnh	Có cạnh bội	Có khuyên
Đơn đồ thị vô hướng	Vô hướng	Không	Không
Đa đồ thị vô hướng	Vô hướng	Có	Không
Giả đồ thị vô hướng	Vô hướng	Có	Có
Đồ thị có hướng	Có hướng	Không	Có
Đa đồ thị có hướng	Có hướng	Có	Có

*Hai đỉnh u và v của đồ thị vô hướng G =<V, E> được gọi là kề nhau nếu (u,v) là cạnh thuộc đồ thị G. Nếu e =(u, v) là cạnh của đồ thị G thì ta nói cạnh này liên thuộc với hai đỉnh u và v, hoặc ta nói cạnh e nối đỉnh u với đỉnh v, đồng thời các đỉnh u và v sẽ được gọi là đỉnh đầu của cạnh (u,v).
*Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và ký hiệu là deg(v).
deg(a) = 2, deg(b) =deg(c) = deg(f) = 4, deg(e) = 3, deg(d) = 1, deg(g)=0.

Đồ thị có hướng G

Nếu e=(u,v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u, v) nối đỉnh u với đỉnh v. Đỉnh u sẽ được gọi là đỉnh đầu v là đỉnh cuối của cung (u,v).
Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v) và deg-(v).
deg-(a) = 1, deg-(b) = 2, deg-(c) = 2, deg-(d) = 2, deg-(e) = 2. deg+(a) = 3, deg+(b) = 1, deg+(c) = 1, deg+(d) = 2, deg+(e) = 2.
Đường đi: Đường đi độ dài n từ đỉnh u đến đỉnh v trên đồ thị vô hướng G=<V,E> là dãy: x0, x1,..., xn-1, xn trong đó n là số nguyên dương, x0=u, xn=v, (xi, xi+1)∈E, i =0, 1, 2,..., n-1.
Đường đi như trên còn có thể biểu diễn thành dãy các cạnh:
(x0, x1), (x1,x2),..., (xn-1, xn).
Đỉnh u là đỉnh đầu, đỉnh v là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (u=v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào lặp lại.
Đồ thị vô hướng được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

[Thuật toán] Duyệt các thành phần liên thông của đồ thị

Một đồ thị có thể liên thông hoặc không liên thông. Nếu đồ thị liên thông thì số thành phần liên thông của nó là 1. Điều này tương đương với phép duyệt theo thủ tục DFS() hoặc BFS() được gọi đến đúng một lần. Nếu đồ thị không liên thông (số thành phần liên thông lớn hơn 1) chúng ta có thể tách chúng thành những đồ thị con liên thông. Điều này cũng có nghĩa là trong phép duyệt đồ thị, số thành phần liên thông của nó bằng số lần gọi tới thủ tục DFS() hoặc BFS().
Để xác định số các thành phần liên thông của đồ thị, chúng ta sử dụng biến mới solt để nghi nhận các đỉnh cùng một thành phần liên thông trong mảng chuaxet[] như sau:
- Nếu đỉnh i chưa được duyệt, chuaxet[i]có giá trị 0;
- Nếu đỉnh i được duyệt thuộc thành phần liên thông thứ j=solt, ta ghi nhận chuaxet[i]=solt;
- Các đỉnh cùng thành phần liên thông nếu chúng có cùng giá trị trong mảng chuaxet[].
Với cách làm như trên, thủ tục BFS() có thể được sửa lại như sau:

void BFS(int u){ 
 queue = φ; 
 u <= queue; /*nạp u vào hàng đợi*/
 solt = solt+1; chuaxet[u] = solt; /*solt là biến toàn cục thiết lập giá trị0*/
 while (queue ≠ φ) { 
  queue<=p; /* lấy p ra từstack*/
  for v ∈ke(p) { 
   if (chuaxet[v] ) { 
    v<= queue; /*nạp v vào hàng đợi*/
    chuaxet[v] = solt; /* v có cùng thành phần liên thông với p*/
   } 
  } 
 } 
} 

Để duyệt hết tất cả các thành phần liên thông của đồ thị, ta chỉ cần gọi tới thủ tục liên thông như dưới đây:

void Lien_Thong(void){ 
 for (i=1; i≤n; i++) 
  chuaxet[i] =0; 
 for(i=1; i<=n; i++) 
  if(chuaxet[i]==0){ 
   solt=solt+1; 
   BFS(i); 
  } 
} 

Để ghi nhận từng đỉnh của đồ thị thuộc thành phần liên thông nào, ta chỉ cần duyệt các đỉnh có cùng chung giá trị trong mảng chuaxet[] như dưới đây:

void Result( int solt){ 
 if (solt==1){ 
  < Do thi la lien thong>; 
 } 
 for( i=1; i<=solt;i++){ 
  /* Đưa ra thành phần liên thông thứi*/
  for( j=1; j<=n;j++){ 
   if( chuaxet[j]==i) 
    <đưa ra đỉnh j>; 
  } 
 } 
}

Số thành phần liên thông	Kết quả duyệt BFS	Giá trị trong mảng chuaxet[]
0	Chưa thực hiện	Chuaxet[]={0,0,0,0,0,0,0,0,0}
1	BFS(1): 1,2,4,5	Chuaxet[]={1,1,0,1,1,0,0,0,0}
2	BFS(3): 3,6,7	Chuaxet[]={1,1,2,1,1,2,2,0,0}
3	BFS(8): 8,9	Chuaxet[]={1,1,2,1,1,2,2,3,3}

*Đỉnh 1,2,4,5 có giá trị 1trong mảng chuaxet[] thuộc thành phần liên thông thứ 1;
*Đỉnh 3, 6,7 cùng có giá trị 2 trong mảng chuaxet[] thuộc thành phần liên thông thứ 2;
*Đỉnh 8, 9 cùng có giá trị 3 trong mảng chuaxet[] thuộc thành phần liên thông thứ 3.
Chương trình cài đặt như sau:

#include<iostream>
#include <conio.h> 
#define MAX  100 
#define TRUE 1 
#define FALSE 0 
using namespace std;
int G[MAX][MAX], n, chuaxet[MAX], QUEUE[MAX], solt,i; 

void Init(){ 
 freopen("lienth.IN", "r", stdin); 
 cin>>n;
 cout<<" so dinh cua do thi n = "<<n;
 //nhập ma trận kề của đồ thị.
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>G[i][j];
  } 
 } 
 //Khởi tạo giá trị ban đầu cho mảng chuaxet.
 for(int i=1; i<=n;i++) 
  chuaxet[i]=0; 
 solt=0; 
} 
void Result(int *chuaxet, int n, int solt){ 
 if(solt==1){ 
  printf("\n Do thi la lien thong"); 
  getch(); return; 
 } 
 for(int i=1; i<=solt;i++){ 
  printf("\n Thanh phan lien thong thu %d:",i); 
  for(int j=1; j<=n;j++){ 
   if( chuaxet[j]==i) 
    printf("%3d", j); 
  } 
 } 
} 
/* Breadth First Search */
void BFS(int G[][MAX], int n, int i, int *solt, int chuaxet[], int QUEUE[MAX]){ 
 int u, dauQ, cuoiQ, j; 
 dauQ=1; cuoiQ=1;
 QUEUE[cuoiQ]=i;chuaxet[i]=*solt; 
 while(dauQ<=cuoiQ){ 
  u=QUEUE[dauQ];
  dauQ=dauQ+1; 
  for(j=1; j<=n;j++){ 
   if(G[u][j]==1 && chuaxet[j]==0){ 
    cuoiQ=cuoiQ+1; 
    QUEUE[cuoiQ]=j; 
    chuaxet[j]=*solt; 
   } 
  } 
 } 
} 
void Lien_Thong(void){ 
 Init(); 
 for(i=1; i<=n; i++) 
  if(chuaxet[i]==0){ 
   solt=solt+1; 
   BFS(G, n, i, &solt, chuaxet, QUEUE); 
  } 
  Result(chuaxet, n, solt); 
  _getch();
} 
int main(void){ 
 Lien_Thong(); 
 return 0;
}

Dữ liệu file input lienth.IN như sau:

9
0 1 0 1 0 0 0 0 0
1 0 0 0 1 0 0 0 0
0 0 0 0 0 1 1 0 0
1 0 0 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0
0 0 1 0 0 0 1 0 0
0 0 1 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0

Trong đó: n = 9 là số đỉnh của đồ thị, tiếp theo đó là ma trận kề của đồ thị

Két quả khi chạy trương trình.

So dinh của do thi n = 9
Thanh phan lien thong thu 1: 1 2 4 5
Thanh phan lien thong thu 2: 3 6 7
Thanh phan lien thong thu 3: 8 9

[Thuật toán] Tìm kiếm theo chiều rộng BFS.

Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây.
Lý thuyết về thuật toán tìm kiếm theo chiều sâu bạn có thể xem ở đây.
Khác với thuật toán tìm kiếm theo chiều sâu, thuật toán tìm kiếm theo chiều rộng thay thế việc sử dụng stack bằng hàng đợi queue. Trong thủ tục này, đỉnh được nạp vào hàng đợi đầu tiên là v, các đỉnh kề với v ( v1, v2,..., vk) được nạp vào queue kế tiếp. Quá trình duyệt tiếp theo được bắt đầu từ các đỉnh còn có mặt trong hàng đợi.
Để ghi nhận trạng thái duyệt các đỉnh của đồ thị, ta cũng vẫn sử dụng mảng chuaxet[] gồm n phần tử thiết lập giá trị ban đầu là TRUE. Nếu đỉnh i của đồ thị đã được duyệt, giá trị chuaxet[i] sẽ nhận giá trị FALSE. Thuật toán dừng khi hàng đợi rỗng. Thủ tục BFS dưới đây thể hiện quá trình thực hiện của thuật toán:

void BFS(int u){ 
 queue = φ; 
 u <= queue; /*nạp u vào hàng đợi*/
 chuaxet[u] = false;/* đổi trạng thái của u*/
 while (queue ≠ φ) { /* duyệt tới khi nào hàng đợi rỗng*/
  queue<=p; /*lấy p ra từ khỏi hàng đợi*/
  Thăm_Đỉnh(p); /* duyệt xong đỉnh p*/
  for (v ∈ke(p) ) {/* đưa các đỉnh v kề với p nhưng chưa được xét vào hàng đợi*/
   if (chuaxet[v] ) { 
    v<= queue; /*đưa v vào hàng đợi*/
    chuaxet[v] = false;/* đổi trạng thái của v*/
   } 
  } 
 } /* end while*/
}/* end BFS*/

Thủ tục BFS sẽ thăm tất cả các đỉnh cùng thành phần liên thông với u. Để thăm tất cả các đỉnh của đồ thị, chúng ta chỉ cần thực hiện đoạn chương trình dưới đây:

for (u=1; u≤n; u++) 
 chuaxet[u] = TRUE; 
for (u∈V ) 
 if (chuaxet[u] ) 
  BFS(u);

Đồ thị - Tìm kiếm theo chiều rộng BFS

STT	Các đỉnh đã duyệt	Các đỉnh trong hàng đợi	Các đỉnh còn lại
1	Ѳ	Ѳ	1,2,3,4,5,6,7,8,9,10,11,12,13
2	1	2,3,11	4,5,6,7,8,9,10,12,13
3	1,2	3,11,4,6	5,7,8,9,10,12,13
4	1,2,3	11,4,6	5,7,8,9,10,12,13
5	1,2,3,11	4,6,12,13	5,7,8,9,10
6	1,2,3,11,4	6,12,13	5,7,8,9,10
7	1,2,3,11,4,6	12,13,7,8	5,9,10
8	1,2,3,11,4,6,12	13,7,8	5,9,10
9	1,2,3,11,4,6,12,13	7,8,9	5,10
10	1,2,3,11,4,6,12,13,7	8,9	5,10
11	1,2,3,11,4,6,12,13,7,8	9,10	5
12	1,2,3,11,4,6,12,13,7,8,9	10,5	Ѳ
13	1,2,3,11,4,6,12,13,7,8,9,10	5	Ѳ
14	1,2,3,11,4,6,12,13,7,8,9,10,5	Ѳ	Ѳ

Kết quả duyệt: 1,2,3,11,4,6,12,13,7, 8, 9,10, 5. 
Ma trận liền kề được tải về tại đây.
Chương trình cài đặt bằng C/C++

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX  100 
#define TRUE 1 
#define FALSE 0 
int G[MAX][MAX], n, chuaxet[MAX], QUEUE[MAX]; 
void Init(){ 
 freopen("BFS.IN","r",stdin);
 cin>>n;
 cout<<"So dinh cua do thi n = "<<n<<endl;
 //nhap ma tran lien ke.
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>G[i][j]; 
  } 
 } 
 for(int i=1; i<=n;i++){
  chuaxet[i]=TRUE; 
 }
} 
/* Breadth First Search */
void BFS(int i){ 
 int u,dauQ, cuoiQ;
 dauQ=1; cuoiQ=1;QUEUE[cuoiQ]=i;chuaxet[i]=FALSE; 
 /* thiết lập hàng đợi với đỉnh đầu là i*/
 while(dauQ<=cuoiQ){ 
  u=QUEUE[dauQ];// lấy đỉnh u ra khỏi queue.
  cout<<"duyet dinh: "<<u<<endl;
  dauQ=dauQ+1; /* duyệt đỉnh đầu hàng đợi*/
  for(int j=1; j<=n;j++){ 
   if(G[u][j]==1 && chuaxet[j] ){ 
    cuoiQ=cuoiQ+1; 
    QUEUE[cuoiQ]=j; 
    chuaxet[j]=FALSE; 
   } 
  } 
 } 
} 
void main(void){ 
 Init(); 
 for(int i=1; i<=n; i++) 
  if (chuaxet[i])
   BFS(i); 
 _getch(); 
}

Chương trình  cài đặt bằng Java

package simplecodecjava.blogspot.com;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class BFSAlgorithm {
 static final int MAX = 100;
 int G[][] = new int[MAX][MAX];/* ma trận kề*/
 boolean chuaxet[] = new boolean[MAX];/*mảng đánh dấu đỉnh đã được thăm.*/
 int QUEUE[] = new int[MAX]; /*hàng đợi*/
 int n;

 void init() {
  File file = new File(getClass().getResource("BFS.IN").getPath());
  BufferedReader reader = null;
  try {
   reader = new BufferedReader(new FileReader(file));
   n = Integer.parseInt(reader.readLine());
   for (int i = 1; i <= n; i++) {
    String[] aLineOfMatrix = reader.readLine().split("\\s+");
    for (int j = 1; j <= n; j++) {
     G[i][j] = Integer.parseInt(aLineOfMatrix[j - 1]);/*index của J bắt đầu từ 0*/
    }
   }
  } catch (FileNotFoundException e) {
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  } finally {
   if (reader != null)
    try {
     reader.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
  }
 }

 void BFS(int v) {
  int u, dauQ, cuoiQ, j;
  dauQ = 1;
  cuoiQ = 1;
  QUEUE[cuoiQ] = v;
  chuaxet[v] = false;
  /* thiết lập hàng đợi với đỉnh đầu là i */
  while (dauQ <= cuoiQ) {
   u = QUEUE[dauQ];
   System.out.print(u + " ");
   dauQ = dauQ + 1; /* duyệt đỉnh đầu hàng đợi */
   for (j = 1; j <= n; j++) {
    if (G[u][j] == 1 && chuaxet[j]) {
     cuoiQ = cuoiQ + 1;
     QUEUE[cuoiQ] = j;
     chuaxet[j] = false;
    }
   }
  }
 }

 public BFSAlgorithm() {
  init();
  for (int i = 1; i <= n; i++) {
   chuaxet[i] = true;
  }
  System.out.print("\n");
  for (int i = 1; i <= n; i++)
   if (chuaxet[i]) {
    BFS(i);
   }
 }

 public static void main(String[] args) {
  new BFSAlgorithm();
 }
}

[Thuật toán] Tìm kiếm theo chiều sâu DFS.

Để xem lý thuyết đồ thị với các định nghĩa về đường đi, chu trình, đồ thị liên thông bạn có thể xem ở đây.
Lý thuyết thuật toán tìm kiếm theo chiều rộng bạn có thể xem ở đây.
Tư tưởng cơ bản của thuật toán tìm kiếm theo chiều sâu là bắt đầu tại một đỉnh v0 nào đó, chọn một đỉnh u bất kỳ kề với v0 và lấy nó làm đỉnh duyệt tiếp theo. Cách duyệt tiếp theo được thực hiện tương tự như đối với đỉnh v0 với đỉnh bắt đầu là u.
Để kiểm tra việc duyệt mỗi đỉnh đúng một lần, chúng ta sử dụng một mảng chuaxet[] gồm n phần tử (tương ứng với n đỉnh), nếu đỉnh thứ i đã được duyệt, phần tử tương ứng trong mảng chuaxet[] có giá trị FALSE. Ngược lại, nếu đỉnh chưa được duyệt, phần tử tương ứng trong mảng có giá trị TRUE. Thuật toán có thể được mô tả bằng thủ tục đệ qui DFS () trong đó: chuaxet - là mảng các giá trị logic được thiết lập giá trị TRUE.

void DFS( int v){ 
 Thăm_Đỉnh(v);
 chuaxet[v]:= FALSE; 
 for ( u ∈ke(v) ) { 
  if (chuaxet[u] ) DFS(u); 
 } 
}

Thủ tục DFS() sẽ thăm tất cả các đỉnh cùng thành phần liên thông với mỗi đỉnh đúng một lần. Để đảm bảo duyệt tất cả các đỉnh của đồ thị (có thể có nhiều thành phần liên thông), chúng ta chỉ cần thực hiện duyệt như sau:

for (i=1; i≤n ; i++) 
 chuaxet[i]:= TRUE; /* thiết lập giá trị ban đầu cho mảng chuaxet[]*/
for (i=1; i≤n ; i++) 
 if (chuaxet[i] ) 
  DFS( i); 

Đồ thị - Tìm kiếm theo chiều sâu DFS

STT	Đỉnh bắt đầu duyệt	Các đỉnh đã duyệt	Các đỉnh chưa duyệt
1	DFS(1)	1	2,3,4,5,6,7,8,9,10,11,12,13
2	DFS(2)	1,2	3,4,5,6,7,8,9,10,11,12,13
3	DFS(4)	1,2,4	3,5,6,7,8,9,10,11,12,13
4	DFS(3)	1,2,4,3	5,6,7,8,9,10,11,12,13
5	DFS(6)	1,2,4,3,6	5,7,8,9,10,11,12,13
6	DFS(7)	1,2,4,3,6,7	5,8,9,10,11,12,13
7	DFS(8)	1,2,4,3,6,7,8	5,9,10,11,12,13
8	DFS(10)	1,2,4,3,6,7,8,10	5,9,11,12,13
9	DFS(10)	1,2,4,3,6,7,8,10,5	9,11,12,13
10	DFS(9)	1,2,4,3,6,7,8,10,5,9	11,12,13
11	DFS(13)	1,2,4,3,6,7,8,10,5,9,13	11,12
12	DFS(11)	1,2,4,3,6,7,8,10,5,9,13,11	12
13	DFS(12)	1,2,4,3,6,7,8,10,5,9,13,11,12	Ѳ

Kết quả duyệt: 1, 2, 4, 3, 6, 7, 8, 10, 5, 9, 13, 11, 12
Ma trận liền kề được tải về tại đây.
Chương trình cài đặt bằng C/C++.

#include<iostream>
#include<conio.h>
using namespace std;
#define MAX  100 
#define TRUE 1 
#define FALSE 0 
int G[MAX][MAX], n, chuaxet[MAX]; 
void Init(){ 
 freopen("DFS.IN", "r", stdin); 
 cin>>n; 
 cout<<"So dinh cua ma tran n = "<<n<<endl;
 //nhap ma tran lien ke.
 for(int i=1; i<=n;i++){ 
  for(int j=1; j<=n;j++){ 
   cin>>G[i][j]; 
  } 
 } 
} 
/* Depth First Search */
void DFS(int G[][MAX], int n, int v, int chuaxet[]){ 
 cout<<"Duyet dinh : "<<v<<endl;
 int u; 
 chuaxet[v]=FALSE; 
 for(u=1; u<=n; u++){ 
  if(G[v][u]==1 && chuaxet[u]) 
   DFS(G,n, u, chuaxet); 
 } 
} 
void main(void){ 
 Init(); 
 for(int i=1; i<=n; i++) 
  chuaxet[i]=TRUE; 
 for(int i=1; i<=n;i++) 
  if(chuaxet[i]) 
   DFS( G,n, i, chuaxet); 
 _getch(); 
}

Chương trình cài đặt bằng Java.

package simplecodecjava.blogspot.com;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;

public class DFSAlgorithm {
 static final int MAX = 100;
 int G[][] = new int[MAX][MAX];// matran kề.
 int n = 0; // số dỉnh của đồ thị
 boolean chuaxet[] = new boolean[MAX];// mảng đánh dấu đỉnh đã được thăm.
 void Init() {
  File file = new File(getClass().getResource("DFS.IN").getPath());
  BufferedReader reader = null;
  try {
   reader = new BufferedReader(new FileReader(file));
   n = Integer.parseInt(reader.readLine());
   for (int i = 1; i <= n; i++) {
    String[] aLineOfMatrix = reader.readLine().split("\\s+");
    for (int j = 1; j <= n; j++) {
     G[i][j] = Integer.parseInt(aLineOfMatrix[j -1]);// index của J bắt đầu từ 0.
    }
   }
  }catch(FileNotFoundException e){
   e.printStackTrace();
  } catch (IOException e) {
   e.printStackTrace();
  } 
  finally {
   if (reader != null)
    try {
     reader.close();
    } catch (IOException e) {
     e.printStackTrace();
    }
  }
 }

 void DFS(int v) {
  int u;
  System.out.print(v + " ");
  chuaxet[v] = false;
  for (u = 1; u <= n; u++) {
   if (G[v][u] == 1 && chuaxet[u])
    DFS(u);
  }
 }

 public DFSAlgorithm() {
  Init();
  for (int i = 1; i <= n; i++){
   chuaxet[i] = true;
  }
  System.out.print("\n");
  for (int i = 1; i <= n; i++)
   if (chuaxet[i]){
    DFS(i);
   }
 }

 public static void main(String[] args) {
  System.out.println("DFS");
  new DFSAlgorithm();
 }
}