数据结构小结（八）图

小鱼儿 2022-08-18 12:23 402阅读 0赞

### 图的定义 ###

图是由顶点集和弧集构成的数据结构，Graph = (V,R);

### 有向图 ###

由顶点集和弧集构成的图称为有向图。（弧是有方向的）

[![youxiang][]][youxiang 1]

### 无向图 ###

由顶点集和边集构成的图称为无向图。（边是无方向的）

[![wuxiang][]][wuxiang 1]

### 有向网或无向网 ###

有向图或无向图中的弧或边带权后的图分别称为有向网或无向网。

无向网  
[![wuxiangw][]][wuxiangw 1]

有向网

[![youxiangw][]][youxiangw 1]

### 子图 ###

子图简单来说就是图的一部分，类比子树的概念很好理解。

### 完全图 ###

图有n个顶点，n(n-1)/2 条边的无向图称为完全图。

### 有向完全图 ###

图有n个顶点，n(n-1)/2 条弧的无向图称为完全图。（这里是 弧 不是边了）

### 稀疏图 ###

假设图中有n 个顶点e 条边（弧），如果边（弧）的个数 e<nlongn,则称之为稀疏图，否则称之
    为稠密图。

### 邻接点 ###

无向图中有一条边的相连的两个顶点互称为邻接点，并且称边依附于这两个顶点。

### 顶点的度 ###

在无向图中与某个顶点关联的边的数目定义为这个顶点的度。

### 路径 ###

顶点与顶点中之间存在的一条连通的路径。

### 简单路径 ###

顶点不重复的路径称为简单路径。

### 回路 ###

首尾顶点相同的路径称为回路

### 简单回路 ###

除了首尾顶点，中间任何一个顶点不重复的回路称为简单回路。

### 连通图 ###

在无向图中两个结点i 和 j 如果着两个顶点中间有路径，则称i 和  j 是连通的，如果无向图中
    任意两个顶点之间都存在路径相通，则称之为连通图。无向图中各个极大连通子图称为该图的连通
    分量。

### 强连通图 ###

在有向图中，若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。有向图中各个
    极大强连通子图称为该图的强连通分量。

### 生成树 ###

包含连通图中全部顶点的极小连通子图称为该图的生成树。

## 图的存储 ##

### 邻接矩阵 ###

图的邻接矩阵是表示顶点之间相邻关系的矩阵，是顺序存储结构，也成为数组表示法。
    其实就是使用一个二维数组来存储一个图的信息。
    设图G是一个具有N个顶点的图，它的顶点集合V = {v0,v1,v2,v3,...,v(n-1)},则顶点之间的
    关系可用如下形式的矩阵A来描述，即矩阵A中的每个元素A[i][j]满足：
    
              1   则表示vi,vj 有连通关系
    A[i][j] 
              0   没有连通关系

[![linjie][]][linjie 1]

#define  MAXVEX      20      /*最大顶点个数*/
    #define  INFINITY    32767   /*表示极大值，个人感觉用-1更好*/
    
    typedef int vextype ;        /*顶点类型*/
    
    typedef struct AdjMatrix{     /*一个图的控制信息*/
    
        int arcs[MAXVEX][MAXVEX];      /*矩阵*/
        vextype vex[MAXVEX];           /*顶点数组*/
        int vexnum         ;           /*顶点个数*/
        int arcnum         ;           /*边的个数*/
    
    }AdjMatrix ;
    
    
    创建一个无向网，（带权）
    
    void  AdjMatrix_create(AdjMatrix *G){
    
        int i,j,k,weight,vex1,vex2;
        printf("vexnum  and  arcnum：\n");
    
        scanf("%d,%d",&G->vexnum,&G->arcnum);
    
    
        for(i = 1; i <= G->vexnum;i++){            /*init the graph*/
            for(j = 1; j <= G->vexnum;j++){
                G->arcs[i][j] = INFINITY ;
            }
        }
    
        for(k = 0;k < G->arcnum;k++){
            printf("please enter vex1 and vex2\n");
            scanf("%d,%d",&vex1,&vex2);
    
            printf("please enter weight\n");
            scanf("%d",&weight);
    
            G->arcs[vex1][vex2] = weight;
            G->arcs[vex2][vex1] = weight;  /*如果是有向网删除这句就好，不需要对称*/
        }  
    
    
    }

几点说明：

对于无向图：第i个顶点的度就等于矩阵中第i行非零元素。
    对于有向图：第i个顶点的出度就等于矩阵中第i行非零元素个数。
              第i个顶点的入读就等于矩阵中第i列非零元素个数。

