使用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);
}
}
