Cầu trong một đồ thị

Một cạnh trong đồ thị vô hướng được cho là cầu nối, nếu và chỉ khi loại bỏ nó, ngắt kết nối đồ thị hoặc tạo các thành phần khác nhau của đồ thị.

Theo cách tiếp cận thực tế, nếu một số cầu nối hiện diện trong mạng khi kết nối của các cầu nối bị hỏng, nó có thể phá vỡ toàn bộ mạng.

Đầu vào và Đầu ra

 Đầu vào:Ma trận kề của đồ thị. 0 1 1 1 01 0 1 0 01 1 0 0 01 0 0 0 10 0 0 1 0 Đầu ra:Cầu trong đồ thị đã cho:Cầu 3--4 Cầu 0--3  
 Thuật toán 
 
 bridgeFind (bắt đầu, truy cập, đĩa, thấp, chính) 
 

  Đầu vào -  Đỉnh bắt đầu, mảng được thăm để đánh dấu khi một nút được truy cập, đĩa sẽ lưu giữ thời gian khám phá của đỉnh và thấp sẽ chứa thông tin về các cây con. Đỉnh cha sẽ giữ đỉnh cha mẹ của đỉnh hiện tại. 
 

  Đầu ra -  in nếu tìm thấy bất kỳ cầu nối nào. 
 
 Begin time:=0 // giá trị của thời gian sẽ không được khởi tạo cho các lệnh gọi hàm tiếp theo đánh dấu bắt đầu như đã truy cập đĩa tập hợp [start]:=time + 1 và low [start]:=time + 1 time:=time + 1 cho tất cả đỉnh v trong đồ thị G, nếu có cạnh giữa (bắt đầu, v), sau đó nếu v được truy cập, thì cha [v]:=start bridgeFind (v, đã thăm, đĩa, thấp, mẹ) low [start]:=tối thiểu của low [start] và low [v] nếu low [v]> disk [start], sau đó hiển thị các cầu nối từ đầu đến v khác nếu v không phải là cha của start, sau đó là low [start] :=tối thiểu thấp [start] và đĩa [v] doneEnd 
 
 Ví dụ 
 
 #include  #define NODE 5 sử dụng không gian tên std; int graph [NODE] [NODE] ={{0, 1, 1, 1, 0}, {1, 0, 1, 0, 0}, { 1, 1, 0, 0, 0}, {1, 0, 0, 0, 1}, {0, 0, 0, 1, 0}}; int min (int a, int b) {return (a  disk [start]) cout <<"Bridge" < 
 Đầu ra 
 
 Cầu trong đồ thị đã cho:Cầu 3--4 Cầu 0--3