论坛 › 数据结构与算法 › 图的广度优先搜索代码

我叫淳子 发表于 2015-12-30 16:54:28

图的广度优先搜索代码

跟深度优先还是一样，这两个是我在做数据结构作业花大量时间去找的代码，就是老师的要求肯定百度是无法直接满足的，就必须通过各个网站的不同功能的代码综合在一起，然后组成的的代码。有错误的话欢迎大神们来纠正。
#include <stdio.h>
#include <stdlib.h>


typedef char VertexType;                //顶点类型应由用户定义
typedef int EdgeType;                   //边上的权值类型应由用户定义

#define MAXVEX100             //最大顶点数，应由用户定义
#define INFINITY0                //用0来代表无穷大
#define DEBUG
int visit = {};
typedef struct
{
    VertexType vexs;            //顶点表
    EdgeType   arc;         //邻接矩阵，可看作边
    int numVertexes, numEdges;      //图中当前的顶点数和边数
}Graph;
int locates(Graph *g, char ch)
{
    int i = 0;
    for(i = 0; i < g->numVertexes; i++)
    {
      if(g->vexs == ch)
      {
            break;
      }
    }
    if(i >= g->numVertexes)
    {
      return -1;
    }
   
    return i;
}
void CreateGraph(Graph *g)
{
    int i, j, k, w;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &(g->numVertexes), &(g->numEdges));
   
    #ifdef DEBUG
    printf("%d %d\n", g->numVertexes, g->numEdges);
    #endif
    printf("输入节点编号:\n");
    for(i = 0; i < g->numVertexes; i++)
    {
      g->vexs = getchar();
      while(g->vexs == '\n')
      {
            g->vexs = getchar();
      }
    }
   
    #ifdef DEBUG
    for(i = 0; i < g->numVertexes; i++)
    {
           
      printf("%c ", g->vexs);
    }
    printf("\n");
    #endif

   
    for(i = 0; i < g->numEdges; i++)
    {
      for(j = 0; j < g->numEdges; j++)
      {
            g->arc = INFINITY; //邻接矩阵初始化
      }
    }
    for(k = 0; k < g->numEdges; k++)
    {
      char p, q;
      printf("输入边(vi,vj)上的下标i，下标j和权值:\n");
         
      p = getchar();
      while(p == '\n')
      {
            p = getchar();
      }
      q = getchar();
      while(q == '\n')
      {
            q = getchar();
      }
      scanf("%d", &w);   
         
      int m = -1;
      int n = -1;
      m = locates(g, p);
      n = locates(g, q);
      if(n == -1 || m == -1)
      {
            fprintf(stderr, "there is no this vertex.\n");
            return;
      }
      //getchar();
      g->arc = w;
      g->arc = g->arc;//因为是无向图，矩阵对称
    }
}
void bfs(Graph *g)
{
    int i, j;
    int x;
    printf("遍历的节点次序为：") ;
    for (i = 0; i < g->numVertexes; i++)
        {
      if (visit != 1)
                {
            visit = 1;
            printf("%3c", g->vexs);

         
      }
    }
}
void printGraph(Graph g)
{
    int i, j;
    for(i = 0; i < g.numVertexes; i++)
    {
      for(j = 0; j < g.numVertexes; j++)
      {
            printf("%d", g.arc);
      }
      printf("\n");
    }
}

int main()
{
    Graph g;
   
    CreateGraph(&g);
    printGraph(g);
        bfs(&g);
    printf("\n");
    printf("0代表无穷大");
    return 0;
}

～风介～ 发表于 2015-12-31 00:05:34

表示数据结构没学好啊~{:9_240:}

我叫淳子 发表于 2015-12-31 10:35:08

～风介～ 发表于 2015-12-31 00:05
表示数据结构没学好啊~

我也没学好。。。不然就自己写了。。不用去网上找。。。我现在在恶补小甲鱼的数据结构和算法。

～风介～ 发表于 2015-12-31 18:28:48

我叫淳子 发表于 2015-12-31 10:35
我也没学好。。。不然就自己写了。。不用去网上找。。。我现在在恶补小甲鱼的数据结构和算法。

我是学着学着就忘了~{:7_140:}

lewisyixin 发表于 2016-1-12 23:52:47

感谢分享

查看完整版本: 图的广度优先搜索代码