Icpc-train-2012/graphs - ประวัติรุ่นแก้ไข

Jittat เมื่อ 05:02, 8 กรกฎาคม 2555

2012-07-08T05:02:00Z

2012-07-08T04:16:52Z

Breadth-First Search

2012-07-08T04:13:47Z

Graph search

2012-07-08T04:04:50Z

การค้นหาในกราฟ

2012-07-08T03:24:24Z

DFS

2012-07-08T02:40:20Z

การอ่านและจัดเก็บกราฟ

2012-07-08T02:36:20Z

2012-07-08T02:34:59Z

2012-07-07T18:07:37Z

2012-07-07T18:06:57Z

@@ แถว 112: / แถว 112: @@
 			System.out.println("" + v);
+		}
+	}

@@ แถว 15: / แถว 15: @@
    procedure BFS(G,s)
-.  Q.init;  Q.add(s)
+.  Q.init
-a. level[s] <- 0
+a. Q.add(s); seen[s] <- true
 .  while not Q.empty
 .    u <- Q.extract
 .    for each edge (u,v) do
 .      if not seen[v]
-.        Q.add(v)
+.        Q.add(v); seen[v] <- true
 a.       level[v] <- level[u]+1
 === DFS ===

@@ แถว 11: / แถว 11: @@
 .       add v to SEEN
 .   add u to EXPLORED
 === DFS ===

@@ แถว 7: / แถว 7: @@
 .  for each edge (u,v) do
 .    if not visited[v] then
-.      dfs(v)
+.      DFS(v)
 === โจทย์ตัวอย่างการค้นหาในกราฟ ===

@@ แถว 51: / แถว 51: @@
+   }
+}
 </pre>
 '''Java'''

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 18:07, 7 กรกฎาคม 2555
แถว 15:		แถว 15:

	พิมพ์ลำดับของโหนดที่ DFS (หรือ BFS) เข้าไปทำงาน		พิมพ์ลำดับของโหนดที่ DFS (หรือ BFS) เข้าไปทำงาน
		+
		+	=== การอ่านและจัดเก็บกราฟ ===
		+
		+	'''C++'''
		+
		+	'''Java'''

@@ แถว 1: / แถว 1: @@
-== โจทย์ตัวอย่างการค้นหาในกราฟ ==
+== การค้นหาในกราฟ ==
 '''DFS:''' รับกราฟที่มี n โหนด m เส้นเชื่อม มีหมายเลขตั้งแต่ 1 ถึง n จากนั้นพิมพ์โหนดในกราฟตามลำดับ DFS โดยเริ่มการค้นหาที่โหนด 1
@@ แถว 8: / แถว 10: @@
 * บรรทัดแรกระบุจำนวนเต็มสองจำนวน n และ m (1 <= n <= 1000; 1 <= m <= 10,000)
-* จากนั้นอีก m บรรทัด
+* จากนั้นอีก m บรรทัด ระบุเส้นเชื่อม m เส้น แต่ละบรรทัดระบุจำนวนเต็มสองจำนวน a และ b (1 <= a <= n; 1 <= b <= n) เพื่อระบุว่ามีเส้นเชื่อมระหว่างโหนด a และ b