邻接矩阵存储图的深度优先遍历
邻接矩阵表示的无向图遍历实现。
#include
using namespace std;
#define MAX_SIZE 100//最大顶点数 。
#define MAX_INT 326564//表示极大值，即 ∞ 。
typedef char Elemtype_A;//定义顶点的数据类型为字符型 。
typedef int Elemtype_S;//定义边的权值为整型 。
/*深度优先遍历（DFS）
方法：
(1)在访问图中某一起始顶点 ν后，由 v出发，访问它的任一邻接顶点 w；
(2)再从 W,出发，访问与 w,邻接但还未被访问过的顶点 Mzi
(3)然后再从 Wz出发，进行类似的访问，..
(4)如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u为止。
(5)接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被
访问的邻接顶点。
如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的
访问；
如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中
所有顶点都被访问过为止。*/
//1.邻接矩阵的
2022-12-16 09:15:04
12KB
1
对任意给定的图（顶点数和边数自定义），建立它的邻接表输出，然后利用栈的五种基本运算（清空堆栈，压栈，弹出，取栈顶元素，判空栈）实现图的深度搜索遍历和广度优先搜素遍历算法
2021-12-28 21:31:27
102KB
1
通过键盘输入图的顶点，以及每一条边的两个顶点，从而建立无向图。实现无向图的深度优先遍历算法。要求以用户给定的结点为起始点，显示深度优先遍历次序。
2021-09-25 09:13:59
3KB
1
/*
* （有向）图的深度优先遍历算法模板
*/
package dsa;
public abstract class DFS extends GraphTraverse {
//变量
protected static int clock = 0;//遍历过程中使用的计时钟
//构造方法
public DFS(Graph g) { super(g); }
//深度优先遍历算法
protected Object traverse(Vertex v, Object info) {//从顶点v出发，做深度优先查找
if (UNDISCOVERED != v.getStatus()) return null;//跳过已访问过的顶点（针对非连通图）
v.setDStamp(clock++); v.setStatus(DISCOVERED); visit(v, info);//访问当前顶点
for (Iterator it = v.outEdges(); it.hasNext();) {//检查与顶点v
Edge e = (Edge)it.getNext();//通过边e = (v, u)
Vertex u = (Vertex)e.getVPosInV(1).getElem();//相联的每一顶点u
switch (u.getStatus()) {//根据u当前的不同状态，分别做相应处理
case UNDISCOVERED ://若u尚未被发现，则
e.setType(TREE);//e被归类为“树边”
traverse(u, info);//从u出发，继续做深度优先查找
break;
case DISCOVERED ://若u已经被发现，但对其访问尚未结束，则
e.setType(BACKWARD);//将e归类为“后向跨边”
break;
default ://VISITED，即对u的访问已经结束
if (u.getDStamp() < v.getDStamp())//若相对于v，u被发现得更早，则
e.setType(CROSS);//将e归类为“横跨边”
else//否则
e.setType(FORWARD);//将e归类为“前向跨边”
break;
}
}//至此，v的所有邻居都已访问结束，故
v.setFStamp(clock++); v.setStatus(VISITED);//将v标记为VISITED
return null;//然后回溯
}
}
2021-07-30 00:56:24
3KB
1