2019-05-21 09:34

# 06-图3 六度空间 无法debug

10

``````
#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 vertexnode
{

//定义图，用邻接表表示图
typedef struct graphnode* Ptr2graphnode;
struct graphnode
{
int nv;
int ne;
};
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是指向邻接点的指针
newnode1 -> adjindex = e -> v2;

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

//newnode2是指向邻接点的指针
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;
}

/*

*/
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();
while(w != NULL)
{
{
cnt++;
}
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 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 vertexnode
{

//定义图，用邻接表表示图
typedef struct graphnode* Ptr2graphnode;
struct graphnode
{
int nv;
int ne;
};
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是指向邻接点的指针
newnode2 -> adjindex = e -> v2;

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

//newnode2是指向邻接点的指针
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)
{

{
cnt++;
}
}
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 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;
}

``````
点赞 评论 复制链接分享