算法之经典图算法

待我称王封你为后i 2022-06-05 01:28 255阅读 0赞

# 图介绍 #

> 图：是一个顶点集合加上一个连接不同顶点对的边的集合组成。定义规定不允许出现重复边（平行边）、连接到顶点自身的边（自环），定义了一个简单图。  
> 自环：连接到顶点自身的边。  
> 平行边：连接同一对顶点的两条边，含有平行边的图称为多重图。  
> 顶点的度数：依附于它的边的总数。  
> 顶点连通：两个顶点之间存在一条连接双方的路径。  
> 连通图：任意一个顶点都存在一条路径到达另一个任意顶点。  
> 极大连通子图：一个非连通的图由若干个连通图组成，这些连通的图都是极大连通子图。  
> 图的密度：已经连接的顶点对占所有可能被连接顶点对的比例，稀疏图被连接的顶点对较少，稠密图没有被连接的顶点对很少。  
> ![这里写图片描述][SouthEast]  
> ![这里写图片描述][SouthEast 1]  
> 在许多计算机应用中，由相连节点表示的模型很重要。沿着这些连接，能否从一个节点到达另外一个节点？有多少节点和指定的节点相连？两个节点之间最短的链接是哪一条？这些都可以通过图模型解决。这里学习的都是已知的最优美和最有意思的算法。下面图片说明了图应用的广泛性。  
> ![这里写图片描述][SouthEast 2]

# 表示图的数据结构 #

1、邻接矩阵  
当图含有百万个顶点时候，数组需要V\*V存储位，并且需要V\*V步初始化。在稠密图中，这种方式可以承受，因为和邻接表需要差不多的存储空间，但是对于很多顶点的稀疏图，那么就使用邻接表比较合适。  
![这里写图片描述][SouthEast 3]  
2、邻接表  
将每个顶点的所有相连顶点都保存在该顶点对应的元素所指向的一张链表中。  
这种结构可以满足典型应用，所以后面实现的各种图数据结构，都是基于邻接表。优点在于总是使用与V+E成正比空间。  
![这里写图片描述][SouthEast 4]

![这里写图片描述][SouthEast 5]

# 图的两种搜索方式 #

1、深度优先搜索（depth-first-search DFS）  
基本思想：是从起始顶点开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。  
实现要诀：访问一个顶点并将其标记为访问，然后递归地访问所有与该顶点邻接且未标记的顶点，深度利用了可以下压的栈（递归支持）。  
深度优先搜索轨迹：  
![这里写图片描述][SouthEast 6]  
深度优先搜索动画：  
![这里写图片描述][SouthEast 7]  
其中：搜索结果是以起点为根节点的树，edgeTo是由父链接表示的树，动画显示的抽象的递归过程。

2、广度优先搜索（breadth-first-search BFS）

> 基本思想：广度优先搜索类似于二叉树的层序遍历，它的基本思想就是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1，w2，…，wi，然后再依次访问w1，w2，…，wi的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们所有未被访问过的邻接顶点……依次类推，直到图中所有顶点都被访问过为止。  
> 实现：为了实现逐层的访问，算法必须借助一个辅助队列，来保存所有已经被标记过但是其邻接表还未被检查过的顶点。先将起点加入队列，然后重复调用即可。  
> 广度优先搜索轨迹：  
> ![这里写图片描述][SouthEast 8]  
> 广度优先搜索动画：  
> ![这里写图片描述][SouthEast 9]  
> 其中：搜索结果是以起点为根节点的树，这个过程不包含递归过程，直到fifo为空，edgeTo是由父链接表示的树，动画显示的抽象的过程。

# DFS可以处理问题 #

1、单点连通性（两个顶点是否连通？）及单点路径（给定一幅图和一个起点s，那么在s和v之间是否存在一条路径？）：  
通过dfs调用，可以得出与起点连通的路径，并且将路径记录父链接树中就可以回答上述两个问题，下面代码里面实现了。  
2、一幅图中连通分量：  
一次dfs可以找出含有起点的某个连通图，如果对所有的顶点进行dfs就可以找出全部连通图并且由于遍历过的点都标记了，所以不会重复以其为起点进行dfs。  
3、检测环：  
4、双色问题：

# BFS可以处理问题 #

单点最短路径  
graph.h

