Last active
August 29, 2015 13:59
-
-
Save tinylamb/10953940 to your computer and use it in GitHub Desktop.
Revisions
-
tinylamb revised this gist
Apr 17, 2014 . 1 changed file with 121 additions and 10 deletions.There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -8,7 +8,7 @@ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include "queue.h" //定义邻接表 typedef struct arcnode{ @@ -28,16 +28,18 @@ void addEdge(Graph *g , int v , int w); void DFSUtil(Graph *g , int v , bool visited[]); //DFS v的可达顶点 void DFS(Graph *g ,int v );//DFS 遍历全图 void BFS(Graph *g);//BFS 遍历全图 int main(){ Graph gra ; InitialGraph( &gra , 4); addEdge(&gra , 0 ,3); addEdge(&gra , 0 ,2); addEdge(&gra , 3 ,2); addEdge(&gra , 2 ,0); addEdge(&gra , 2 ,1); addEdge(&gra , 1 ,1); DFS(&gra , 3); BFS(&gra); return 0; } @@ -78,9 +80,118 @@ void DFS(Graph *g , int v){ visited[i] = false; DFSUtil(g , v ,visited); for (int i=0 ; i< g->vernum ;i++){ if (!visited[i]) DFSUtil(g , i , visited); } } void BFS(Graph *g){ bool *visited = malloc(g->vernum * sizeof(bool)); for(int i = 0; i < g->vernum ; i++) visited[i] = false ; Queue q; InitQueue(&q ,(unsigned)g->vernum); for(int i = 0; i < g->vernum ;i++){ if (!visited[i]){ //遍历i的可达顶点 printf("%d ",i); visited[i] = true; InQueue(&q , i); while(!IsEmpty(&q)){ int v = DeQueue(&q); ArcNode *p = (g->ver + v)->next; while(p){ if (!visited[p->arc]){ printf("%d ",p->arc); visited[p->arc] = true; InQueue(&q , p->arc); } p = p->next; } } } } } /* * ===================================================================================== * * Filename: queue.h * * Description: 整数循环队列头文件说明 * * Version: 1.0 * Created: 2014/04/17 14时46分22秒 * Revision: none * Compiler: gcc * * Author: YOUR NAME (), * Organization: * * ===================================================================================== */ typedef struct queue{ int *array; unsigned size; int head,tail; }Queue; extern void InitQueue(Queue *q , unsigned qsize); extern bool IsEmpty(Queue *q); extern bool IsFull(Queue *q); extern void InQueue(Queue *q , int elem); extern int DeQueue(Queue *q); /* * ========================================================= * Filename: queue.c * Description: 整数循环队列操作的实现 * * ========================================================= */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <assert.h> #include "queue.h" void InitQueue(Queue *q , unsigned qsize){ q->size = qsize; q->array = malloc(qsize * sizeof(int)); q->head = q->tail = 0; } bool IsEmpty(Queue *q){ return (q->head == q->tail)?true:false; } bool IsFull(Queue *q){ return ((q->tail + 1) % q->size == q->head)?true:false; } void InQueue(Queue *q , int elem){ assert(!IsFull(q)); q->array[q->tail] = elem; q->tail = (q->tail + 1) % q->size; } int DeQueue(Queue *q){ assert(!IsEmpty(q)); int e = q->array[q->head]; q->head = (q->head + 1) % q->size; return e; } /*makefile. make -f makefile*/ adjlist: adjlist.o queue.o clang adjlist.o queue.o -o adjlist adjlist.o: adjlist.c queue.h clang -c adjlist.c queue.o: queue.c queue.h clang -c queue.c -
Apr 17, 2014 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,86 @@ /* * ========================================================= * Filename: adjlist.c * Description: 图的邻接表表示及各种操作 * * ========================================================= */ #include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define VERMAX 20 //定义邻接表 typedef struct arcnode{ int arc ;//邻接顶点值 struct arcnode *next ; //指向下一个邻接顶点 }ArcNode ,*AdjList ; typedef struct graph{ AdjList ver ; //ver是 arcnode类型数组，存储顶点及邻接信息 int vernum ; //顶点个数 }Graph; //根据图创建对应的邻接表,输入arc对(v , w) ArcNode *newArc(int v); void InitialGraph(Graph *g ,int vnum); //也就是类中的Constructor void addEdge(Graph *g , int v , int w); void DFSUtil(Graph *g , int v , bool visited[]); //DFS v的可达顶点 void DFS(Graph *g ,int v );//DFS 遍历全图 int main(){ Graph gra ; InitialGraph( &gra , 4); addEdge(&gra , 0 ,1); addEdge(&gra , 0 ,2); addEdge(&gra , 1 ,2); addEdge(&gra , 2 ,0); addEdge(&gra , 2 ,3); addEdge(&gra , 3 ,3); DFS(&gra , 2); return 0; } ArcNode *newArc(int v){ ArcNode *n = malloc(sizeof(ArcNode)); n->arc = v; n->next = NULL; return n; } void InitialGraph( Graph *g ,int vnum){ g->vernum = vnum; g->ver = malloc(vnum * sizeof(ArcNode)); } void addEdge(Graph *g , int v , int w){ //脑子里有清晰的创建过程 // ArcNode vertex = g->ver[v]; ArcNode *n = newArc(w); // ArcNode *p = &vertex ; ArcNode *p = g->ver + v; while ( p->next ) p = p->next; p->next = n; } void DFSUtil(Graph *g , int v , bool visited[]){ visited[v] = true; printf("%d ",v); ArcNode *p = g->ver[v].next; while (p){ if (!visited[p->arc]) DFSUtil(g ,p->arc ,visited); p = p->next; } } void DFS(Graph *g , int v){ bool *visited = malloc(g->vernum * sizeof(bool)); for (int i=0 ; i< g->vernum ;i++) visited[i] = false; DFSUtil(g , v ,visited); /* for (int i=0 ; i< g->vernum ;i++){ * if (!visited[i]) * DFSUtil(g , i , visited); * } */ }