ผลต่างระหว่างรุ่นของ "Icpc-train-2012/graphs"
ไปยังการนำทาง
ไปยังการค้นหา
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
(ไม่แสดง 9 รุ่นระหว่างกลางโดยผู้ใช้ 2 คน) | |||
แถว 1: | แถว 1: | ||
− | == โจทย์ตัวอย่างการค้นหาในกราฟ == | + | == การค้นหาในกราฟ == |
+ | === 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 | ||
+ | 1a. Q.add(s); seen[s] <- true | ||
+ | 1b. 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); seen[v] <- true | ||
+ | 6a. level[v] <- level[u]+1 | ||
+ | |||
+ | === 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 | '''DFS:''' รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ DFS โดยเริ่มการค้นหาที่โหนด 1 | ||
แถว 8: | แถว 42: | ||
* บรรทัดแรกระบุจำนวนเต็มสองจำนวน n และ m (1 <= n <= 1000; 1 <= m <= 10,000) | * บรรทัดแรกระบุจำนวนเต็มสองจำนวน n และ m (1 <= n <= 1000; 1 <= m <= 10,000) | ||
− | * จากนั้นอีก m บรรทัด | + | * จากนั้นอีก m บรรทัด ระบุเส้นเชื่อม m เส้น แต่ละบรรทัดระบุจำนวนเต็มสองจำนวน a และ b (1 <= a <= n; 1 <= b <= n) เพื่อระบุว่ามีเส้นเชื่อมระหว่างโหนด a และ b |
+ | |||
+ | '''Output:''' | ||
+ | |||
+ | พิมพ์ลำดับของโหนดที่ DFS (หรือ BFS) เข้าไปทำงาน | ||
+ | |||
+ | === การอ่านและจัดเก็บกราฟ === | ||
+ | |||
+ | '''C++''' | ||
+ | |||
+ | <pre> | ||
+ | #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); | ||
+ | } | ||
+ | } | ||
+ | </pre> | ||
+ | |||
+ | '''Java''' | ||
+ | |||
+ | <pre> | ||
+ | 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(); | ||
+ | } | ||
+ | } | ||
+ | </pre> | ||
+ | |||
+ | === โค้ดอื่น ๆ === | ||
+ | |||
+ | '''BFS ใน Java''' | ||
+ | |||
+ | <pre> | ||
+ | import java.util.ArrayList; | ||
+ | import java.util.LinkedList; | ||
+ | import java.util.Scanner; | ||
+ | |||
+ | class Main { | ||
+ | int n; | ||
+ | int m; | ||
+ | ArrayList<ArrayList<Integer>> adj; | ||
+ | |||
+ | void readInput(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); | ||
+ | adj.get(v).add(u); | ||
+ | } | ||
+ | } | ||
+ | |||
+ | void BFS(int s) { | ||
+ | LinkedList<Integer> q = new LinkedList<Integer>(); | ||
+ | boolean [] seen = new boolean[n]; | ||
+ | |||
+ | q.add(s); | ||
+ | seen[s] = true; | ||
+ | while(!q.isEmpty()) { | ||
+ | int u = q.removeFirst(); | ||
+ | |||
+ | System.out.println("" + (u+1)); | ||
+ | |||
+ | for(int v : adj.get(u)) | ||
+ | if(!seen[v]){ | ||
+ | q.addLast(v); | ||
+ | seen[v] = true; | ||
+ | } | ||
+ | } | ||
+ | } | ||
+ | |||
+ | void run() { | ||
+ | Scanner sc = new Scanner(System.in); | ||
+ | |||
+ | readInput(sc); | ||
+ | BFS(0); | ||
+ | } | ||
+ | |||
+ | public static void main(String [] argv) { | ||
+ | Main m = new Main(); | ||
+ | m.run(); | ||
+ | } | ||
+ | } | ||
+ | </pre> |
รุ่นแก้ไขปัจจุบันเมื่อ 05:02, 8 กรกฎาคม 2555
เนื้อหา
การค้นหาในกราฟ
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 1a. Q.add(s); seen[s] <- true 1b. 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); seen[v] <- true 6a. level[v] <- level[u]+1
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(); } }
โค้ดอื่น ๆ
BFS ใน Java
import java.util.ArrayList; import java.util.LinkedList; import java.util.Scanner; class Main { int n; int m; ArrayList<ArrayList<Integer>> adj; void readInput(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); adj.get(v).add(u); } } void BFS(int s) { LinkedList<Integer> q = new LinkedList<Integer>(); boolean [] seen = new boolean[n]; q.add(s); seen[s] = true; while(!q.isEmpty()) { int u = q.removeFirst(); System.out.println("" + (u+1)); for(int v : adj.get(u)) if(!seen[v]){ q.addLast(v); seen[v] = true; } } } void run() { Scanner sc = new Scanner(System.in); readInput(sc); BFS(0); } public static void main(String [] argv) { Main m = new Main(); m.run(); } }