Perform the Depth First Search algorithm from a source node on a topology in respect the node index metric.
[V,P] = NL_R_DFS(G,I)
Graph.
Source node.
Vector that gathers the chronological order how network nodes are visited.
Vector composed by the predecessor of each node in order to reach the source node.
NL_R_DFS constructs the DFS tree inside the graph G in respect with the source node I defined as the root (WIKIPEDIA). This graph search algorithm begins at the root node and explores all the neighboring nodes. Then for each of those nodes with the smallest index, unexplored neighbor nodes are explored, and so on. The search is done in depth. The vector V gathers the chronological order how network nodes are visited. P provides the predecessor of each node in order to reach the source node.
void DFS(Graph G, int v) { // DFS PreVisit(G, v); // action on the vertex v G.setMark(v, VISITED); // v is set as visited for (Edge w = G.first(v); G.isEdge(w); w = G.next(w)) if (G.getMark(G.v2(w)) == UNVISITED) DFS(G, G.v2(w)); PostVisit(G, v); // action on the vertex v } | ![]() | ![]() |
n=150;//network size L=1000;//network square area side dmax=100;//Locality radius [g]=NL_T_LocalityConnex(n,L,dmax);//generation of a topology in respect with the Locality method i=NL_F_RandInt1n(length(g.node_x));//selection of the source node [v,pred]=NL_R_DFS(g,i);//application of NL_R_DFS i v(1:10)//first ten values pred(1:10)//first ten values | ![]() | ![]() |