项目作者： daomin-xsy
项目描述 ：
#include #include typedef enum {false, true} bool; #define MaxVertexNum 10 /* 最大顶点数设为10 */ typedef int Vertex; /* 用顶点下标表示顶点,为整型 */ /* 邻接点的定义 */ typedef struct AdjVNode *PtrToAdjVNode; struct AdjVNode{ Vertex AdjV; /* 邻接点下标 */ PtrToAdjVNode Next; /* 指向下一个邻接点的指针 */ }; /* 顶点表头结点的定义 */ typedef struct Vnode{ PtrToAdjVNode FirstEdge; /* 边表头指针 */ } AdjList[MaxVertexNum]; /* AdjList是邻接表类型 */ /* 图结点的定义 */ typedef struct GNode *PtrToGNode; struct GNode{ int Nv; /* 顶点数 */ int Ne; /* 边数 */ AdjList G; /* 邻接表 */ }; typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */ bool Visited[MaxVertexNum]; /* 顶点的访问标记 */ LGraph CreateGraph() { int i, k, VertexNum; Vertex V, E1, E2; LGraph Graph; printf("输入顶点的个数："); scanf("%d", &VertexNum); Graph = (LGraph)malloc (sizeof(struct GNode)); Graph->Nv = VertexNum; Graph->Ne = 0; for(V = 0; V < Graph->Nv; V ++) { Graph->G[V].FirstEdge = NULL; } printf("输入边的个数："); scanf("%d", &(Graph->Ne)); if(Graph->Ne) { for(i = 0; i < Graph->Ne; i ++) { scanf("%d %d", &E1, &E2); //插入边 PtrToAdjVNode NewNode; NewNode = (PtrToAdjVNode)malloc (sizeof(struct AdjVNode)); NewNode->AdjV = E2; NewNode->Next = Graph->G[E1].FirstEdge; Graph->G[E1].FirstEdge = NewNode; //无向图，所以还是插入边 NewNode = (PtrToAdjVNode)malloc (sizeof(struct AdjVNode)); NewNode->AdjV = E1; NewNode->Next = Graph->G[E2].FirstEdge; Graph->G[E2].FirstEdge = NewNode; } } return Graph; } void Visit( Vertex V ) { printf(" %d", V); } void BFS ( LGraph Graph, Vertex S, void (*Visit)(Vertex) ) { int queue[11]; //定义一个队列 int l = 0, r = 0; queue[r++] = S; Visit(S); Visited[S] = true; PtrToAdjVNode tmp; while(l != r) //队列不为空 { tmp = Graph->G[queue[l++]].FirstEdge; while(tmp) { Vertex pos = tmp->AdjV; if(!Visited[pos]) { Visit(pos); Visited[pos] = true; queue[r++] = pos; } tmp = tmp->Next; } } } int main() { LGraph G; Vertex S; G = CreateGraph(); scanf("%d", &S); printf("BFS from %d:", S); BFS(G, S, Visit); return 0; }
高级语言：
项目地址: git://github.com/daomin-xsy/11.5.git