Optimized Proposed Algorithm for Graph Traversal
|
10.5120/18234-9217 |
Ankit Malhotra, Dipit Malhotra and Saksham Kashyap. Article: Optimized Proposed Algorithm for Graph Traversal. International Journal of Computer Applications 104(9):38-43, October 2014. Full text available. BibTeX
@article{key:article,
author = {Ankit Malhotra and Dipit Malhotra and Saksham Kashyap},
title = {Article: Optimized Proposed Algorithm for Graph Traversal},
journal = {International Journal of Computer Applications},
year = {2014},
volume = {104},
number = {9},
pages = {38-43},
month = {October},
note = {Full text available}
}
Abstract
This paper includes a flexible algorithm for traversing a directed and an undirected graph. Graph traversal is defined as the problem of visiting all the nodes in a graph in a particular manner, updating and/or checking their values along the way. The Breadth first search along with Depth first search are the most widely used algorithms for traversing a graph. In this article, an algorithm is proposed for traversing a graph taking in consideration the vertex with the maximum outgoing edges. Instead of beginning from the root node and then gaining access to visit the neighbors of the currently visited node, the algorithms looks for the vertex with the maximum edges and then continue traversing all the neighboring vertices of that vertex. This paper presents an algorithm to traverse an undirected or a directed graph and calculates the time and space complexity of the algorithm. The work proposed here intends to find a new algorithm that can be universally applied to all types of graphs
References
- Applications of graph theory in communication networks by Suman Deswal.
- Shortest path algorithm in GIS network analysis based on Clifford algebra by Jiyi Zhang, Weichang, Mei, Wen Luo, Linwang Yuan.
- Graph theory and applications by Paul Van Dooren
- Applications of graph theory by S. G. Shirinivas S. Vetrivel , Dr. N. M. Elango
- BFS by Allison June Barlow Chaney,Princeton. edu.
- DFS by Allison June Barlow Chaney.
- Introduction to Algorithms(2nd ed) by Cormen Thomas H, Leiserson , Charles E,Clifford(2001)
- Breadth First Search WIKIPEDIA
- CMU-Data Structures Lessons 5
- Graphs :Representation and Exploration by Julian Mestre
- Y. T. Yu, M. F. Lau, "A comparison of MC/DC, MUMCUT and several other coverage criteria for logical decisions", Journal of Systems and Software, 2005, in press.
- Spector, A. Z. 1989. Achieving application requirements. In Distributed Systems, S. Mullender