刘凡 3282579ec1 first commit 2 سال پیش
..
README.md 3282579ec1 first commit 2 سال پیش
dfs_visual.py 3282579ec1 first commit 2 سال پیش
input.txt 3282579ec1 first commit 2 سال پیش

README.md

Visualisation of DFS traversal using networkx library

INPUT

Graph is first drawn from the weighted matrix input from the user. Input is taken from the file

input.txt

Sample input

 4
 0 5 0 5
 5 0 5 0
 0 5 0 5
 5 0 5 0
 0

First line contains the number of nodes,say n.(Nodes are numbered as 0,1,2,...(n-1) ) Followed by n*n weighted matrix. Disconnected egdes are represented by negative weight. Last line contains the source node.(i.e, the node from which the DFS should begin)

Visualization of the input graph- 1

DFS traversal

Recursive DFS is performed, resulting DFS forests are stored in a stack.

Visulization of DFS path

The stack is then used to mark the DFS traversed edges with a different colour(Here, Red. So, as to distinguish itself from the rest). Visualization of the result- 2

Complexity

Time: 0(m+n)
where m - number of edges
n - number of nodes