#ifndef GRAPH_H
    #define GRAPH_H
    #include "stdio.h"
    #include "stdlib.h"
    #include "queue.h"
    
    typedef struct Graphnode* Node;
    struct Graphnode{
        int  v;
        Node next;
    };//邻接表节点
    typedef struct{
        int v;
        int w;
    }Edge;//边结构体
    
    typedef struct graph* Graph;
    struct graph {
        int v;
        int E;
        Node *adj;
    };//表结构体，含有顶点个数，边个数，指针数组
    
    /******************************无向图操作*******************************/
    Graph GraphInit(int v);//初始化存储空间
    void addEdge(Graph G ,Edge E);//添加边
    void GraphShow(Graph G);//显示邻接表
    void DFSPaths(Graph G , int s);//给定图和起点s，给出连通图深度搜索路径
    void BFSPaths(Graph G , int s);//给定图和起点s，给出连通图广度搜索路径
    void DFSCC(Graph G);//给定图，求连通分量
    /**********************************************************************/
    #endif // GRAPH_H

graph.c

#include "graph.h"
    #include <memory.h>
    static Node NewNode( Node head , int w  )//元素插入链表前面
    {
        Node x = (Node)malloc(sizeof(struct Graphnode));
        x->v = w;
        x->next = head;
        return x;
    }
    Graph GraphInit(int v)//依据顶点个数，初始化邻接表
    {
        int i = 0;
        Graph G = (Graph)malloc(sizeof(struct graph));//分配graph变量地址
        G->v = v;
        G->E = 0;
        G->adj = (Node *)malloc( v * sizeof(Node));//分配指针数组
        for(i = 0 ; i < v ; i++){
       //初始化指针数组全为空
            G->adj[i] = NULL;//这里将G->adj[v]越界访问，直接破坏了堆，所以后面分配报错。
        }
        return G;//将整个分配好的空间返回调用者
    }
    void addEdge(Graph G ,Edge E)//传指针，既可以减少栈开销也可以修改传入参数值。
    {
        G->adj[E.v] = NewNode(G->adj[E.v] , E.w);//插入链表
        G->adj[E.w] = NewNode(G->adj[E.w] , E.v);//插入链表
        G->E++;//边数目加1
    }
    void GraphShow(Graph G)//显示邻接表
    {
        int i = 0;
        Node t;
        printf("%d vertices , %d edges\n" , G->v , G->E);
        for(i = 0 ; i < G->v ; i++){
            printf("%d: " , i);
            for(t = G->adj[i] ; t != NULL ; t = t->next)
                printf("%2d ",t->v);
            printf("\n");
        }
    }
    static int marked[20];//标记顶点是否被访问
    static int edgeTo[20];
    static int id[20];//同一连通分量顶点与对应的标识符链接起来
    static int CC_Count = 0;
    bool hasPathTo(int v)//是否存在起点s到v的路径
    {
        return marked[v];
    }
    static void dfs(Graph G , int s)//深度优先搜索
    {
        Node t;
        marked[s] = 1;//访问了
        id[s] = CC_Count;
        for(t = G->adj[s] ; t!=NULL ; t=t->next){
            if(marked[t->v] == 0){
       //没有标记
                edgeTo[t->v] = s;//记录在父链接树
                dfs(G , t->v);//递归继续访问，模仿栈
            }
        }
    }
    void DFSPaths(Graph G , int s)//在G中找出所有起点为s的路径
    {
        int i,j;
        memset(marked , 0 , sizeof(marked));//BFS和DFS共同数组部分清0
        memset(edgeTo , 0 , sizeof(edgeTo));
        dfs(G , s);
        for(i = 0 ; i < G->v ; i++){
            if(hasPathTo(i)){
       //如果到起点有路径
                printf("%d to %d :" , s , i);
                for(j = i ; j != s ; j = edgeTo[j])
                    printf("%2d " , j);
                printf("%2d " , s);
                printf("\n");
            }
        }
    }
    
    static void bfs(Graph G , int s)//广度优先搜索
    {
        Node t;
        int v;
        marked[s] = 1;//标记起点
        QueuePut(s);//将起点加入队列
        while( !QueueEmpty()){
            v = QueueGet();
            for(t = G->adj[v] ; t!=NULL ; t=t->next){
                if(marked[t->v] == 0){
       //没有标记
                    edgeTo[t->v] = v;//记录在父链接树
                    marked[t->v] = 1;//标记已知最短
                    QueuePut(t->v);//添加队列
                }
            }
        }
    }
    void BFSPaths(Graph G , int s)//在G中找出所有起点为s的路径
    {
        int i,j;
        memset(marked , 0 , sizeof(marked));
        memset(edgeTo , 0 , sizeof(edgeTo));
        bfs(G , s);
        for(i = 0 ; i < G->v ; i++){
            if(hasPathTo(i)){
       //如果到起点有路径
                printf("%d to %d :" , s , i);
                for(j = i ; j != s ; j = edgeTo[j])
                    printf("%2d " , j);
                printf("%2d " , s);
                printf("\n");
            }
        }
    }
    //Connected Components.
    void DFSCC(Graph G)//输入图得出连通量，一次深度搜索找出一个连通量，那么进行v次搜索即可找出所有连通量
    {
        int i , t;
        for(t = 0 ; t <G->v ; t++){
       //所有顶点遍历一次
            if(marked[t] == 0){
       //没有标记，防止重复遍历
                dfs(G , t);//递归继续访问，模仿栈
                CC_Count++;//当dfs递归完成，那么一个连同分量遍历完成
            }
        }
        printf("All Components is %d\n" , CC_Count );
        for(i = 0 ; i < CC_Count ; i++){
            printf("%d Components vertex:\n" , i+1);
            for(t = 0 ; t <G->v ; t++){
                if(id[t] == i)
                    printf("%d " , t);
            }
            printf("\n");
        }
    }

