最近学习图论，课程片中理论。但是，觉得还是实现一下好。就根据书上的写了图的BFS和DFS搜索算法。

1.图的实现，邻接链表。

#include<stdlib.h>

typedef struct {int u;int v;} edge;
struct node{int v;struct node * next;}; 
struct graph{int nv;int ne;struct node ** adj;};
typedef struct graph * Graph;

Graph init(int n){
    Graph g=malloc(sizeof *g);// sizeof graph

    g->nv=n;
    g->ne=0;
    g->adj=malloc((sizeof *(g->adj))*n);
    int i;
    for(i=0;i<g->nv;i++)
        g->adj[i]=NULL;
    
    return g;
}

void insert(Graph g,edge e){
    int u,v;

    u=e.u;
    v=e.v;
    
    struct node* unode=malloc(sizeof *unode);
    unode->v=v;
    unode->next=g->adj[u];

    g->adj[u]=unode;

    struct node* vnode=malloc(sizeof *vnode);
    vnode->v=u;
    vnode->next=g->adj[v];

    g->adj[v]=vnode;

    g->ne++;
}

2.队列实现。

#include<stdlib.h>

static int maxsize=0;
static int front=0;
static int rear=0;
int * queue;

int * initq(int max){
    maxsize=max+1;
    queue=malloc(sizeof(int)*maxsize);
    front=rear=0;
    return queue;
}

int add(int * q,int v){
    if((rear+1)%maxsize==front)
        return -1;
    rear=(rear+1)%maxsize;
    q[rear]=v;
    return v;
}

int delete(int *q){
    if(front==rear)
        return -1;
    front=(front+1)%maxsize;
    return q[front];
}

int isempty(){
    return (front==rear)?1:0;
}

3.搜索算法。

#include<stdlib.h>
#include<stdio.h>
#include"graph.c"
#include"queue.c"
/*bfs,dfs algos. from "introduction to algos".
*/

#define MAXV 1000   
#define BIG  (MAXV+1)
#define NUM 100
int color[MAXV];
int d[MAXV];
int p[MAXV];
int f[MAXV];
enum cl {WHITE,GRAY,BLACK};
int * q;
int time;

void bfs(Graph g,int s){
    int i;

    for(i=0;i<g->ne;i++){
        color[i]=WHITE;
        d[i]=-1;
        p[i]=-1;
    }
    color[s]=GRAY;
    d[s]=0;
    p[s]=-1;

    q=initq(NUM);
    add(q,s);

    while(!isempty()){
        int u;
        u=delete(q);
        printf("%d u \n",u);
        struct node * vnode=g->adj[u];
        while(vnode){
            int v;
            v=vnode->v;
            if(color[v]==WHITE){
                color[v]=GRAY;
                d[v]=d[u]+1;
                p[v]=u;
                add(q,v);
            }
            vnode=vnode->next;
        }
        color[u]=BLACK;
    }
}

void dfsv(Graph g,int u){
    color[u]=GRAY;
    time++;
    d[u]=time;
    struct node * vnode;
    vnode=g->adj[u];
    while(vnode){
        int vv;
        vv=vnode->v;
        if(color[vv]==WHITE){
            p[vv]=u;
            dfsv(g,vv);
        }
        vnode=vnode->next;
    }
    color[u]=BLACK;
    time++;
    f[u]=time;
}

void dfs(Graph g){
    int i,v;

    v=g->nv;
    for(i=0;i<v;i++){
        color[i]=WHITE;
        p[i]=-1;
    }
    time=0;
    for(i=0;i<v;i++){
        if(color[i]==WHITE)
            dfsv(g,i);
    }
}


void printpath(Graph g,int s,int v){
    if(v==s)
        printf("%d ",s);
    else if(p[v]==-1)
        printf("no path from s to v\n");
    else
        {
            printpath(g,s,p[v]);
            printf("%d ",v);
        }
}

int main(){
    Graph  g;
    int n=5;
    g=init(n);

    edge e[7];
    e[0].u=0;e[0].v=1;
    e[1].u=0;e[1].v=3;
    e[2].u=1;e[2].v=2;
    e[3].u=1;e[3].v=3;
    e[4].u=1;e[4].v=4;
    e[5].u=2;e[5].v=4;
    e[6].u=3;e[6].v=4;

    int i;
    for(i=0;i<7;i++)
        insert(g,e[i]);
    bfs(g,0);
    printpath(g,0,4);
    printf("\n");
    dfs(g);
    printpath(g,0,4);
    printf("\n");
    
    return 0;
}

CODE过程中，指针的出错还是有，一定要注意动态分配内存的问题，在这个地方很容易出错。还有就是指向指针的指针问题。对于C来说，指针部分得多练多想呀！不知道，谁有好的理解。