Application of DFS in the Study of Edge-connected Graph
Author: Cui-xia XU
Journal: International Journal of Education and Management Engineering(IJEME) @ijeme
Article in issue: 1 vol.2, 2012.
Free access
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.
Spanning tree, bridge, edge-connected graph, DFS (depth-first search), back edge
Short address: https://sciup.org/15013641
IDR: 15013641
References Application of DFS in the Study of Edge-connected Graph
- [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.
