在邻接矩阵上应用广度和深度优先搜索？

2 回答

• 1

  ANS 1: 是的，最好将文本文件中的输入读入常规矩阵 .

  void MyGraph::csv_import()
      {
          int temp, i=0;
          string parsed;
          fstream file("input.csv");
          while (getline(file, parsed, ',')) {
              temp = stoi(parsed);
              arr[i/10][i%10] = temp; //10 x 10 Matrix
              i++;
          }
      }
  

  ANS 2: 选择一个起始节点，调用BFS显示搜索结果 . 例如（在我的情况下）

  void MyGraph::BFS(int v)
      {
          memset(visited, false, sizeof(visited);
          QQ.push(v);                         //push the starting vertex into queue
          visited[v] = true;                  //mark the starting vertex visited
          while (!QQ.empty())                 //until queue is not empty
          {
              v = QQ.front();                 //assign v the vertex on front of queue
              cout << v << "  ";              //print the vertex to be popped
              QQ.pop();                       //pop the vertex on front
              for (int c = 0; c< V; c++)      //V is the number of nodes
              {
                   //M[i][j] == 1, when i,j are connected
                  if (M[v][c] == 1 && visited[c] == false) 
                  {                           //if vertex has edge and is unvisited
                      QQ.push(c);             //push to the queue
                      visited[c] = true;      //mark it visited
                      Path[c] = p;            //assign the path length
                  }
              }
          }
      }
  

  回复于 2024-04-27T07:04:04+08:00
• 1

  • 是的

  • http://www.geeksforgeeks.org/depth-first-traversal-for-a-graph/

  http://www.geeksforgeeks.org/breadth-first-traversal-for-a-graph/

  BFS：注意：对于无向图，扫描矩阵的上三角或下三角就足够了 . 对于有向图，应考虑整个矩阵 .

  步骤1：维护一组布尔值，以保存是否访问了节点 .

  第二步：实现队列

  步骤3：从任何元素开始并将其推入队列并将其标记为已访问 . Step4：在循环中将队列中的顶部元素出列队列 . 它是x

  对于x..push的所有未访问的邻居，他们进入队列并将其标记为已访问 .

  执行step4直到队列为空..

  在将元素推入队列时给出图遍历顺序 .

  如果我找时间，我会解释dfs

  回复于 2024-04-27T07:04:04+08:00