06-图3 六度空间 (30分)
程序员文章站
2024-01-19 16:54:52
...
06-图3 六度空间 (30分)
思路分析:这里主要列举一下自己犯的错误,因为这个题目要求每一个结点都要BFS,所以说每一个结点BFS之前都要将Visited数组初始化为没有访问的状态,我忘记了,所以运行一直是错误。还要注意的是,这里是从1开始的,所以Visited数组存储最好也从1开始。之所以这里选择邻接表的存储方式,是因为由题意得知 N*(N-1)=N*33,N解出来等于67,所以当N越大,M也就越小,所以这是一个 稀疏图,用邻接表的方式最好。
代码写得有点零乱…
#include<iostream>
#include<iomanip>
#include<queue>
#define MaxSize 1001
using namespace std;
//邻接点
typedef struct VNode* PtrToVNode;
struct VNode
{
PtrToVNode Next;
int Data;
};
typedef PtrToVNode AdjNode;
//边
typedef struct ENode
{
int V1,V2;
}*Edge;
//顶点表
typedef struct VNodes
{
AdjNode FirstEdge;
}AdjList[MaxSize];
//图结构
typedef struct Graphs
{
AdjList G;
int Nv,Ne;
}*LGraph;
LGraph CreateGraph(int VertexNum);
LGraph BuildGraph();
void InsertEdge(LGraph Graph,Edge E);
int BFS(LGraph Graph, int n);
void IniVisited();
int* Visited = new int[MaxSize];
int main()
{
LGraph Graph;
Graph = BuildGraph();
int i;
double count;
for(i = 1;i<=Graph->Nv;i++)
{
IniVisited();
count = BFS(Graph,i);
cout <<i<<":"<<" ";
cout<<setiosflags(ios::fixed) <<setprecision(2)<<(count/Graph->Nv)*100<<"%"<<endl;
}
return 0;
}
LGraph CreateGraph(int VertexNum)
{
LGraph Graph;
Graph = new Graphs;
Graph->Nv = VertexNum;
Graph->Ne = 0;
int i;
for(i = 1;i<=Graph->Nv;i++)
Graph->G[i].FirstEdge = NULL;
return Graph;
}
void InsertEdge(LGraph Graph,Edge E)
{
AdjNode NewNode;
NewNode = new VNode;
NewNode->Data = E->V2;
NewNode->Next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;
NewNode = new VNode;
NewNode->Data = E->V1;
NewNode->Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}
LGraph BuildGraph()
{
LGraph Graph;
Edge E;
int VertexNum,EdgeNum;
cin >> VertexNum >> EdgeNum;
Graph = CreateGraph(VertexNum);
Graph->Ne = EdgeNum;
int i;
if(EdgeNum!=0)
{
E = new ENode;
for(i=0;i<Graph->Ne;i++)
{
cin >> E->V1 >> E->V2;
InsertEdge(Graph,E);
}
}
return Graph;
}
int BFS(LGraph Graph, int n)
{
AdjNode p;
Visited[n] = 1;
queue<int>Q;
int Value,count = 1;
int last = n,tail,level = 0;
Q.push(n);
while(!Q.empty())
{
Value = Q.front();
Q.pop();
for(p = Graph->G[Value].FirstEdge;p;p = p->Next)
if(Visited[p->Data]==0)
{
Visited[p->Data]=1;
Q.push(p->Data);
count++;
tail = p->Data;
}
if(Value==last)
{
level++;
last=tail;
}
if(level==6) break;
}
return count;
}
void IniVisited()
{
int i;
for(i = 0;i<MaxSize;i++)
Visited[i] = 0;
}
保留两位小数的办法:!!
上一篇: 急死人。
下一篇: php新手提问.几个简单有关问题