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

Views:34   Downloads:1


Cui-xia XU

Index Terms

Spanning tree;bridge;edge-connected graph;DFS (depth-first search);back edge


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.


[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.