yuAriellexi
yuAriellexi
采纳率52.4%
2019-05-21 09:34

06-图3 六度空间 无法debug

10
已采纳

使用debug, 在q.push(i)无法下一步,报错


#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, 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 newnode1 = new adjnode;
    newnode1 -> adjindex = e -> v2;

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

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

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

    scanf("%d", &(graph->ne));
    getchar();
    if(graph -> ne != 0)
    {
        e = new edgenode;
        for(v = 0; v < graph -> ne; v++)
        {
            scanf("%d %d", &e->v1, &e->v2);
            getchar();
            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();
        adjnode* w = graph->G[temp].firstedge;//指向i的第一个邻接结点
        while(w != NULL)
        {
            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;
            }
            w = w -> next;
        }
    }
    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);
    }
}
  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • yuAriellexi yuAriellexi 2年前
    
    #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);
        }
    }
    
    
    
    

    自己解决问题

    点赞 评论 复制链接分享
  • dabocaiqq dabocaiqq 2年前
    #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;   
    }
    
    
    点赞 评论 复制链接分享

为你推荐