function dad = pfs(G)
%
% A = pfs(G)
% Do a priority first search of the graph, starting at node 1.
% Return the search tree.
% See Sedgewick, "Algorithms", Addison-Wesley. (1988) p466.

% dad(k) is the parent of k in the spanning tree.
% val(k) is negative if k is on the fringe (in the queue),
%  positive if processed (the value is the weight of the edge between k and dad(k))
%  and equal to the sentinel -unseen if not yet touched.

n = length(G);
unseen = 10000;
val = ones(1,n)*-unseen;
dad = zeros(1,n);
minval = unseen+1;
argmin = 1;

done = 0;

while ~done
  k = argmin;
  val(k) = -val(k);
  minval = unseen+1;
  if val(k) == unseen, val(k) = 0; end
  for t=1:n
    priority = G(k,t);
    if val(t) < 0
      if (G(k,t) ~= 0) & (val(t) < -priority)
	val(t) = -priority;
	dad(t) = k;
      end
      if -val(t) < minval
	minval = -val(t);
	argmin = t;
      end
    end
  end
  if minval == unseen+1, done = 1; end
end
