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,*

1. Weifang University Weifang261061, China

* Corresponding author.

DOI: https://doi.org/10.5815/ijeme.2012.01.02

Received: 12 Oct. 2011 / Revised: 17 Nov. 2011 / Accepted: 23 Dec. 2011 / Published: 29 Jan. 2012

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.