设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 编程语言专区 › AI禁区（悬赏） › C语言实现图的遍历
返回列表 发新帖
查看: 1684|回复: 3

[C\C++] C语言实现图的遍历

[复制链接]
王小二°
发表于 2024-6-5 23:31:07 | 显示全部楼层 |阅读模式
50鱼币

  2. #include<stdio.h>
  3. #include<stdlib.h>
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define OK 1
  7. #define ERROR 0
  8. #define OVERFLOW -2
  9. typedef int Status;
  10. typedef struct Node
  11. {
  12.         int elem;
  13.         struct Node *next;
  14. }Node,*QNode;
  15. typedef struct
  16. {
  17.         QNode front;
  18.         QNode rear;
  19. }Queue;
  20. #define MAX 20

  22. typedef struct ArcNode       //表结点
  23. {
  24.         int adjvex;              //该边所指向的顶点的位置
  25.         struct ArcNode *nextarc; //指向下一条边
  26. }ArcNode;

  28. typedef struct VNode           //头结点
  29. {
  30.         int data;                //顶点信息
  31.         ArcNode *firstarc;       //指向第一条依附该结点的边的指针
  32. }VNode,AdjList[MAX];

  34. typedef struct
  35. {
  36.         AdjList vertices;     //一维数组（头结点）
  37.         int vexnum;           //结点的个数
  38.         int arcnum;           //边的条数
  39. }Graph;
  40. Queue* InitQueue(Queue *Q)
  41. {
  42.         Q->front=(QNode)malloc(sizeof(Node));
  43.         if(Q->front!=NULL)  
  44.         {
  45.                 Q->rear=Q->front;
  46.                 Q->front->next=NULL;
  47.                 return Q;
  48.         }

  50.         else return NULL;
  51. }
  52. Status EnQueue(Queue *Q,int e)
  53. {
  54.        
  55.         QNode newnode;
  56.         newnode=(QNode)malloc(sizeof(Node));
  57.         if(newnode!=NULL)
  58.         {
  59.                 newnode->elem=e;
  60.                 newnode->next=NULL;
  61.                 Q->rear->next=newnode;
  62.                 Q->rear=newnode;
  63.                 return OK;
  64.         }
  65.         else return FALSE;
  66. }
  67. Status DeQueue(Queue *Q,int *e)
  68. {
  69.         QNode p;
  70.         if(Q->front==Q->rear)
  71.         {
  72.                 return 0;
  73.         }
  74.         p=Q->front->next;
  75.         Q->front->next=p->next;
  76.         if(Q->rear==p)
  77.                 Q->rear=Q->front;
  78.         *e=p->elem;
  79.         free(p);
  80.         return 1;
  81. }

  83. int LocateVex(Graph *G,int index)
  84. {
  85.         int i;
  86.         for(i=0;i<G->vexnum;i++)
  87.         {
  88.                 if(G->vertices[i].data==index)
  89.                         return i;
  90.         }
  91. }

  93. Status CreateGraph(Graph *G)//Status CreateGraph(Graph &G)(引用参数）
  94. {//以邻接表形式创建无向图G
  95.         int m,n,i,j,k,v1,v2,flag=0;
  96.         ArcNode *p1,*q1,*p,*q;
  97.         printf("请输入VNode的编号: ");
  98.         scanf("%d",&m);
  99.         printf("请输入ArcNode的编号");
  100.         scanf("%d",&n);
  101.         G->vexnum=m;            //顶点数目
  102.         G->arcnum=n;            //边的数目
  103.         for(i=0;i<G->vexnum;++i)
  104.         {
  105.                 G->vertices[i].data=i+1;      //顶点信息
  106.                 G->vertices[i].firstarc=NULL;
  107.         }
  108.         //顶点信息
  109.         printf("输出VNode的消息:\n");
  110.         for(i=0;i<G->vexnum;++i)
  111.                 printf("v%d\n",G->vertices[i].data);
  112.        
  113.         for(k=0;k<G->arcnum;++k)
  114.         {
  115.                 printf("请输入%d边起始点和端点: ",k+1);
  116.                 scanf("%d%d",&v1,&v2);
  117.                 i=LocateVex(G,v1);
  118.                 j=LocateVex(G,v2);
  119.                
  120.                 if(i>=0&&j>=0)
  121.                 {
  122.                         ++flag;
  123.                         p=(ArcNode *)malloc(sizeof(ArcNode));
  124.                         p->adjvex=j;
  125.                         p->nextarc=NULL;
  126.                         if(!G->vertices[i].firstarc)
  127.                                 G->vertices[i].firstarc=p;
  128.                         else
  129.                         {
  130.                                 for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc);
  131.                                 p1->nextarc=p;
  132.                         }
  133.                        
  134.                         q=(ArcNode *)malloc(sizeof(ArcNode));
  135.                         q->adjvex=i;
  136.                         q->nextarc=NULL;
  137.                         if(!G->vertices[j].firstarc)
  138.                                 G->vertices[j].firstarc=q;
  139.                         else
  140.                         {
  141.                                 for(q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc);
  142.                                 q1->nextarc=q;
  143.                         }
  144.                 }
  145.                 else
  146.                 {
  147.                         printf("没有这个优势!\n");
  148.                         k=flag-1;
  149.                 }
  150.                
  151.         }
  152.        
  153.         printf("邻接表为:\n"); //输出邻接表
  154.         for(i=0;i<G->vexnum;++i)
  155.         {
  156.                 printf("\t%d v%d->",i,G->vertices[i].data);
  157.                 p=G->vertices[i].firstarc;
  158.                 while(p->nextarc)
  159.                 {
  160.                         printf("%d->",p->adjvex);
  161.                         p=p->nextarc;
  162.                 }
  163.                 printf("%d\n",p->adjvex);
  164.         }
  165.         return OK;
  166. }

  168. int FirstAdjVex(Graph G,int v)
  169. {//返回v的第一个邻接顶点
  170.         ArcNode *p;
  171.         p=G.vertices[v].firstarc;
  172.         if(p)
  173.                 return (p->adjvex);
  174.         else
  175.                 return -1;
  176. }


  179. int NextAdjVex(Graph G,int v,int w)
  180. {//返回v中相对于w的下一个邻接顶点
  181.         int flag=0;
  182.         ArcNode *p;
  183.         p=G.vertices[v].firstarc;
  184.         while(p)
  185.         {
  186.                 if(p->adjvex==w)
  187.                 {
  188.                         flag=1;
  189.                         break;
  190.                 }
  191.                 p=p->nextarc;
  192.         }
  193.         if(flag && p->nextarc)
  194.                 return p->nextarc->adjvex;
  195.         else
  196.                 return -1;
  197. }

  199. int Visited[MAX];

  201. void DFS(Graph G,int v)
  202. {//深度优先遍历
  203.        
  204.         ArcNode *p;
  205.         p=G.vertices[v].firstarc;
  206.         printf("%d ",G.vertices[v].data);
  207.         Visited[v]=TRUE;
  208.         while(p)
  209.         {
  210.                 if(!Visited[p->adjvex])
  211.                 {
  212.                
  213.                         DFS(G,p->adjvex);
  214.                 }
  215.                 p=p->nextarc;
  216.                
  217.         }
  218. }

  220. void DFSTraverse(Graph G)
  221. {
  222.         int i;//递归
  223.         for(i=0;i<G.vexnum;i++)
  224.         {
  225.                 Visited[i]=FALSE;
  226.         }
  227.         for(i=0;i<G.vexnum;i++)
  228.         {
  229.                 if(!Visited[i])
  230.                         DFS(G,i);
  231.         }
  232. }

  234. void BFSTraverse(Graph G)
  235. {//广度优先遍历
  236.         int i,index;
  237.         ArcNode *temp;
  238.         Queue* que=InitQueue(que);
  239.        
  240.         for(i=0;i<G.vexnum;i++)
  241.         {
  242.                 Visited[i]=0;
  243.         }
  244.         index=G.vertices[0].data;
  245.         if(!Visited[index])
  246.         {
  247.                 EnQueue(que,index);
  248.                 Visited[index]=1;
  249.                 while(que->rear!=que->front)
  250.                 {
  251.                         DeQueue(que,&index);
  252.                        
  253.                         printf("%d ",G.vertices[index].data);
  254.                         temp=G.vertices[index].firstarc;
  255.                         while(temp)
  256.                         {
  257.                                 index=LocateVex(&G,G.vertices[index].data);
  258.                                 if(!Visited[index])
  259.                                 {
  260.                                         EnQueue(que,index);
  261.                                         Visited[index]=1;
  262.                                 }
  263.                                 temp=temp->nextarc;
  264.                                
  265.                         }
  266.                 }
  267.         }
  268.        
  269. }

  271. void main()
  272.                         {
  273.                                 Graph G;
  274.                                 CreateGraph(&G);
  275.                                 printf("深度优先搜索:\n");
  276.                                 DFSTraverse(G);
  277.                                 printf("\n广度优先搜索:\n");
  278.                                 BFSTraverse(G);
  279.                                 printf("\n");
  280.                                 system("pause");
  281.                         }
  282.                        
  283.        
  284.                        
  285.                        
