关于BFS和DFS的问题…

这是出现的问题，最后会有一个问号，以及顺序好像不太对

img


这是文件“Graph.txt”里的数据，放在D盘下


//下一行为图的标识行
Graph
//图的类型标识，此图为无向图
UDG
//顶点元素数据
1 2 3 4 5 6 7 8 9 10
//以下为边的数据，共24行数据，表示12条边
1 2
1 8
2 1
2 3
2 4
3 2
4 2
4 5
4 6
4 7
5 4
5 6
6 5
6 4
6 7
7 4
7 6
8 1
8 9
8 10
9 8
9 10
10 8
10 9

这是代码


#include<iostream>
using namespace std;
#include"Graph.h"
int main() {
    Graph G;
    char filename[] = "D:\\Graph.txt";
    CreateGraphFromFile(filename, G);
    menu();
    int i,x;
    cout << "请输入要执行的操作：";
    cin >> i;
    while (i)
    {
        switch (i)
        {
        case 1:
            cout << "该图的边数为：" << G.ArcNum << endl;
            break;
        case 2:
            GraphIsTree(G);
            break;
        case 3:
            cout << "请输入访问图的起始顶点编号：" << endl;
            cin >> x;
            cout << "深度优先遍历序列为：" << endl;
            DFSTraverse(G, x);
            cout << endl;
            break;
        case 4:
            cout << "请输入访问图的起始顶点编号：" << endl;
            cin >> x;
            cout << "广度优先遍历序列为：" << endl;
            BFSTraverse(G, x);
            cout << endl;
            break;
        }
        system("pause");
        cout << "请输入要执行的操作：";
        cin >> i;
    }
    return 0;
}