### 邻接表 ###

当图中的边数远远小于图中的顶点数时，就是稀疏图的时候，邻接矩阵就成为稀疏矩阵，如果继续
    使用邻接矩阵就会造成很大的浪费，一个较好的解决方案就是采用邻接表。这里所有的顶点之间是
    平行关系，不存在顺序关系。

[![linjiebiao][]][linjiebiao 1]

下来说下变量类型和创建代码。

typedef struct ArcNode{         /* node type  结点类型 */
    
        int adjvex ;
        int weight ;
        struct ArcNode *next;
    
    }ArcNode;
    
    
    typedef struct VertexNode{    /* 数组实例*/
    
        char vexdata ;
        ArcNode *head;
    
    }VertexNode;
    
    
    typedef struct AdjList{
    
        VertexNode vertex[MAXVEX];
        int vexnum;
        int arcnum;
    
    
    }AdjList;          /*邻接表结构体*/
    
    
    创建一个邻接表，这里只有函数代码，完整可测试代码在附录
    
    void AdjList_create(AdjList *G){
    
        int i,j,k;
        int vex1,vex2,weight;
        if(!G){
            printf("G need cast a spece\n");
            return ;
        }
    
        printf("please enter the vexnum and arcnum\n");
    
        scanf("%d,%d",&G->vexnum,&G->arcnum);
    
        for(i = 1;i <= G->vexnum;i++){
    
            G->vertex[i].head  = NULL;
    
        }
    
    
        for(i = 1;i <= G->arcnum;i++){
            printf("please enter the vex1 and vex2 and weight\n");
            scanf("%d,%d,%d",&vex1,&vex2,&weight);
            add_node(G,vex1,vex2,weight);
    
        }
    
    }
    
    void add_node(AdjList *G,int vex1,int vex2,int weight){
    
        ArcNode *p,*q;
        p = (ArcNode *)malloc(sizeof(struct ArcNode));
        p->adjvex = vex2  ;
        p->weight = weight;
        q = G->vertex[vex1].head;
        do{
            if(NULL == q){
                G->vertex[vex1].head  = p;
                break;
            }else if(NULL == q->next){
                q->next = p;
                p->next = NULL;
                break;
            }else{
                q = q->next;
            }
        }while(1);
    
        return ;
    
    }

### 十字链表 ###

这并非考试常考考点，简要说明。

十字链表是有向图的另一种存储结构，可以看成是邻接表与逆邻接表的结合。仍然由边表和顶点组成。

[![shizi][]][shizi 1]

#define   MAXVEX   20
    
    typedef struct  ArcNode{
    
        int tailvex,headvex;
        int weight         ;
        struct ArcNode *hnextarc,*tnextarc;
    
    }ArcNode;
    
    typedef struct VertexNode{
    
        char vexdata;
        ArcNode *head,*tail;
    
    }Vertexxnode;
    
    typedef struct  OrthList{
    
        VertexNode vertex[MAXVEX];
        int vexnum;
        int arcnum;
    
    }OrthList;
    
    
    
    一些说明：
    
    tailvex   headvex  hnextarc  tnextarc  info
    边表结点结构
    
    vexdata   head  tail
    顶点表结点结构
    
    headvex : 弧头
    tailvex : 弧尾
    hnextarc: 指向具有同一弧头顶点的下一条弧
    tnextarc: 指向具有同一弧尾顶点的下一条弧
    info :表示弧权值等信息
    
    vexdata:  顶点的相关数据结构信息
    head   :  以该顶点为弧头的边表指针
    tail   :  以该顶点为弧尾的边表头指针

### 多重链表 ###

多重链表是适用于无向图的链式存储结构。它是邻接表的改进，主要解决了在邻接表中对边表操作不方便的问题。

[![test][]][test 1]

这个插图确实没找好。。。。

#define  MAXVEX   20
    
    typedef struct ArcNode{
    
        int mark,ivex,jvex;
        int weight;
        struct ArcNode *inext,*jnext;
    
    }ArcNode;
    
    typedef struct VertexNode{
    
        char vexdata;
        ArcNode *head;
    
    }VertexNode;
    
    typedef struct AdjMultipleList{
    
        VertexNode vertex[MAXVEX];
        int  vexnum;
        int  arcnum;
    
    }AdjMultipleList;

## 图的遍历 ##

### 深度优先遍历 ###

深度优先遍历类似于树的先根遍历。就是从一个结点开始，每次按照往最深遍历，如果图是连通的，
    那么就能遍历完成，如果图不是连通的，就找到没有遍历的顶点开始继续遍历直到遍历整个图。