复制代码

能不能帮忙看看为什么广度遍历不成功啊，急

最佳答案

小甲鱼的二师兄

查看完整内容

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

小甲鱼的二师兄
发表于 2024-6-5 23:31:08 | 显示全部楼层
本帖最后由 小甲鱼的二师兄 于 2024-6-5 23:45 编辑
  1. #include <stdio.h>
  2. #include <stdlib.h>

  4. #define TRUE 1
  5. #define FALSE 0
  6. #define OK 1
  7. #define ERROR 0
  8. #define OVERFLOW -2

  10. typedef int Status;

  12. typedef struct Node {
  13.     int elem;
  14.     struct Node *next;
  15. } Node, *QNode;

  17. typedef struct {
  18.     QNode front;
  19.     QNode rear;
  20. } Queue;

  22. #define MAX 20

  24. typedef struct ArcNode {       // 表结点
  25.     int adjvex;                // 该边所指向的顶点的位置
  26.     struct ArcNode *nextarc;   // 指向下一条边
  27. } ArcNode;

  29. typedef struct VNode {         // 头结点
  30.     int data;                  // 顶点信息
  31.     ArcNode *firstarc;         // 指向第一条依附该结点的边的指针
  32. } VNode, AdjList[MAX];

  34. typedef struct {
  35.     AdjList vertices;          // 一维数组（头结点）
  36.     int vexnum;                // 结点的个数
  37.     int arcnum;                // 边的条数
  38. } Graph;

  40. // 初始化队列
  41. Queue* InitQueue(Queue *Q) {
  42.     Q->front = (QNode)malloc(sizeof(Node));
  43.     if (Q->front != NULL) {
  44.         Q->rear = Q->front;
  45.         Q->front->next = NULL;
  46.         return Q;
  47.     } else {
  48.         return NULL;
  49.     }
  50. }

  52. // 入队
  53. Status EnQueue(Queue *Q, int e) {
  54.     QNode newnode;
  55.     newnode = (QNode)malloc(sizeof(Node));
  56.     if (newnode != NULL) {
  57.         newnode->elem = e;
  58.         newnode->next = NULL;
  59.         Q->rear->next = newnode;
  60.         Q->rear = newnode;
  61.         return OK;
  62.     } else {
  63.         return FALSE;
  64.     }
  65. }

  67. // 出队
  68. Status DeQueue(Queue *Q, int *e) {
  69.     QNode p;
  70.     if (Q->front == Q->rear) {
  71.         return 0;
  72.     }
  73.     p = Q->front->next;
  74.     Q->front->next = p->next;
  75.     if (Q->rear == p) {
  76.         Q->rear = Q->front;
  77.     }
  78.     *e = p->elem;
  79.     free(p);
  80.     return 1;
  81. }

  83. // 查找顶点位置
  84. int LocateVex(Graph *G, int index) {
  85.     int i;
  86.     for (i = 0; i < G->vexnum; i++) {
  87.         if (G->vertices[i].data == index)
  88.             return i;
  89.     }
  90.     return -1;  // 如果找不到顶点，返回-1
  91. }

  93. // 创建图
  94. Status CreateGraph(Graph *G) {
  95.     int m, n, i, j, k, v1, v2;
  96.     ArcNode *p1, *q1, *p, *q;
  97.     printf("请输入VNode的编号: ");
  98.     scanf("%d", &m);
  99.     printf("请输入ArcNode的编号: ");
  100.     scanf("%d", &n);
  101.     G->vexnum = m;            // 顶点数目
  102.     G->arcnum = n;            // 边的数目

  104.     for (i = 0; i < G->vexnum; ++i) {
  105.         G->vertices[i].data = i + 1;      // 顶点信息
  106.         G->vertices[i].firstarc = NULL;
  107.     }

  109.     printf("输出VNode的信息:\n");
  110.     for (i = 0; i < G->vexnum; ++i)
  111.         printf("v%d\n", G->vertices[i].data);

  113.     for (k = 0; k < G->arcnum; ++k) {
  114.         printf("请输入第%d条边的起始点和终点: ", k + 1);
  115.         scanf("%d%d", &v1, &v2);
  116.         i = LocateVex(G, v1);
  117.         j = LocateVex(G, v2);

  119.         if (i >= 0 && j >= 0) {
  120.             p = (ArcNode *)malloc(sizeof(ArcNode));
  121.             p->adjvex = j;
  122.             p->nextarc = NULL;
  123.             if (!G->vertices[i].firstarc)
  124.                 G->vertices[i].firstarc = p;
  125.             else {
  126.                 for (p1 = G->vertices[i].firstarc; p1->nextarc; p1 = p1->nextarc);
  127.                 p1->nextarc = p;
  128.             }

  130.             q = (ArcNode *)malloc(sizeof(ArcNode));
  131.             q->adjvex = i;
  132.             q->nextarc = NULL;
  133.             if (!G->vertices[j].firstarc)
  134.                 G->vertices[j].firstarc = q;
  135.             else {
  136.                 for (q1 = G->vertices[j].firstarc; q1->nextarc; q1 = q1->nextarc);
  137.                 q1->nextarc = q;
  138.             }
  139.         } else {
  140.             printf("没有这个顶点!\n");
  141.             --k;  // 如果顶点不存在，重新输入这条边
  142.         }
  143.     }

  145.     printf("邻接表为:\n");  // 输出邻接表
  146.     for (i = 0; i < G->vexnum; ++i) {
  147.         printf("\t%d v%d->", i, G->vertices[i].data);
  148.         p = G->vertices[i].firstarc;
  149.         while (p) {
  150.             printf("%d->", p->adjvex);
  151.             p = p->nextarc;
  152.         }
  153.         printf("NULL\n");
  154.     }
  155.     return OK;
  156. }

  158. int Visited[MAX];  // 访问标志数组

  160. // 广度优先遍历
  161. void BFSTraverse(Graph G) {
  162.     int i, index;
  163.     ArcNode *temp;
  164.     Queue que;
  165.     InitQueue(&que);

  167.     for (i = 0; i < G.vexnum; i++) {
  168.         Visited[i] = 0;  // 初始化访问标志数组
  169.     }

  171.     for (i = 0; i < G.vexnum; i++) {
  172.         if (!Visited[i]) {
  173.             EnQueue(&que, i);
  174.             Visited[i] = 1;
  175.             while (que.rear != que.front) {
  176.                 DeQueue(&que, &index);
  177.                 printf("%d ", G.vertices[index].data);
  178.                 temp = G.vertices[index].firstarc;
  179.                 while (temp) {
  180.                     if (!Visited[temp->adjvex]) {
  181.                         EnQueue(&que, temp->adjvex);
  182.                         Visited[temp->adjvex] = 1;
  183.                     }
  184.                     temp = temp->nextarc;
  185.                 }
  186.             }
  187.         }
  188.     }
  189.     printf("\n");
  190. }

  192. int main() {
  193.     Graph G;
  194.     CreateGraph(&G);
  195.     printf("广度优先遍历结果：\n");
  196.     BFSTraverse(G);
  197.     return 0;
  198. }
复制代码
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

王小二°
 楼主| 发表于 2024-6-6 00:02:31 | 显示全部楼层
小甲鱼的二师兄 发表于 2024-6-5 23:44

感谢感谢
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

王小二°
 楼主| 发表于 2024-6-6 00:03:56 | 显示全部楼层
小甲鱼的二师兄 发表于 2024-6-5 23:31

麻烦问一下，我的bfs函数问题出在哪里啊？
小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-5-7 19:46

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表