main.c

#include "graph.h"
    Edge EdgestinyG[13] = {
       //连接描述数组
        {
       0,5},
        {
       4,3},
        {
       0,1},
        {
       9,12},
        {
       6,4},
        {
       5,4},
        {
       0,2},
        {
       11,12},
        {
       9,10},
        {
       0,6},
        {
       7,8},
        {
       9,11},
        {
       5,3},
    };
    Edge EdgestinyGG[8] = {
       //连接描述数组
        {
       0,5},
        {
       2,4},
        {
       2,3},
        {
       1,2},
        {
       0,1},
        {
       3,4},
        {
       3,5},
        {
       0,2},
    };
    #define EDGES 13
    int main(void)
    {
    /********* 测试BFS和DFS***************/
        Graph G;
        int i;
          QueueInit(15);
        G = GraphInit(6);
        for(i = 0; i < 8 ; i++)
            addEdge(G , EdgestinyGG[i]);
        GraphShow(G);
        DFSPaths( G , 0 );
        printf("\n");
        BFSPaths( G , 0 );
    
    /*********测试连通图个数***************/
    // Graph G;
    // int i;
    // G = GraphInit(13);
    // for(i = 0; i < EDGES ; i++)
    // addEdge(G , EdgestinyG[i]);
    // GraphShow(G);
    // DFSCC(G);
        return 0;
    }

以下是两种测试的结果：  
![这里写图片描述][SouthEast 10]

![这里写图片描述][SouthEast 11]  
如果碰到一个图中含有多个连通图，一般的思路就是分别处理子图即可。

# 有向图 #

# 最小生成树 #

![这里写图片描述][SouthEast 12]

# 最短路径 #

经典图算法必须时刻记住并且已经在很多领域应用了很久了，是经过实际验证的算法设计。

[SouthEast]: /images/20220605/2dc4d848b4334f1ca9fd9570ce563415.png
[SouthEast 1]: /images/20220605/8771c0fff934439fb3515fade798a6a3.png
[SouthEast 2]: /images/20220605/7fe87b78abfe4e889791a96f2e4cb854.png
[SouthEast 3]: /images/20220605/077ec884d5844c9a927678642c0d0b3d.png
[SouthEast 4]: /images/20220605/4044956f42f34a5dbf8a3d4afbf462a7.png
[SouthEast 5]: /images/20220605/c956f10938a54190b975e7b55e8d45cd.png
[SouthEast 6]: /images/20220605/0dd693396d674b7f818cfbbc7fa39fc5.png
[SouthEast 7]: /images/20220605/2fc5c4be86ee439e9cd3911a6a97d45b.png
[SouthEast 8]: /images/20220605/ec7ea710929b40e4b23fe460bfcf53e6.png
[SouthEast 9]: /images/20220605/3b30d2fc9af947959f56df186ddcc4f8.png
[SouthEast 10]: /images/20220605/e478212a7b9a4d3bb5a3ef4b28e6a4f8.png
[SouthEast 11]: /images/20220605/97b075103c2c46f3a23dde925d9bad33.png
[SouthEast 12]: /images/20220605/086edc9620cd47c5b21a1f8b5884eec5.png