Icpc-train-2012/graphs

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

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