06-图3 六度空间 无法debug

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
using namespace std;

typedef int vertex;//顶点下标表示整型
typedef int weight; //边的权值设为整型

//定义边
typedef struct edgenode* Ptr2edgenode;
struct edgenode
{
    vertex v1;
    vertex v2;
};
typedef Ptr2edgenode edge;

//定义邻接点
typedef struct adjnode* Ptr2adjnode;
struct adjnode
{
    vertex adjindex;//邻接点下标
    adjnode* next;
};

//定义表头顶点结点

typedef struct vertexnode
{
    Ptr2adjnode firstedge; //头顶点结点第一条边指向的邻接点
}AdjList[10000];//一个数组，存放的每个元素都是struct vertexnode, 即指向邻接点的指针


//定义图，用邻接表表示图
typedef struct graphnode* Ptr2graphnode;
struct graphnode
{
    int nv;
    int ne;
    AdjList G;
};
typedef Ptr2graphnode LGraph;

LGraph createGraph(int numv)
{
    vertex v;
    LGraph graph = new graphnode;
    graph -> nv = numv;
    graph -> ne = 0;

    for(v = 0; v < graph->nv; v++)
    {
        graph -> G[v].firstedge = NULL;
    }
    return graph;
}

void insertEdge(LGraph graph, edge e)
{

    //newnode1是指向邻接点的指针
    Ptr2adjnode newnode2 = new adjnode;
    newnode2 -> adjindex = e -> v2;

    //  newnode1 -> w = 1;
    newnode2 -> next = graph -> G[e->v1].firstedge;
    graph -> G[e->v1].firstedge = newnode2;

    //newnode2是指向邻接点的指针
    Ptr2adjnode newnode1 = new adjnode;
    newnode1 -> adjindex = e -> v1;
    //   newnode2 -> w = 1;
    newnode1 -> next = graph -> G[e->v2].firstedge;
    graph -> G[e->v2].firstedge = newnode1;
}

LGraph BuildGraph()
{
    LGraph graph;
    edge e;
    int v;
    int nv;
    scanf("%d", &nv);
    //   getchar();
    graph = createGraph(nv);

    scanf("%d", &(graph->ne));

    getchar();
    if(graph -> ne != 0)
    {
        e = new edgenode;
        for(int i = 0; i < graph -> ne; i++)
        {
            scanf("%d %d", &(e->v1), &(e->v2));

            insertEdge(graph, e);
        }
    }
    return graph;
}


/*
注意！并不是每调用一次BFS，深度就增加一层
例如：
第一次bfs得到层数为1的点，c, e, f
第二次bfs，是以c为起始点bfs, g, h, i
第三次bfs, 是以e为起始点bfs, j, k
但是第二次bfs, 第三次bfs的层数都是2，并不是按照调用bfs次数

 */
int BFS(LGraph graph, vertex i, int visited[])
{
    queue<vertex> q;
    int cnt = 1;//该结点本身就是一个
    int level = 0;
    vertex last = i;
    vertex tail = i;

    visited[i] = 1;
    q.push(i);
    vertex temp;
    while(!q.empty())
    {
        temp = q.front();
        q.pop();
        for(adjnode* w = graph->G[temp].firstedge; w != NULL;  w = w -> next)
        {

            if (visited[w->adjindex] == 0)
            {
                visited[w->adjindex] = 1;
                q.push(w->adjindex);
                cnt++;
                tail = w->adjindex;
            }
        }
        if(temp == last)
        {
            level++;
            last = tail;
        }
        if(level == 6)
        {
            break;
        }


    }
    return cnt;
}

void initVisit(int visited[])
{
    for(int i = 0; i < 10000; i++)
    {
        visited[i] = 0;
    }
}

int main()
{
    LGraph graph = BuildGraph();
    int visited[10000];

    for(vertex i = 1; i <= graph -> nv; i++)
    {
        initVisit(visited);

        int cnt = BFS(graph, i, visited);

        printf("%d: ", i);
        printf("%.2f%%\n", (100.0*cnt)/graph->nv);
    }
}

自己解决问题

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

#define MAXN 10001 
//建立图
int G[MAXN][MAXN] = {0},n,m;//n是节点数，m是边数
int visited[MAXN] ={0};//初始化的访问列表 

void isinvisited();
int BFS(int v);

int main()
{
    //freopen("test.txt", "r", stdin); 
    int i,v1,v2;//注意节点从1到N编号，图是从0开始的 
    scanf("%d %d",&n,&m);
    for( i=0; i<m; i++)
    {
        scanf("%d %d",&v1,&v2);
        v1--;
        v2--;
        G[v1][v2] = 1;
        G[v2][v1] = 1;
    }

    int v;
    int count;
    double ratio;
    for( v=0; v<n; v++)
    {
        isinvisited();
        count = BFS(v);
        ratio = count * 1.0  / n * 100;
        printf("%d: %.2lf%%\n",v+1,ratio);//%%才能输出百分号 
    }

    return 0; 
}

void isinvisited()
{
    int i;
    for(i=0; i<n; i++){
        visited[i] = 0;
    }

}
int BFS(int v)
{
    //顺序队列 
    const int MAXNUM = 10002;
    int queue[MAXNUM];
    int first = -1,rear = -1;

    int count,level,last,tail;

    visited[v] = true;
    count = 1;//这个节点有多少人 
    level = 0;//层数
    last = v;//这一层访问的最后一个节点 
    queue[++rear] = v;//入队 

    while(first < rear) //队列不为空
    {
        int de = queue[++first];//出队
        for(int i=0; i<n; i++)
        {
            if(G[de][i] && !visited[i])
            {
                visited[i] = true;
                queue[++rear] = i;
                count++;
                tail = i; 
            }

        } 
        if(de == last)
        {
            level++;
            last = tail;
        }
        if(level == 6)
        {
            break;
        }
    } 

    return count;   
}