图的广度优先搜索代码

我叫淳子

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

#include <stdio.h>  
#include <stdlib.h>

 
typedef char VertexType;                //顶点类型应由用户定义
typedef int EdgeType;                   //边上的权值类型应由用户定义
 
#define MAXVEX  100             //最大顶点数，应由用户定义
#define INFINITY  0                //用0来代表无穷大
#define DEBUG
int visit[100] = {};
typedef struct
{
    VertexType vexs[MAXVEX];            //顶点表
    EdgeType   arc[MAXVEX][MAXVEX];         //邻接矩阵，可看作边
    int numVertexes, numEdges;      //图中当前的顶点数和边数
}Graph;
int locates(Graph *g, char ch)
{
    int i = 0;
    for(i = 0; i < g->numVertexes; i++)
    {
        if(g->vexs[i] == 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[i] = getchar();
        while(g->vexs[i] == '\n')
        {
            g->vexs[i] = getchar();
        }
    }
     
    #ifdef DEBUG
    for(i = 0; i < g->numVertexes; i++)
    {
            
        printf("%c ", g->vexs[i]);
    }
    printf("\n");
    #endif
 
    
    for(i = 0; i < g->numEdges; i++)
    {
        for(j = 0; j < g->numEdges; j++)
        {
            g->arc[i][j] = 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[m][n] = w;
        g->arc[n][m] = g->arc[m][n];  //因为是无向图，矩阵对称
    }
}
void bfs(Graph *g)  
{  
    int i, j;  
    int x;  
    printf("遍历的节点次序为：") ;
    for (i = 0; i < g->numVertexes; i++) 
        {  
        if (visit[i] != 1) 
                {  
            visit[i] = 1;  
            printf("%3c", g->vexs[i]);  
  
           
        }  
    }  
}  
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[i][j]);
        }
        printf("\n");
    }
}
  
int main()  
{  
    Graph g;
    
    CreateGraph(&g);
    printGraph(g);
        bfs(&g);  
    printf("\n");  
    printf("0代表无穷大"); 
    return 0;  
}  

～风介～

表示数据结构没学好啊~

我叫淳子

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

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

～风介～

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

我是学着学着就忘了~

lewisyixin

感谢分享