这里只写了主要函数的代码，其他完整代码在附录
    void TraverseGraph(AdjMatrix *G,int index){
        int i;
        for(i = 1;i <= G->vexnum;i++){
            G->vex[i] = 0;
        }
        for(i = 1;i <= G->vexnum;i++){
            if(!G->vex[i])
                DFS(G,i);
        }
    }
    
    int FirstAdjvex(AdjMatrix *G,int i){    /*这两个寻找顶点的函数中间还是使用了循环，在考虑进一步优化*/
        int j ;
        for(j = 1;j <= G->vexnum;j++){
            if(G->arcs[i][j] != 0){
                printf("j = %d\n",j);
                return j;
            }
        }
        return -1;
    }
    
    int NextAdjvex(AdjMatrix *G,int i,int w){
        int j;
        for(j = 1;j <= G->vexnum;j++){
            if(G->arcs[i][j] != 0  &&  j!= w){
                return j;
            }
        }
        return -1;
    }
    
    
    void DFS(AdjMatrix *G,int i){
    
        int w;
        printf("%d \n",i);
        G->vex[i] = 1;
        w = FirstAdjvex(G,i);
        while(w != -1){
            if(!G->vex[i])
                DFS(G,w);
            w = NextAdjvex(G,i,w);
        }
    
    }
    
    
    
    非递归遍历：
    void  DFS(Graph *G,int v){
        stack *S;
        S = INIT_stack();
        int vex[MAXVEX];
    
        push(S,v);
        while(!isEmpty(S)){
            v = pop(S);
            if(!vex[v]){
                visit(v);
                vex[v] = 1;
            }
            w = FirstAdjVertex(G,v);
            while(w != -1){
                if(!vex[w])
                    push(S,w);
                w = NextAdjVertex(G,v,w);
            }
        }
    
    }

### 广度优先遍历 ###

图的广度优先遍历相似于树的按照层次遍历，所以可以借助队列完成遍历。
    每次访问到一个顶点都将它入队，当队头元素出队时，将其未被访问的邻接点入队，每个顶点只入队
    一次。

void BFS(AdjMatrix *G,int v){
        printf("%d\n",v);
        G->vex[v] = 1;
        queue * Q;
        int w;
        Q = queue_init();
        queue_inq(Q,v);
        while(!isEmpty(Q)){
            v = queue_deq(Q);
            w = FirstAdjvex(G,v);
            while(w != -1){
                if(!G->vex[w]){
                    printf("%d\n",w);
                    G->vex[w] = 1;
                    queue_inq(Q,w);
                }
                w = NextAdjvex(G,v,w);   
            }
        }
    }
    
    
    
    void TraverG(AdjMatrix * G,int v){
        int i ;
        for(i = 1;i <= G->vexnum;i++){
            G->vex[i] = 0;
        }
        for(i = 1; i <= G->vexnum;i++){
            if(!G->vex[i]){
                BFS(G,i);
            }
        }
    }

查看原文：[http://zmrlinux.com/2015/12/20/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%b0%8f%e7%bb%93%ef%bc%88%e5%85%ab%ef%bc%89%e5%9b%be/][http_zmrlinux.com_2015_12_20_e6_95_b0_e6_8d_ae_e7_bb_93_e6_9e_84_e5_b0_8f_e7_bb_93_ef_bc_88_e5_85_ab_ef_bc_89_e5_9b_be]

[youxiang]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/youxiang.jpg
[youxiang 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/youxiang.jpg
[wuxiang]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/wuxiang.jpg
[wuxiang 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/wuxiang.jpg
[wuxiangw]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/wuxiangw.jpg
[wuxiangw 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/wuxiangw.jpg
[youxiangw]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/youxiangw.jpg
[youxiangw 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/youxiangw.jpg
[linjie]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/linjie.png
[linjie 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/linjie.png
[linjiebiao]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/linjieb.png
[linjiebiao 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/linjieb.png
[shizi]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/shizi.png
[shizi 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/shizi.png
[test]: https://github.com/zmr961006/DSAA/raw/master/chap8_graph/test.png
[test 1]: https://github.com/zmr961006/DSAA/blob/master/chap8_graph/test.png
[http_zmrlinux.com_2015_12_20_e6_95_b0_e6_8d_ae_e7_bb_93_e6_9e_84_e5_b0_8f_e7_bb_93_ef_bc_88_e5_85_ab_ef_bc_89_e5_9b_be]: http://zmrlinux.com/2015/12/20/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%b0%8f%e7%bb%93%ef%bc%88%e5%85%ab%ef%bc%89%e5%9b%be/