The Ship
A generation ship carrying one million people for an indefinite period will need to carry or generate a minimum of 550,000,000 litres of $O_2$ per day. Mixed to match Earth atmosphere ratios, in which $O_2$ accounts for 21% of the air, that's a minimal atmosphere capacity of 2,620,000,000 litres.
Assuming a classic rotating cylinder ship, that is a cylinder roughly 3,000 km long and 1,050 km across. Such a ship would have an internal surface area of 11,700,000 $km^2$, so something between Canada and Antarctica in size. Again, that is the bare minimum – meaning zero redundancy, zero waste, zero loss – to support one million air-breathing adults.
The Interstellar Medium
99% of the interstellar medium by mass is gas, of which 70% is hydrogen and 28% helium. Oxygen makes up trace amounts – less than 1,000 molecules per $cm^3$ in the best case scenario; not enough to harvest en route to make a difference. Barring fusion of those H and He molecules, you're going to have to bring all the oxygen you need with you, in one form or another.
The Oxygen Cycle
Fortunately, people – and plants – also need water to live, and water has oxygen.
To keep these people breathing you'll have to simulate or approximate the natural oxygen cycle found on Earth:

Specifically the Hydrogen and Oxygen steps. The only inputs this system needs are photosynthesis-permitting light, which can be achieved artificially, and topping up any lost hydrogen.
Grow It
From the same Wikipedia article linked above, the carbon cycle accounts for 99% of the oxygen, stored away in rock; your ship will need as much oxygen produced and cycling as possible, and cannot justify the space and mass a crust-substitute quantity of rock and minerals would require, or the time, so this step will need to be bypassed.
The "light-dependent reaction" in the diagram above is photosynthesis – plants combining $6CO_2$ (carbon dioxide) with $6H_2O$ (water) and light to produce $C_6H_{12}O_6$ (sugar – glucose) and $6O_2$ (oxygen).
On Earth the Amazon produces more than 20% of total oxygen from photosynthesis – 20% of 165,000,000,000,000 litres; see table 2 in link above – in an area roughly 5,500,000 $km^2$. That's tens of thousands times more oxygen than you need, produced in an area half the size of the cylinder described.
(There is another way to produce oxygen called photolysis – UV light breaking $H_2O$ into its constituent parts; $H_2$ to be absorbed/collected, free oxygen combining to $O_2$ – but on Earth it doesn't produce even 0.001% of the $O_2$ we breathe, so we probably shouldn't factor it into this situation.)