図の遍歴(保持1)
3289 ワード
問題の説明:
関数の説明:
試験用図:
/*
01.
02.
03.*Copyright(c) 2015,
04.*All rights reserved.
05.* : 111.cpp
06.* : **
07.* :2015 11 16
08.* :V1.0
09.*
10.* :
11.* :
*/
関数の説明:
:
#ifndef GRAPH_H_INCLUDED
#define GRAPH_H_INCLUDED
#define MAXV 100 //
#define INF 32767 //INF ∞
typedef int InfoType;
//
typedef struct
{
int no; //
InfoType info; // ,
} VertexType; //
typedef struct //
{
int edges[MAXV][MAXV]; //
int n,e; // ,
VertexType vexs[MAXV]; //
} MGraph; //
//
typedef struct ANode //
{
int adjvex; //
struct ANode *nextarc; //
InfoType info; // ,
} ArcNode;
typedef int Vertex;
typedef struct Vnode //
{
Vertex data; //
int count; // ,
ArcNode *firstarc; //
} VNode;
typedef VNode AdjList[MAXV]; //AdjList
typedef struct
{
AdjList adjlist; //
int n,e; // n e
} ALGraph; //
// : ,
// :Arr - , , Arr ( int )
// n -
// g -
void ArrayToMat(int *Arr, int n, MGraph &g); //
void ArrayToList(int *Arr, int n, ALGraph *&); //
void MatToList(MGraph g,ALGraph *&G);// g G
void ListToMat(ALGraph *G,MGraph &g);// G g
void DispMat(MGraph g);// g
void DispAdj(ALGraph *G);// G
#endif // GRAPH_H_INCLUDED
:
#include <stdio.h>
#include <malloc.h>
#include "graph.h"
void BFS(ALGraph *G, int v)
{
ArcNode *p;
int w,i;
int queue[MAXV],front=0,rear=0; //
int visited[MAXV]; //
for (i=0; i<G->n; i++) visited[i]=0; //
printf("%2d",v); //
visited[v]=1; //
rear=(rear+1)%MAXV;
queue[rear]=v; //v
while (front!=rear) //
{
front=(front+1)%MAXV;
w=queue[front]; // w
p=G->adjlist[w].firstarc; // w
while (p!=NULL)
{
if (visited[p->adjvex]==0)
{
printf("%2d",p->adjvex); //
visited[p->adjvex]=1;
rear=(rear+1)%MAXV; //
queue[rear]=p->adjvex;
}
p=p->nextarc; //
}
}
printf("
");
}
int main()
{
ALGraph *G;
int A[5][5]=
{
{0,1,0,1,0},
{1,0,1,0,0},
{0,1,0,1,1},
{1,0,1,0,1},
{0,0,1,1,0}
};
ArrayToList(A[0], 5, G);
printf(" 2 :");
BFS(G, 2);
printf(" 0 :");
BFS(G, 0);
return 0;
}
試験用図: