美文网首页
012-数据结构与算法-图

012-数据结构与算法-图

作者: 沉默Coder | 来源:发表于2020-05-06 11:05 被阅读0次

    什么是图 ?

    前面总结了“树”这种数据结构,而这篇博客总结的是更为复杂的一种数据结构:图(graph),它表明了物件与物件之间的“多对多”的一种复杂关系。图包含了两个基本元素:顶点(vertex, 简称V)和边(edge,简称E)。


    有向图和无向图
    无向图
    有向图

    如果给图的每条边规定一个方向,那么得到的图称为有向图。在有向图中,从一个顶点出发的边数称为该点的出度,而指向一个顶点的边数称为该点的入度。相反,边没有方向的图称为无向图。

    有权图和无权图

    如果图中的边有各自的权重,得到的图是有权图。比如地铁路线图,连接两站的边的权重可以是距离,也可以是价格,或者其他。反之,如果图的边没有权重,或者权重都一样(即没有区分),称为无权图

    连通图和非连通图

    如果图中任意两点都是连通的,那么图被称作连通图。如果存在一个或多个点和其他的顶点没有连通,那么图被称为非连通图

    图的存储

    • 邻接矩阵
    • 邻接表
    邻接矩阵
    邻接矩阵
    typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码,如OK等 */
    typedef char VertexType; /* 顶点类型应由用户定义  */
    typedef int EdgeType; /* 边上的权值类型应由用户定义 */
    typedef struct
    {
        VertexType vexs[MAXVEX]; /* 顶点表 */
        EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵,可看作边表 */
        int numNodes, numEdges; /* 图中当前的顶点数和边数  */
    }MGraph;
    

    以上的代码就定义好了一个图形结构,下面我们再使用邻接表定义一个图形存储结构

    邻接表
    邻接表

    需要注意的是:这里的next指针所指向的顶点并不代表和当前顶点有联系,比如说从V0开始,v0和v1,v2,v3分别相连,但是v1的next指针指向了v2顶点,并不代表v1和v2相关联
    仅仅表示,这条链表上的所有元素都和v0相关联

    typedef char Element;
    typedef int BOOL;
    //邻接表的节点
    typedef struct Node{
        int adj_vex_index;  //弧头的下标,也就是被指向的下标
        Element data;       //权重值
        struct Node * next; //边指针
    }EdgeNode;
    
    //顶点节点表
    typedef struct vNode{
        Element data;          //顶点的权值
        EdgeNode * firstedge;  //顶点下一个是谁?
    }VertexNode, Adjlist[M];
    
    //总图的一些信息
    typedef struct Graph{
        Adjlist adjlist;       //顶点表
        int arc_num;           //边的个数
        int node_num;          //节点个数
        BOOL is_directed;      //是不是有向图
    }Graph, *GraphLink;
    

    图的遍历

    • 深度优先遍历
    • 广度优先遍历
    深度优先遍历(邻接矩阵实现)

    广度优先遍历

    邻接矩阵深度优先遍历代码实现思路:

    1. 将图的顶点和边信息输⼊到图结构中;
    2. 创建⼀个visited 数组,⽤用来标识顶点是否已经被遍历过.
    3. 初始化visited 数组,将数组中元素置为FALSE
    4. 选择顶点开始遍历.(注意非连通图的情况)
    5. 进入递归; 打印i 对应的顶点信息. 并将该顶点标识为已遍历.
    6. 循环遍历边表,判断当前arc[i][j] 是否等于1,并且当前该顶点没有被遍历过,则继续递归 DFS;

    代码实现:

    /*4.2 DFS遍历*/
    Boolean visited[MAXVEX]; /* 访问标志的数组 */
    //1. 标识顶点是否被标记过;
    //2. 选择从某一个顶点开始(注意:非连通图的情况)
    //3. 进入递归,打印i点信息,标识; 边表
    //4. [i][j] 是否等于1,没有变遍历过visted
    void DFS(MGraph G,int i){
        //1.
        visited[i] = TRUE;
        printf("%c",G.vexs[i]);
        
        //2.0~numVertexes
        for(int j = 0; j < G.numVertexes;j++){
            if(G.arc[i][j] == 1 && !visited[j])
                DFS(G, j);
        }
    }
    
    void DFSTravese(MGraph G){
        //1.初始化
        for(int i=0;i<G.numVertexes;i++){
            visited[i] = FALSE;
        }
        
        //2.某一个顶点
        for(int i = 0;i<G.numVertexes;i++){
            if(!visited[i]){
                DFS(G, i);
            }
        }
    }
    
    深度优先遍历(邻接表实现)
    Boolean visited[MAXSIZE]; /* 访问标志的数组 */
    /* 邻接表的深度优先递归算法 */
    void DFS(GraphAdjList GL, int i)
    {
        EdgeNode *p;
        visited[i] = TRUE;
        
        //2.打印顶点 A
        printf("%c ",GL->adjList[i].data);
        
        p = GL->adjList[i].firstedge;
        
        //3.
        while (p) {
            if(!visited[p->adjvex])
                DFS(GL,p->adjvex);
            
            p = p->next;
        }
    }
    
    /* 邻接表的深度遍历操作 */
    void DFSTraverse(GraphAdjList GL)
    {
        //1. 将访问记录数组默认置为FALSE
        for (int i = 0; i < GL->numVertexes; i++) {
            /*初始化所有顶点状态都是未访问过的状态*/
            visited[i] = FALSE;
        }
    
        //2. 选择一个顶点开始DFS遍历. 例如A
        for(int i = 0; i < GL->numVertexes; i++)
            //对未访问过的顶点调用DFS, 若是连通图则只会执行一次.
            if(!visited[i])
                DFS(GL, i);
    }
    

    图的广度优先遍历(邻接矩阵实现)

    1. 把根节点放到队列的末尾。
    2. 每次从队列的头部取出一个元素,查看这个元素所有的下一级元素,把它们放到队
      列的末尾。并把这个元素记为它下一级元素的前驱。
    3. 找到所要找的元素时结束程序。
    4. 如果遍历整个树还没有找到,结束程序.
    /* 循环队列的顺序存储结构 */
    typedef struct
    {
        int data[MAXSIZE];
        int front;        /* 头指针 */
        int rear;        /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
    }Queue;
    
    /* 初始化一个空队列Q */
    Status InitQueue(Queue *Q)
    {
        Q->front=0;
        Q->rear=0;
        return  OK;
    }
    
    /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
    Status QueueEmpty(Queue Q)
    {
        if(Q.front==Q.rear) /* 队列空的标志 */
        return TRUE;
        else
        return FALSE;
    }
    
    /* 若队列未满,则插入元素e为Q新的队尾元素 */
    Status EnQueue(Queue *Q,int e)
    {
        if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */
        return ERROR;
        Q->data[Q->rear]=e;            /* 将元素e赋值给队尾 */
        Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */
        /* 若到最后则转到数组头部 */
        return  OK;
    }
    
    /* 若队列不空,则删除Q中队头元素,用e返回其值 */
    Status DeQueue(Queue *Q,int *e)
    {
        if (Q->front == Q->rear)            /* 队列空的判断 */
        return ERROR;
        *e=Q->data[Q->front];                /* 将队头元素赋值给e */
        Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置, */
        /* 若到最后则转到数组头部 */
        return  OK;
    }
    /******** Queue End **************/
    
    /*4.3 邻接矩阵广度优先遍历-代码实现*/
    Boolean visited[MAXVEX]; /* 访问标志的数组 */
    void BFSTraverse(MGraph G){
        
        int temp = 0;
        
        //1.
        Queue Q;
        InitQueue(&Q);
        
        //2.将访问标志数组全部置为"未访问状态FALSE"
        for (int i = 0 ; i < G.numVertexes; i++) {
            visited[i] = FALSE;
        }
        
        //3.对遍历邻接表中的每一个顶点(对于连通图只会执行1次,这个循环是针对非连通图)
        for (int i = 0 ; i < G.numVertexes; i++) {
            
            if(!visited[i]){
                visited[i] = TRUE;
                printf("%c  ",G.vexs[i]);
                
                //4. 入队
                EnQueue(&Q, i);
                while (!QueueEmpty(Q)) {
                    //出队
                    DeQueue(&Q, &i);
                    for (int j = 0; j < G.numVertexes; j++) {
                        if(G.arc[i][j] == 1 && !visited[j])
                        {
                            visited[j] = TRUE;
                            printf("%c   ",G.vexs[j]);
                            EnQueue(&Q, j);
                        }
                    }
                }
            }
        }
    }
    

    图的广度优先遍历(邻接表实现)

    /*
     5.2 ***需要用到的队列结构与相关功能函数***
     */
    /* 循环队列的顺序存储结构 */
    typedef struct
    {
        int data[MAXSIZE];
        int front;        /* 头指针 */
        int rear;        /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
    }Queue;
    
    /* 初始化一个空队列Q */
    Status InitQueue(Queue *Q)
    {
        Q->front=0;
        Q->rear=0;
        return  OK;
    }
    
    /* 若队列Q为空队列,则返回TRUE,否则返回FALSE */
    Status QueueEmpty(Queue Q)
    {
        if(Q.front==Q.rear) /* 队列空的标志 */
        return TRUE;
        else
        return FALSE;
    }
    
    /* 若队列未满,则插入元素e为Q新的队尾元素 */
    Status EnQueue(Queue *Q,int e)
    {
        if ((Q->rear+1)%MAXSIZE == Q->front)    /* 队列满的判断 */
        return ERROR;
        Q->data[Q->rear]=e;            /* 将元素e赋值给队尾 */
        Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置, */
        /* 若到最后则转到数组头部 */
        return  OK;
    }
    
    /* 若队列不空,则删除Q中队头元素,用e返回其值 */
    Status DeQueue(Queue *Q,int *e)
    {
        if (Q->front == Q->rear)            /* 队列空的判断 */
        return ERROR;
        *e=Q->data[Q->front];                /* 将队头元素赋值给e */
        Q->front=(Q->front+1)%MAXSIZE;    /* front指针向后移一位置, */
        /* 若到最后则转到数组头部 */
        return  OK;
    }
    /* *********************** Queue End ******************************* */
    /*5.3 邻接表广度优先遍历*/
    Boolean visited[MAXSIZE]; /* 访问标志的数组 */
    void BFSTraverse(GraphAdjList GL){
        
        //1.创建结点
        EdgeNode *p;
        
        Queue Q;
        InitQueue(&Q);
        
        //2.将访问标志数组全部置为"未访问状态FALSE"
        for(int i = 0; i < GL->numVertexes; i++)
            visited[i] = FALSE;
        
        //3.对遍历邻接表中的每一个顶点(对于连通图只会执行1次,这个循环是针对非连通图)
        for(int i = 0 ;i < GL->numVertexes;i++){
            //4.判断当前结点是否被访问过.
            if(!visited[i]){
                visited[i] = TRUE;
                //打印顶点
                printf("%c ",GL->adjList[i].data);
                
                EnQueue(&Q, i);
                while (!QueueEmpty(Q)) {
                    DeQueue(&Q, &i);
                    p = GL->adjList[i].firstedge;
                    while (p) {
                        //判断
                        if(!visited[p->adjvex]){
                            visited[p->adjvex] = TRUE;
                             printf("%c ",GL->adjList[p->adjvex].data);
                            EnQueue(&Q, p->adjvex);
                        }
                        p = p->next;
                    }
                }
                
            }
        }
    }
    

    相关文章

      网友评论

          本文标题:012-数据结构与算法-图

          本文链接:https://www.haomeiwen.com/subject/hzyightx.html