输入的图是:
0 4
0 5
0 1
0 2
2 3
1 3
5 6
权重都是1
输出中3号节点没有被访问而且报错了
#include "Gragh-link.h"
#include "Queue.h"
#include "stdbool.h"
Gragh Initialize(int VerNum){
Gragh G = (Gragh)malloc(sizeof(struct LGragh));
G->Nv = VerNum;
G->Ne = 0;
for (int i = 0;i < G->Nv-1;i++)
{
G->NodeList[i].First = NULL;
}
return G;
}
void InsertEdge(Gragh G,Edge E)
{
PtrToAdjNode NewNode0 = (PtrToAdjNode)malloc(sizeof(struct AdjNode));
NewNode0->Weight = E->Weight;
NewNode0->VAdj = E->V2;
//下面开始插入,插到表头后面
NewNode0->Next = G->NodeList[E->V1].First;
G->NodeList[E->V1].First = NewNode0;
//若为无向图,还要执行以下代码
PtrToAdjNode NewNode1 = (PtrToAdjNode)malloc(sizeof(struct AdjNode));
NewNode1->Weight = E->Weight;
NewNode1->VAdj = E->V1;
NewNode1->Next = G->NodeList[E->V2].First;
G->NodeList[E->V2].First = NewNode1;
}
Gragh BuildGragh(){
int Nv,Ne;
Edge E;
do
{
printf("Please enter a number less than 100:");
scanf("%d",&Nv);
} while (Nv >= 100);
Gragh G = Initialize(Nv);
printf("Input the number of edges:");
scanf("%d",&Ne);
G->Ne = Ne;
if (G->Ne != 0)
{
E = (Edge)malloc(sizeof(struct ENode));
printf("please add edges for your gragh.format:Vec1 Vec2 Weight.\n");
for (int i = 0;i < G->Ne;i++)
{
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight);
InsertEdge(G,E);
}
}
/*以下是可选的数据录入*/
//printf("Please add data for each vertex.");
//for (int i = 0;i < G->Nv;i++)
//{
// scanf("%s",G->NodeList[i].data[i]);
//}
return G;
}
PtrToQ queue_init()
{
PtrToQ q = (PtrToQ)malloc(sizeof(struct queue));
q->front = q->rear = 0;
return q;
}
int queue_empty(PtrToQ q)
{
return q->front == q->rear;
}
int queue_en(PtrToQ q, datatype e)
{
/* 队满 */
if (q -> rear == MAX_QUEUE_SIZE)
return false;
/* 入队 */
q -> sp_queue_array[q -> rear] = e;
q -> rear += 1;
return true;
}
datatype queue_de(PtrToQ q)
{
/* 队空 */
if(queue_empty(q))
return false;
/* 出队 */
datatype element = q->sp_queue_array[q->front];
q->front += 1;
return element;
}
void queue_clear(PtrToQ q)
{
q -> front = q -> rear = 0;
}
int queue_len(PtrToQ q)
{
return (q->rear - q->front);
}
void queue_traverse(PtrToQ q, void (*visit)(PtrToQ q))
{
visit(q);
}
void visit(PtrToQ q)
{
/* 队空 */
if (q->front == q->rear)
printf("队列为空\n");
int temp = q->front;
while(temp != q->rear)
{
printf("%d ",q->sp_queue_array[temp]);
temp += 1;
}
printf("\n");
}
bool visited[MaxVerNum];
void visiting(Vertex V);
int main(){
for (int i = 0;i < MaxVerNum;i++)
visited[i] = false;
Gragh G = BuildGragh();
BFS(G,0,visiting);
system("pause");
return 0;
}
void BFS(Gragh G,Vertex V, void (*visiting)(Vertex));
void visiting(Vertex V){
printf("visiting vertex %d now.",V);
}
void BFS(Gragh G,Vertex V, void (*visiting)(Vertex)){
PtrToAdjNode S,W;
PtrToQ Q = queue_init();
queue_en(Q,V);
while (!queue_empty(Q))
{
V = queue_de(Q);
visiting(V);
visited[V] = true;
S = G->NodeList[V].First;
while (S)
{
if (!visited[S->VAdj])
queue_en(Q,S->VAdj);
S = S->Next;
}
}
}