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  
 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();
	}
}