function [d, pre, post, cycle, f, pred] = dfs(adj_mat, start, directed)
% 标准的深度优先搜索算法,可实现节点遍历、产生随机路由、检测图中是否有回路等功能,详细情况请看原英文注释
% 我在此程序中添加了随机性,即遇到分叉时,随机选下一个节点,成为随机深度优先搜索算法
% DFS Perform a depth-first search of the graph starting from 'start'.
% [d, pre, post, cycle, f, pred] = dfs(adj_mat, start, directed)
%
% Input:
% adj_mat(i,j)=1 iff i is connected to j.
% start is the root vertex of the dfs tree; if [], all nodes are searched
% directed = 1 if the graph is directed
%
% Output:
% d(i) is the time at which node i is first discovered.
% pre is a list of the nodes in the order in which they are first encountered (opened).
% post is a list of the nodes in the order in which they are last encountered (closed).
% 'cycle' is true iff a (directed) cycle is found.
% f(i) is the time at which node i is finished.
% pred(i) is the predecessor of i in the dfs tree.
%
% If the graph is a tree, preorder is parents before children,
% and postorder is children before parents.
% For a DAG, topological order = reverse(postorder).
%
% See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478.
adj_mat=triu(adj_mat);%考虑兼容性,只取上三角部分
n = length(adj_mat);
global white gray black color
white = 0; gray = 1; black = 2;
color = white*ones(1,n);
global time_stamp
time_stamp = 0;
global d f
d = zeros(1,n);
f = zeros(1,n);
global pred
pred = zeros(1,n);
global cycle
cycle = 0;
global pre post
pre = [];
post = [];
if ~isempty(start)
dfs_visit(start, adj_mat, directed);
end
for u=1:n
if color(u)==white
dfs_visit(u, adj_mat, directed);
end
end
%%%%%%%%%%
- 1
- 2
- 3
- 4
前往页