Icpc-train-2012/graphs
เนื้อหา
การค้นหาในกราฟ
Graph search
procedure Search(G,s) 1. SEEN <- {s} 2. EXPLORED <- {} 3. while SEEN != EXPLORED 4. pick u from SEEN - EXPLORED 5. for each edge (u,v) do 6. if v not in SEEN 7. add v to SEEN 5. add u to EXPLORED
Breadth-First Search
procedure BFS(G,s) 1. Q.init; Q.add(s) 1a. level[s] <- 0 2. while not Q.empty 3. u <- Q.extract 4. for each edge (u,v) do 5. if not seen[v] 6. Q.add(v) 6a. level[v] <- level[u]+1 7. seen[v] <- true 8. visited[u] <- true
DFS
procedure DFS(u) 1. visited[u] <- true 2. for each edge (u,v) do 3. if not visited[v] then 4. DFS(v)
โจทย์ตัวอย่างการค้นหาในกราฟ
DFS: รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ DFS โดยเริ่มการค้นหาที่โหนด 1
BFS: รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ BFS โดยเริ่มการค้นหาที่โหนด 1
Input:
- บรรทัดแรกระบุจำนวนเต็มสองจำนวน n และ m (1 <= n <= 1000; 1 <= m <= 10,000)
- จากนั้นอีก m บรรทัด ระบุเส้นเชื่อม m เส้น แต่ละบรรทัดระบุจำนวนเต็มสองจำนวน a และ b (1 <= a <= n; 1 <= b <= n) เพื่อระบุว่ามีเส้นเชื่อมระหว่างโหนด a และ b
Output:
พิมพ์ลำดับของโหนดที่ DFS (หรือ BFS) เข้าไปทำงาน
การอ่านและจัดเก็บกราฟ
C++
#include <vector> #include <cstdio> using namespace std; #define MAX_N 10000 int n,m; typedef vector<int> vi; vi adj[MAX_N]; void read_input() { scanf("%d %d",&n,&m); for(int i=0; i<m; i++) { int u,v; scanf("%d %d",&u,&v); u--; v--; adj[u].push_back(v); adj[v].push_back(u); } }
Java
import java.util.ArrayList; import java.util.Scanner; class Main { int n; int m; ArrayList<ArrayList<Integer>> adj; void readGraph(Scanner sc) { n = sc.nextInt(); m = sc.nextInt(); adj = new ArrayList<ArrayList<Integer>>(); for(int i=0; i<n; i++) adj.add(new ArrayList<Integer>()); for(int i=0; i<m; i++) { int u = sc.nextInt(); int v = sc.nextInt(); u--; v--; adj.get(u).add(v); } } void run() { Scanner sc = new Scanner(System.in); readGraph(sc); for(int v : adj.get(0)) { System.out.println("" + v); } } public static void main(String [] argv) { Main m = new Main(); m.run(); } }