#pragma once
#include<iostream>
#include<queue>
using namespace std;
#define INF 999
#define MaxVerNum 99
typedef char elementType;
typedef int cellType;
typedef enum { UDG, UDN, DG, DN }GraphKind;
typedef struct GraphAdjMaxtrix {
    elementType Data[MaxVerNum];
    cellType AdjMatrix[MaxVerNum][MaxVerNum];
    int VerNum;
    int ArcNum;
    GraphKind gKind;
}Graph;
bool visited[MaxVerNum + 1];  //全局数组，标记顶点是否已经访问，visited[0]单元不用
int CreateGraphFromFile(char fileName[], Graph &G);
void menu();
void strLTrim(char* str);
void visit(Graph& G, int verID);
int firstAdj(Graph& G, int v);
int nextAdj(Graph& G, int v, int w);
bool GraphIsTree(Graph& G);
void DFS(Graph& G, int v);
void DFSTraverse(Graph& G, int v);
void BFS(Graph& G, int v);
void BFSTraverse(Graph& G, int v);
//从文本文件创建邻接矩阵表示的图
int CreateGraphFromFile(char fileName[], Graph &G)
{
    FILE* pFile;          //定义文件指针
    char str[1000];         //存放读出一行文本的字符串
    char strTemp[10];      //判断是否注释行
    cellType eWeight;      //边的信息，常为边的权值
    GraphKind graphType;  //图类型枚举变量
    pFile = fopen(fileName, "r");
    if (!pFile)
    {
        printf("错误：文件%s打开失败。\n", fileName);
        return false;
    }
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);     //删除字符串左边空格，这是一个自定义的函数
        if (str[0] == '\n')    //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, str, 2);
        if (strstr(strTemp, "//") != NULL)  //跳过注释行
            continue;
        else                       //非注释行、非空行，跳出循环
            break;
    }
    //循环结束，str中应该已经是图的标识Graph，判断标识是否正确
    if (strstr(str, "Graph") == NULL)
    {
        printf("错误：打开的文件格式错误！\n");
        fclose(pFile); //关闭文件
        return false;
    }
    //读取图的类型，跳过空行
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);    //删除字符串左边空格，这是一个自定义函数
        if (str[0] == '\n')   //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, str, 2);
        if (strstr(strTemp, "//") != NULL)  //注释行，跳过，继续读取下一行
            continue;
        else                       //非空行，也非注释行，即图的类型标识
            break;
    }
    //设置图的类型
    if (strstr(str, "UDG"))
        graphType = UDG;    //无向图
    else if (strstr(str, "UDN"))
        graphType = UDN;    //无向网
    else if (strstr(str, "DG"))
        graphType = DG;     //有向图
    else if (strstr(str, "DN"))
        graphType = DN;     //有向网
    else
    {
        printf("错误：读取图的类型标记失败！\n");
        fclose(pFile);       //关闭文件
        return false;
    }
    //读取顶点行数据到str。跳过空行
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);      //删除字符串左边空格，这是一个自定义函数
        if (str[0] == '\n')     //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, str, 2);
        if (strstr(strTemp, "//") != NULL)  //注释行，跳过，继续读取下一行
            continue;
 else                       //非空行，也非注释行，即图的顶点元素行
            break;
    }
    //顶点数据放入图的顶点数组    
    char* token = strtok(str, " ");
    int nNum = 0;
    while (token != NULL)
    {
        G.Data[nNum] = *token;
        token = strtok(NULL, " ");
        nNum++;
    }
    //图的邻接矩阵初始化
    int nRow = 0;    //矩阵行下标
    int nCol = 0;     //矩阵列下标
    if (graphType == UDG || graphType == DG)
    {
        for (nRow = 0; nRow < nNum; nRow++)
            for (nCol = 0; nCol < nNum; nCol++)
                G.AdjMatrix[nRow][nCol] = 0;
    }
    else
    {
        for (nRow = 0; nRow < nNum; nRow++)
            for (nCol = 0; nCol < nNum; nCol++)
                G.AdjMatrix[nRow][nCol] = INF;  //INF表示无穷大
    }
    //循环读取边的数据到邻接矩阵
    int edgeNum = 0;         //边的数量
    elementType Nf, Ns;     //边或弧的2个相邻顶点
    while (fgets(str, 1000, pFile) != NULL)
    {
        strLTrim(str);       //删除字符串左边空格，这是一个自定义函数
        if (str[0] == '\n')      //空行，继续读取下一行
            continue;
        strncpy_s(strTemp, str, 2);
        if (strstr(strTemp, "//") != NULL)  //注释行，跳过，继续读取下一行
            continue;
        char* token = strtok(str, " ");  //以空格为分隔符，分割一行数据，写入邻接矩阵
        if (token == NULL)         //分割为空串，失败退出
        {
            printf("错误：读取图的边数据失败！\n");
            fclose(pFile);         //关闭文件
            return false;
        }
        Nf = *token;               //获取边的第一个顶点
        token = strtok(NULL, " ");   //读取下一个子串，即第二个顶点
        if (token == NULL)          //分割为空串，失败退出
        {
            printf("错误：读取图的边数据失败！\n");
            fclose(pFile);          //关闭文件
            return false;
        }
        Ns = *token;  //获取边的第二个顶点
        //从第一个顶点获取行号        
        for (nRow = 0; nRow < nNum; nRow++)
        {
            if (G.Data[nRow] == Nf)  //从顶点列表找到第一个顶点的编号
                break;
        }
        //从第二个顶点获取列号
        for (nCol = 0; nCol < nNum; nCol++)
        {
            if (G.Data[nCol] == Ns)  //从顶点列表找到第二个顶点的编号
                break;
        }
        //如果为网，读取权值
        if (graphType == UDN || graphType == DN)
        {                //读取下一个子串，即边的附加信息，常为边的权重
            token = strtok(NULL, " ");
            if (token == NULL)    //分割为空串，失败退出
            {
                printf("错误：读取图的边数据失败！\n");
                fclose(pFile);    //关闭文件
                return false;
            }
            eWeight = atoi(token);  //取得边的附加信息
        }
        if (graphType == UDN || graphType == DN)
            G.AdjMatrix[nRow][nCol] = eWeight;
        //如果为网，邻接矩阵中对应的边设置权值，否则置为1
        else
            G.AdjMatrix[nRow][nCol] = 1;
        edgeNum++;   //边数加1
    }
    G.VerNum = nNum;           //图的顶点数
    if (graphType == UDG || graphType == UDN)
        G.ArcNum = edgeNum / 2;  //无向图或网的边数等于统计的数字除2  
    else
        G.ArcNum = edgeNum;
    G.gKind = graphType;         //图的类型
    fclose(pFile);               //关闭文件
    cout << "已从文本文件\"D:\\Graph.txt\"创建邻接矩阵表示的图" << endl;
    return true;
}
void menu()
{
    cout << "0、退出程序" << endl;
    cout << "1、从文本文件创建邻接矩阵表示的图，并求给定图中边的个数" << endl;
    cout << "2、判断该图是否是一棵树" << endl;
    cout << "3、输出DFS序列" << endl;
    cout << "4、输出BFS序列" << endl;
}
// 删除字符串、字符数组左边的空格
void strLTrim(char* str)
{
    int i, j;
    int n = 0;
    n = strlen(str) + 1;
    for (i = 0; i < n; i++)
    {
        if (str[i] != ' ')  //找到左起第一个非空格位置
            break;
    }
    //以第一个非空格字符为手字符移动字符串
    for (j = 0; j < n; j++)
    {
        str[j] = str[i];
        i++;
    }
}
void visit(Graph& G, int verID)
{        //顶点编号从1开始，数组0单元不用
    cout << G.Data[verID] << " ";
    visited[verID] = true;
}
//求顶点v的第一个邻接点
int firstAdj(Graph& G, int v)
{
    int w;
    for (w = 1; w <= G.VerNum; w++)
    {
        if ((G.AdjMatrix[v][w] >= 1) && (G.AdjMatrix[v][w]) < INF)
            return w;    //返回第一个邻接点编号
    }
    return 0;          //未找到邻接点，返回0
}
//求顶点v的位于邻接点w后的下一个邻接点
int nextAdj(Graph& G, int v, int w)
{
    int k;
    for (k = w + 1; k <= G.VerNum; k++)
    {
        if ((G.AdjMatrix[v][k] >= 1) && (G.AdjMatrix[v][k]) < INF)
            return k;    //返回v的位于w之后的下一个邻接点k
    }
    return 0;           //不存在下一个邻接点，返回0
}
//判断该图是否是一棵树
bool GraphIsTree(Graph& G)
{
    for (int i = 0; i < G.VerNum; i++)
    {
        visited[i] = false;
    }
    int VNum = 0;
    int ENum = 0;
    if (VNum == G.VerNum && ENum == 2 * (G.VerNum - 1))
    {
        cout << "该图是一棵树" << endl;
        return true;
    }
    else
    {
        cout << "该图不是一棵树" << endl;
        return false;
    }
}
void DFS(Graph& G, int v)
{
    int w;
    visit(G, v);             //访问定点，并设置其访问标志
    w = firstAdj(G, v);        //求出v的第一个临结点，返回临结点编号w
    while (w != 0)             //还存在临结点
    {
        if (visited[w] == false && G.AdjMatrix[v][w] >= 1 && G.AdjMatrix[v][w] < INF)//从来没有访问过的临结点进行深度遍历
            DFS(G, w);
        w = nextAdj(G, v, w);    //取下一个临结点
    }
}
//一般图的深度优先遍历
void DFSTraverse(Graph& G, int v)
{
    int i;
    for (i = 1; i <= G.VerNum; i++)
    {
        visited[i] = false;       //初始化访问标志为false
    }
    for (v; v >= 1; v--)             //编号1到v
    {
        if (visited[v] == false)   //循环选择未被访问的顶点
            DFS(G, v);           //每次循环遍历一个连通分量
    }
    for (v; v <= G.VerNum; v++)      //编号v到G.vernum
    {
        if (visited[v] == false)   //循环选择未被访问的顶点
            DFS(G, v);           //每次循环遍历一个连通分量
    }
}
// 连通图的广度优先遍历
void BFS(Graph & G, int v)
{
    queue<int> Q;              //队列存放元素的编号
    int w;
    visit(G, v);                //访问定点，并设置其访问标志
    Q.push(v);                 //节点编号入队
    while (!Q.empty())
    {
        v = Q.front();
        Q.pop();
        w = firstAdj(G, v);
        while (w != 0)
        {
            if (!visited[w] && G.AdjMatrix[v][w] >= 1 && G.AdjMatrix[v][w] < INF)
            {
                visit(G, w);
                Q.push(w);
            }
            w = nextAdj(G, v, w);
        }
    }
}
//一般图的广度优先遍历
void BFSTraverse(Graph& G, int v)
{
    int i;
    for (i = 1; i <= G.VerNum; i++)
    {
        visited[i] = false;       //初始化访问标志为false
    }
    for (v; v >= 1; v--)             //编号1到v
    {
        if (visited[v] == false)   //循环选择未被访问的顶点
            BFS(G, v);           //每次循环遍历一个连通分量
    }
    for (v; v <= G.VerNum; v++)      //编号v到G.vernum
    {
        if (visited[v] == false)   //循环选择未被访问的顶点
            BFS(G, v);           //每次循环遍历一个连通分量
    }
}
  • 这篇博客也许可以解决你的问题👉 ：【霍罗维兹数据结构】GRAPH 图 | 基本图运算 DFS&BFS | 最小代价生成树
  • 除此之外, 这篇博客: BFS及DFS的Java实现中的 图（graph） 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:

  • 图和树的最大区别在于图的下一个节点可能指向已访问过的节点。因此在使用BFS及DFS遍历时，应维护一个Set，Set中存放已被访问过的节点，在遍历时先判断节点未被访问过再遍历即可。

     

    使用BFS举例如下：

    //使用Queue实现BFS
public void BFSWithQueue(Node root) {
    Queue<Node> queue = new LinkedList<>();
    if (root != null)
        queue.add(root);
    Set<Node> visited = new HashSet<>();
    
    while (!queue.isEmpty()) {
        Node node = queue.poll();
        visited.add(node);

        //在这里处理遍历到的Node节点

        if (node.children != null) {
            for (Node child : node.children) {
                if (child != null && !visited.contains(child){
                    queue.add(child);
                }
            }
        }
    }
}

     

    follow my github:https://github.com/Gene1994