数据结构_图的遍历

深度优先搜索遍历

遍历思想

邻接矩阵上的遍历算法

void Map::DFS(int v)
{
    int w, i, k;
    visited[v] = true; // 标记已访问
    cout << v << " ";

    // 找出与v相连接的其他所有顶点，存放在AdjVex数组中
    int* AdjVex = new int[Vexnum]; // 存放连接的顶点编号
    for (i = 0; i < Vexnum; i++)
    {
        AdjVex[i] = -1;
    }

    // k是数组AdjVex的空位置下标，初始化为0表示数组AdjVex一开始没有数据
    k = 0;
    for (i = 0; i < Vexnum; i++)
    {
        // 如果顶点i与v连接
        if (Maxtrix[v][i] == 1)
        {
            AdjVex[k] = i;
            k++;
        }
    }

    i = 0;
    w = AdjVex[i];
    while (w != -1)
    {
        // 如果顶点w未访问
        if (visited[w] == false)
        {
            DFS(w);
        }
        i++;
        w = AdjVex[i];
    }
    delete[] AdjVex;
}

广度优先搜索遍历及其实现

实现

void Map::BFS(Graph G, int v)
{
    int w, u;
    queue<int> Q;
    visited[v] = true; // 访问第v个顶点
    cout << v << " ";  // 输出访问的顶点

    Q.push(v);
    while (!Q.empty())
    {
        u = Q.front();
        Q.pop();
        for (w = FirstAdjVex(G, u); w >= 0; w = NextAdjVex(G, u, w))
        {
            if (!visited[w])
            {
                cout << w << " ";
                visited[w] = true;
                Q.push(w);
            }
        }
    }
}

int Map::FirstAdjVex(Graph& G, int v)
{
    for (int i = 0; i < G.num; i++)
    {
        if (G.arcs[v][i] != 0)
        {
            return i;
        }
    }
    return -1;
}

int Map::NextAdjVex(Graph& G, int v, int w)
{
    for (int i = w + 1; i < G.num; i++)
    {
        if (G.arcs[v][i] != 0)
            return i;
    }
    return -1;
}