International Journal of Education and Management Engineering (IJEME)
IJEME Vol. 2, No. 1, 8 Jan. 2012
Cover page and Table of Contents: PDF (size: 80KB)
Application of DFS in the Study of Edge-connected Graph
Full Text (PDF, 80KB), PP.9-15
Views: 0 Downloads: 0
Author(s)
Cui-xia XU
1,*
Index Terms
Spanning tree, bridge, edge-connected graph, DFS (depth-first search), back edge
Abstract
In this paper a simple method is proposed to determine whether a graph is edge-connected. This method may calculate the minimum pre-order number of each vertex by back edge for the depth-first search spanning tree, and then find out the bridges in the graph. Finally, it may determine whether the graph is edge-connected. The best nature of method is to understand and hold the algorithm easily. It can help teaching improvement and practice application. It is also worth popularization.
Cite This Paper
Cui-xia XU,"Application of DFS in the Study of Edge-connected Graph", IJEME, vol.2, no.1, pp.9-15, 2012. DOI: 10.5815/ijeme.2012.01.02
Reference
[1] [U.S.] Robert Sedgewick. “Algorithms in C(Third Edition)”. Beijing: POSTS & TELECOMMUNICATIONS PRESS, 2004. (in chinese)
[2] Sara baase, Allen Van Gelder.“Computer Algorithms:Introduction to Design and Analysis(Third Edition)”. Beijing: Higher Education Press, 2001.
[3] [Saudi Arabia] M.H. Alsuwaiyel. “Algorithms Design Techniques and Analysis”. Beijing: Electronic Industry Press, 2004.(in chinese)
[4] Bernard Kolman, Robert C. Busby, Sharon Cutler Ross.“Discrete Mathematical Structures”. Beijing: Higher Education Press, 2008.