刘凡
3282579ec1
first commit
|
2 年 前 | |
|---|---|---|
| .. | ||
| README.md | 2 年 前 | |
| dfs_visual.py | 2 年 前 | |
| input.txt | 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-
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-
Complexity
Time: 0(m+n)
where m - number of edges
n - number of nodes