图

邻接矩阵法

#define MaxVertexNum 100
typedef char VertexType //顶点的数据类型
typedef int EdgeType    //边的数据类型
typedef struct{
    VertexType Vex[MaxVertexNum];
    EdgeType Edge[MaxVertexNum][MaxVertexNum];
    int vexnum,arcnum;  //当前顶点数和弧数
}MGraph;

邻接表法

typedef struct ArcNode{ //定义边表结点
    int adjvex;         //该弧所指向的顶点位置
    struct ArcNode *next;   //指向下一条弧的指针
}ArcNode;
typedef struct VNode{   //定义顶点表结点
    VertexType data;    //顶点信息
    ArcNode *first;     //指向第一条依附顶点的弧的指针
}VNode,AdjList[MaxVertexNum];
typedef struct{         
    AdjList vertices;   //邻接表
    int vexnum,arcnum;  //图顶点数和弧数
}ALGraph;

BFS

bool visited[MaxVertexNum];
void BFSTraverse(Graph G){
    for(int i = 0;i < G.vexnum;++i)
        visited[i] = false;
    InitQueue(Q);
    for(int i = 0;i < G.vexnum;++i)
        if(!visited[i])     BFS(G,i);
}
void BFS(Graph G,int v){
    visit(v);
    visited[v] = true;
    EnQueue(Q,v);
    while(!IsEmpty(Q)){
        DeQueue(Q,v);
        for(w = FirstNeighbor(G,v);w >= 0;w = NextNeighbor(G,v,w))
            if(!visited[w]){
                visit(w);
                visited[w] = true;
                EnQueue(Q,w);
            }
    }
}

BFS求最短路径

void BFS_mindistance(Graph G,int u){    //d[i]表示u到i结点的最短路径
    for(int = 0;i < G.vexnum;++i)
        d[i] = ∞;
    visited[u] = true;
    d[u] = 0;
    EnQueue(Q,u);
    while(!IsEmpty(Q)){
        DeQueue(Q,u);
        for(int w = FirstNeighbor(G,u);w >= 0;w = NextNeighbor(G,u,w))
            if(!visited[w]){
                visited[w] = true;
                d[w] = d[u]+1;
                EnQueue(Q,w);
            }
    }
}

DFS

bool visited[MaxVertexNum];
void DFSTraverse(Graph G){
    for(int v = 0;v < G.vexnum;++v)
        visited[v] = false;
    for(int v = 0;v < G.vexnum;++v)
        if(!visited[v])     DFS(G,v);
}
void DFS(Graph G,int v){
    visit(v);
    visited[v] = true;
    for(int w = FirstNeighbor(G,v);w >= 0;w = NextNeighbor(G,v,w))
        if(!visited[w])     DFS(G,w);
}