International Journal of Education and Management Engineering(IJEME)
ISSN: 2305-3623 (Print), ISSN: 2305-8463 (Online)
Published By: MECS Press
IJEME Vol.2, No.1, Jan. 2012
Application of DFS in the Study of Edge-connected Graph
Full Text (PDF, 80KB), PP.9-15
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.
[U.S.] Robert Sedgewick. “Algorithms in C(Third Edition)”. Beijing: POSTS & TELECOMMUNICATIONS PRESS, 2004. (in chinese)
Sara baase, Allen Van Gelder.“Computer Algorithms:Introduction to Design and Analysis(Third Edition)”. Beijing: Higher Education Press, 2001.
[Saudi Arabia] M.H. Alsuwaiyel. “Algorithms Design Techniques and Analysis”. Beijing: Electronic Industry Press, 2004.(in chinese)
Bernard Kolman, Robert C. Busby, Sharon Cutler Ross.“Discrete Mathematical Structures”. Beijing: Higher Education Press, 2008.