Find all the countries I can visit by just crossing direct borders

Question

I was helping on this question. There you have a table border to indicate countryA and countryB have a common border. And want to know what country you can reach starting from country S Sweden.

I did my recursion and works ok. But I feel I cheat a little bit. Taking advantage the number of countries are limited put a break on 300. But in a different problem where I don't know the upper limit won't be able to do the same.

How I optimize my query so recursion doesn't travel the same path again?

SQL Fiddle Demo

WITH RECURSIVE travel(r_level, country) AS (
    select distinct 1 as r_level,
                    CASE WHEN country1 = 'S' THEN country2
                         ELSE country1          
                    END as country
    from borders 
    where country1 = 'S' 
       or country2 = 'S'    
    UNION 
    select distinct t.r_level + 1 as r_level,
                    CASE WHEN b.country1 = t.country THEN b.country2
                         ELSE b.country1
                    END as country           
    from borders b
    join travel  t
      ON (b.country1 = t.country OR b.country2 = t.country)
     AND (b.country1 <> 'S' AND b.country2 <> 'S')
    WHERE t.r_level < 300
)
SELECT DISTINCT country
FROM travel

I can't use subquery based on the same recursive table:

AND (    b.country1 NOT IN (SELECT country FROM Travel)
     AND b.country2 NOT IN (SELECT country FROM Travel)
    )

Answer 1

You don't need to artificially limit number of iterations, according to PG manual using UNION without ALL is enough:

Recursive Query Evaluation

1. Evaluate the non-recursive term. For UNION (but not UNION ALL), discard duplicate rows. Include all remaining rows in the result of the recursive query, and also place them in a temporary working table.

2. So long as the working table is not empty, repeat these steps:

   a) Evaluate the recursive term, substituting the current contents of the working table for the recursive self-reference. For UNION (but not UNION ALL), discard duplicate rows and rows that duplicate any previous result row. Include all remaining rows in the result of the recursive query, and also place them in a temporary intermediate table.

   b) Replace the contents of the working table with the contents of the intermediate table, then empty the intermediate table.

with recursive travel(country) as (
  select 'S'
  union
  select unnest(array[country1, country2]::text[])
    from travel
      join borders on (country = any(array[country1, country2]))
)
select country from travel where country <> 'S';

Btw, the problem is related to calculating transitive closure on a graph.