图的便深度广度遍历如何进行

Question

如何根据任意图，用c语言建立它的邻接表，并且从键盘指定一个起点，按照队列进行广度遍历，按照栈进行深度遍历?想不明白栈是怎么定义遍历的

Answer 1

• 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/233189
• 除此之外, 这篇博客: 【C数据结构】解决链表最繁结构双向链表和经典力扣题中的 一、双向带头循环链表 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 
    因为它的结构是链表中最复杂的，通过这个结构，我们可以更好的练习一下双向、带头结点、循环这几个情况下的链表。
    它和单链表相比，虽然结构上复杂了，但是单链表的一个明显的缺点——只能往一个方向访问，访问不了上一个结点，使得在一些操作的实现上变得很复杂。
    所以它的结构复杂，却在一些操作的实现上可以变得很容易。
   

  ---

• 以下回答由chatgpt基于相关博客总结生成:

  建立邻接表的步骤如下：

  1. 定义邻接表的结构体，包括顶点数和每一个顶点所对应的边表
  2. 为每个顶点的边表开辟空间
  3. 读取边的信息，将该边的信息加入到边表中
  4. 将所有边读取完毕后，邻接表就建好了

  下面是代码：

  #include <stdio.h>
  #include <stdlib.h>
  
  // 边表结构体
  typedef struct EdgeNode {
      int adjvex;             // 邻接点域，存储该顶点对应的下标
      struct EdgeNode *next;  // 指向下一个邻接点的指针
  } EdgeNode;
  
  // 顶点表结构体
  typedef struct VertexNode {
      char data;          // 顶点域，存储顶点信息
      EdgeNode *firstedge; // 边表头指针
  } VertexNode, AdjList[100];
  
  // 邻接表结构体
  typedef struct {
      AdjList adjList;
      int numVertexes, numEdges;  // 图中当前的顶点数和边数
  } GraphAdjList;
  
  // 建立图的邻接表结构
  void CreateALGraph(GraphAdjList *G) {
      int i, j, k;
      EdgeNode *e;
      printf("请输入顶点数和边数:\n");
      scanf("%d %d", &(G->numVertexes), &(G->numEdges));
  
      // 读入顶点信息建立顶点表
      for (i = 0; i < G->numVertexes; i++) {
          printf("请输入第%d个顶点信息: ", i + 1);
          scanf(" %c", &(G->adjList[i].data));
          G->adjList[i].firstedge = NULL;
      }
  
      // 读入边信息，建立邻接表
      for (k = 0; k < G->numEdges; k++) {
          printf("请输入边(vi, vj)上的顶点序号:\n");
          scanf("%d %d", &i, &j);
  
          // 向内存申请空间
          e = (EdgeNode *)malloc(sizeof(EdgeNode));
          e->adjvex = j;
  
          // 新增的点放在链表的头部
          e->next = G->adjList[i].firstedge;
          G->adjList[i].firstedge = e;
  
          // 无向图需要建两次
          e = (EdgeNode *)malloc(sizeof(EdgeNode));
          e->adjvex = i;
          e->next = G->adjList[j].firstedge;
          G->adjList[j].firstedge = e;
      }
  }
  
  // 广度优先遍历
  void BFSTraverse(GraphAdjList G, int start) {
      int visited[100] = {0};  // 记录已访问的节点
      EdgeNode *p;
      int que[100], head = 0, tail = 0;  // 定义队列
      int i, j, k;
      printf("从%d号节点开始的广度优先遍历路径为: ", start);
      visited[start] = 1;
      que[tail++] = start;
  
      // 执行队列操作
      while (head != tail) {
          i = que[head++];
          for (p = G.adjList[i].firstedge; p != NULL; p = p->next) {
              j = p->adjvex;
              if (!visited[j]) {
                  visited[j] = 1;
                  que[tail++] = j;
              }
          }
      }
  
      // 打印路径
      for (k = 0; k < G.numVertexes; k++) {
          if (visited[k]) {
              printf("%c ", G.adjList[k].data);
          }
      }
      printf("\n");
  }
  
  // 栈实现深度优先遍历
  void DFS(GraphAdjList g, int start) {
      EdgeNode *p;
      int visited[100] = {0};  // 记录已访问的顶点
      int s[100], top = -1;
      int i, j;
      printf("从%d号节点开始的深度优先遍历路径为: ", start);
      visited[start] = 1;
      s[++top] = start;
  
      // 执行栈操作
      while (top != -1) {
          i = s[top--];
          printf("%c ", g.adjList[i].data);
          for (p = g.adjList[i].firstedge; p != NULL; p = p->next) {
              j = p->adjvex;
              if (!visited[j]) {
                  visited[j] = 1;
                  s[++top] = j;
              }
          }
      }
      printf("\n");
  }
  
  int main() {
      GraphAdjList G;
      printf("请依次输入各个顶点的信息以及边信息:\n");
      CreateALGraph(&G);
      int start;
      printf("请输入遍历的起点: \n");
      scanf("%d", &start);
      BFSTraverse(G, start);
      DFS(G, start);
      return 0;
  }