邻接矩阵表示的无向图深度遍历算法实现

邻接表表示的无向图深度遍历算法实现

克鲁斯卡尔算法 O(eloge) 适合稀疏图

图的遍历

①图的遍历：从图的某一顶点出发，遍历图中的其余顶点，且每个顶点仅被访问一次
复杂性：图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点
②解决办法：在遍历过程中记下已被访问过的顶点。设置一个辅助向量Visited[1…n](n为顶点数)，其初值为0，一旦访问了顶点vi后，使Visited[i]为1或为访问的次序号
③图的遍历算法有深度优先搜索算法和广度优先搜索算法。采用的数据结构是(正)邻接链表

深度优先遍历

连通图的深度优先遍历类似于树的先根遍历

深度优先遍历连通图

bool visited[MVNum];        //访问标志数组，其初值为"false"\
void DFS(Graph G,int v){
    //从第v个顶点出发递归地深度优先遍历图G
    cout<<v;    visited[v]=true;    //访问第v个顶点，并置访问标志数组相应分量值为true
    for(w=FirstAdjVex(G,u);w >= 0;w=NextAdjVex(G,u,W))
            //依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接点
            //NextAdjVex(G,u,w)表示u相对于w的下一个邻接点,w>=0表示存在邻接点
        if(!visited[w])    DFS(G,w);    
}

深度优先遍历非连通图

void DFSTraverse(Graph G){
    //对非连通图G做深度优先遍历
    for(v=0;v<G.vexnum;++v)    visited[v] = false;    //标志数组初始化
    for(v=0;v<G.vexnum;++v)
        if(!visited[v])    DFS(G,v)
}

邻接矩阵表示的无向图深度遍历算法实现

创建辅助数组visited[n]用来标记顶点是否被访问

void DFS(AMGraph G,int v){
    cout<<v; visited[v] = true;    //访问第v个顶点
    for(w=0;w < G.vexnum;w++)    //依次检查邻接矩阵v所在的行
        if((G.arcs[v][w] != 0)&&(!visited[w]))
            DFS(G,w);
        //w是v的邻接点，如果w未访问，则递归调用DFS
}

邻接表表示的无向图深度遍历算法实现

void DFS_AL(ALGraph G, int v){
    //图G为邻接表类型，从第v个顶点深度优先遍历图G
    cout<<v; visited[v]=true;        //访问第v个顶点，并置访问标志数组相应分量值为true
    p = G.vertices[v].firstarc;    //p指向v的边链表的第一个边结点
    while(p != NULL){
        w = p->adjvex;            //w是v的邻接点
        if(!visited[w]) DFS_AL(G,w);
        p = p->nextarc;
    }
}

①用邻接矩阵来表示图，遍历图中每一个顶点都要从头扫描该顶点所在行，时间复杂度为O(n^2)

②用邻接表表示图，虽然有2e个表结点，但只需扫描e个结点即可完成遍历，加上访问n个头结点的时间，时间复杂度为O(n+e)

③稠密图适合于在邻接矩阵上进行深度遍历

稀疏图适合于在邻接表上进行深度遍历

广度优先遍历

按照广度优先非递归遍历连通图G

void BFS(Graph G,int v){    //按广度优先非递归遍历连通图G
    cout<<v;visited[v] = true;    //访问第v个顶点
    InitQueue(Q);            //辅助队列Q初始化，置空
    EnQueue(Q,v);            //v入队
    while(!QueueEmpty(Q)){    //队列非空
        DeQueue(Q,u);         //队头元素出队并置为u
        for(w=FirstAdjVex(G,u);w >= 0;w=NextAdjVex(G,u,W))
            //依次检查u的所有邻接点w，FirstAdjVex(G,u)表示u的第一个邻接点
            //NextAdjVex(G,u,w)表示u相对于w的下一个邻接点,w>=0表示存在邻接点
        if(!visited[w]){        //w为u的尚未访问的邻接顶点
            cout<<w; visited[w]=true;    EnQueue(Q,w);    //w进队
        }
    }
}

①当用邻接矩阵存储时，时间复杂度为O(n^2)

②用邻接表存储时，时间复杂度为O(n+e)

DFS和BFS的算法效率比较

①空间复杂度相同，都是O(n)

②时间复杂度只与存储结构有关，与搜索路径无关

图的应用

最小生成树

生成树：所有顶点均由边连接在一起，但不存在回路的图

所有生成树的特点：①生成树的顶点个数与图的顶点个数相同

②生成树是图的极小连通子图，去掉一条边则非连通

③在生成树中再加一条边必然形成回路

④一个有n个顶点的连通图的生成树有n-1条边

⑤生成树中任意两个顶点间的路径是唯一的

最小生成树：给定一个无向网，在该网的所有生成树中，带权连通图中代价最小的生成树称为最小生成树

Prim算法 O(n^2) 适合稠密图

依次向下寻找顶点，并添加该顶点到下一个顶点的最小权值的边

克鲁斯卡尔算法 O(eloge) 适合稀疏图

最短路径

在有向带权图中，从一点到另一点的权值最小的路径或者是非带权图中边数最少的路径

迪杰斯特拉算法 O(n^2)

单源最短路径（从一个顶点到其他顶点的路径）

弗洛伊德算法 O(n^3)

求图中各顶点之间最短路径

void ShortestPath_Floyd(AMGraph G){
        //用Floyd算法求有向网G中各对顶点i和j之间的最短路径
    for(i=0;i < G.vexnm;;++i=
        for(j=0;j < G.vexnum;++j){
            D[i][j] = G.arcs[i][j];
            if(D[i][j] < MaxInt && i != j)  Path[i][j]=i;
            else Path[i][j] = -1;
        }
    for(k=0;k < G.vexnum;++k)
        for(i=0;i < G.vexnum;++i)
            for(j=0;j < G.vexnum;++j=
                if(D[i][j]+D[k][j] < D[i][j] = 
                    D[i][j]=D[i][k]+D[k][j];
                    Path[i][j] = Path[k][j];
                }
}