数据结构图 广度深度优先搜索

图的深度优先搜索（DFS）和广度优先搜索（BFS）是图的两种主要遍历算法。在数据结构图中，可以使用邻接矩阵或邻接表来存储图的结构。

深度优先搜索（DFS）是一种用于遍历或搜索图的算法。它从起始顶点开始，沿着一条路径走到底，然后回溯并探索其他路径。DFS使用栈来保存待访问的顶点，通过不断地将相邻的未访问顶点压入栈中，并在访问过后将其弹出，直到栈为空为止。

广度优先搜索（BFS）是一种用于遍历或搜索图的算法。它从起始顶点开始，逐层地访问其所有相邻的顶点，然后再访问这些相邻顶点的相邻顶点。BFS使用队列来保存待访问的顶点，通过不断地将相邻的未访问顶点加入队列，并在访问过后将其出队，直到队列为空为止。

以下是一个示例代码实现：

#define MaxVertexNum 100
typedef struct ArcNode{
    struct ArcNode *next;
    int adjVertex;
}ArcNode;

typedef struct VNode{
    ArcNode *next;
    elemtype data;
}VNode, adjList = false;
    }
  
    Stack S;
    InitStack(S);
    int i, j;
  
    // 访问v，并将v压入栈中
    visited[v = true;
    push(S, v);
  
    // 循环直到栈空
    while(!IsEmpty(S)){
        // 弹出栈顶元素
        pop(S, i);
      
        // 访问i所有的邻接结点
        for (j = FirstNeighbor(G, i); j >= 0; j = NextNeighbor(G, i, j)){
            // 将j压入栈中
            if (!visited[j]) {
                visited[j = true;
                push(S, j);
            }
        }
    }
}

void BFS(ALGraph G, int v){
    // 初始化visited数组
    for (int i = 0; i < MaxVertexNum; i++){
        visited[i = false;
    }
  
    Queue Q;
    InitQueue(Q);
    int i, j;
  
    // 访问v，并将v加入队列中
    visited[v = true;
    enqueue(Q, v);
  
    // 循环直到队列为空
    while(!IsEmpty(Q)){
        // 出队列
        dequeue(Q, i);
      
        // 访问i所有的邻接结点
        for (j = FirstNeighbor(G, i); j >= 0; j = NextNeighbor(G, i, j)){
            // 将j加入队列中
            if (!visited[j]) {
                visited[j = true;
                enqueue(Q, j);
            }
        }
    }
}

通过调用DFS函数可以进行图的深度优先搜索，调用BFS函数可以进行图的广度优先搜索。这样可以遍历或搜索整个数据结构图的顶点。