c++数据结构图的遍历

C++数据结构图的遍历有两种方法：深度优先遍历和广度优先遍历。

深度优先遍历（DFS）是一种用于遍历或搜索树或图的算法。在这种搜索方法中，从根结点开始，尽可能深地搜索每个分支，直到找到目标值或达到叶子结点。然后回溯到前一个结点，继续搜索下一个分支。具体实现可以使用递归或栈来实现。

以下是使用邻接矩阵和邻接表两种数据结构实现深度优先遍历的C++代码：

邻接矩阵实现深度优先遍历：

const int Max_Num = 100;
bool visited[Max_Num];//全局变量

void Adj_matrix::DFS(int x)//深度优先遍历递归
{
    cout << vexs[x] << endl;
    visited[x] = true;
    for (int i = 0; i < vexnum; i++)//遍历邻接矩阵中X的行
    {
        if (arcs[x][i] == 1 && !visited[x])//邻接矩阵中的值为1，且节点未被访问
        {
            DFS(i);//递归
        }
    }
}

void Adj_matrix::DFSTraverse()//深度优先遍历
{
    for (int i = 0; i < vexnum; i++)
        visited[i] = false;//把数组初始化
    int s;
    cin >> s;//输入起始点
    DFS(s);//执行递归算法
}

邻接表实现深度优先遍历：

const int Max_Num = 100;
bool visited[Max_Num];//全局变量

void ADList::DFS(int x)//深度优先遍历的递归调用
{
    cout << adlist[x].data;//输出节点信息
    visited[x] = true;//把节点设置为已访问
    table_node* p = adlist[x].firstarc;//用一个指针指向该顶点的弧链表
    while (p != NULL)//如果该节点的弧链表不为空
    {
        if (!visited[p->adjvex])//该弧顶点如果未访问的话
            DFS(p->adjvex);//遍历该顶点
        p = p->nextarc;//指向下一个链表节点
    }
}

void ADList::DFSTraverse()//深度优先遍历
{
    for (int i = 0; i < vexnum; i++)
        visited[i] = false;
    int s;
    cin >> s;//输入起始点
    DFS(s);//执行递归算法
}

广度优先遍历（BFS）是一种用于遍历或搜索树或图的算法。在这种搜索方法中，从根结点开始，按照层次顺序逐层搜索每个分支，直到找到目标值或遍历完整个图。具体实现可以使用队列来实现。

以下是使用邻接表数据结构实现广度优先遍历的C++代码：

const int Max_Num = 100;
bool visited[Max_Num];//全局变量

void ADList::BFSTraverse()//广度优先遍历
{
    for (int i = 0; i < vexnum; i++)
        visited[i] = false;
    int s;
    cin >> s;//输入起始点
    queue<int> q;
    q.push(s);//把起始点入队
    visited[s] = true;//把起始点设置为已访问
    while (!q.empty())//队列不为空
    {
        int x = q.front();//取出队首元素
        q.pop();//弹出队首元素
        cout << adlist[x].data;//输出节点信息
        table_node* p = adlist[x].firstarc;//用一个指针指向该顶点的弧链表
        while (p != NULL)//如果该节点的弧链表不为空
        {
            if (!visited[p->adjvex])//该弧顶点如果未访问的话
            {
                q.push(p->adjvex);//把该顶点入队
                visited[p->adjvex] = true;//把该顶点设置为已访问
            }
            p = p->nextarc;//指向下一个链表节点
        }
    }
}