ผลต่างระหว่างรุ่นของ "Icpc-train-2012/graphs"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 3 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 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 ===
 
=== DFS ===
แถว 88: แถว 112:
 
System.out.println("" + v);
 
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);
 
}
 
}
 
 

รุ่นแก้ไขปัจจุบันเมื่อ 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();
	}
}
ดึงข้อมูลจาก "http://158.108.32.49/wiki/index.php?title=Icpc-train-2012/graphs&oldid=35830"