携手创造，共同生长！这是我参与「日新方案 8 月更文应战」的第12天，点击查看活动详情

介绍

在数据结构中，树和图能够说是不可或缺的两种数据结构。其中，关于图来说，最重要的算法能够说便是遍历算法。而查找算法中，最标志性的便是深度优先算法和广度优先算法。

图的定义

图的定义普遍为两种，一种是邻接表，另一种是邻接矩阵。 图的邻接矩阵表示是仅有的，但关于邻接表来说，若边的输入次序不同生成的邻接表也不同。因而，关于同一个表，基于邻接矩阵的遍历所得到的BFS序列和DFS序列是不仅有的，基于邻接表的遍历所得到的BFS和DFS是仅有的。

邻接表

#define MXNUM 100
typedef char VertexType;
typedef int EdgeType;
typedef struct VNode
{
    VertexType data;
    ArcNode *first;
}VNode,AdjList[MXNUM];
typedef struct{
    AdjList vertics;
    int vexnum,arcnum;
}ALGraph;

邻接矩阵

#define MXNUM 100
typedef char VertexType;
typedef int EdgeType;
typedef struct 
{
    VertexType  Vex[MXNUM];
    EdgeType    Edge[MXNUM][MXNUM];
    int Vexnum,Edgenum;
}MGraph;
typedef struct ArcNode{
    int adjvex;
    struct ArcNode *next;
}ArcNode;

广度优先算法

广度优先算法的完成

广度优先算法是一种分层的查找过程，每向前走一步可能会拜访一批极点，不像深度优先查找算法那样有回溯的情况，因而它不是一个递归的算法。为了完成逐层拜访，算法有必要借助一个辅佐队列，以回忆正在拜访的极点的下一层极点。

void BFSTraverse(MGraph G)
{
    int i;
    for(i=0;i<G.Vexnum;++i)
    {
        visited[i]=false;
    }
    InitQueue(Q);
    for(i=0;i<G.Vexnum;++i)
    {
        if(!visited[i])
        BFS(G,i);
    }
}
void BFS(MGraph G,int v)
{
    visit(v);
    visited[v]=true;
    enqueue(Q,v);
    while(!Empty(Q))
    {
        Dequeue(Q,v);
    for(int w=firstNeighbor(v);w>=0;w=NextNeighbor(G,w,v))
    {
        if(!visited[w])
        {
            visit(w);
            visited[w]=true;
            enqueue(Q,w);
        }
    }
    }
}

无论是邻接表还是邻接矩阵存储图，广度优先算法的空间复杂度都是O（n）。
选用邻接表存储方法时，每个极点均需要查找一次，故时刻复杂度O(|V|)，在查找恣意节点的邻接点时，每条边至少拜访一次，故时刻复杂度为O(E)，算法总时刻复杂度为O(E+V)。选用邻接矩阵存储时，时刻复杂度为O(V*V)。

广度优先算法的运用

广度优先算法在很多求解问题的最优解方面有很好的运用，下面以求图中某一结点的单源最短途径为例。
算法思路：求某一结点的单源最短途径，能够运用广度优先算法，每向外查找一层，途径+1。全部查找完后，就能够得到所求节点到一切节点的途径。

void MIN_Distance(MGraph G,int v)
{
    for(i=0;i<G.Vexnum;i++)
    dis[i]=&;
    visited[v]=true;
    dis[v]=0;
    Enqueue(Q,v);
    while(!Empty(Q))
    {
        Dequeue(Q,v);
        for(w=firstNeighbor(G,v);w>=0;w=nextNeighbor(G,v,w))
        {
            if(!visited[w])
            {
                visited[w]=true;
                dis[w]=dis[v]+1l;
                Enqueue(Q,w);
            }
        }
    }
}

能够看出来，其实便是将简略的广度优先算法的变型。

深度优先算法

深度优先算法的完成

图的深度优先算法类似于树的先序遍历，DFS算法是一个递归算法，需要借助一个工作栈，故其空间复杂度度为O(V)。
深度优先算法的邻接矩阵的时刻复杂度为O(V*V),邻接表的时刻复杂度为O（V+E）。

void DFSTraverse(MGraph G,int v)
{
    for(int i=0;i<G.Vexnum;++i)
    {
        visited[i]=false;
    }
    for(int i=0;i<G.Vexnum;++i)
    if(!visited[i])
    DFS(G,i);
}
void DFS(MGraph G,int v)
{
    visit(v);
    visited[v]=true;
    for(int w=firstNeighbor(G,v);w>=0;w=nextNeighbor(G,w,v))
    {
        if(!visited[w])
        DFS(G,w);
    }
}

后续

图的遍历算法能够用来检索是连通图还对错连通图，只需要进行一次深度优先算法或者广度优先遍历，假如能够遍历一切节点，代表是连通图，假如一次不能遍历一切节点，代表对错连通图。