图的表示法

太过爱你忘了你带给我的痛 2022-08-23 09:56 180阅读 0赞

# 图的分类 #

图表示一种多对多的关系。

## 图的概念 ##

图由顶点和边组成。可以无边，但至少有一个顶点。

*  一组顶点，通常有V(vetex)表示顶点的集合
 *  一组边，通常用E(edge)表示边的集合

图可以分为有向图和无向图

*  (v,w)表示无向边，即v和w是互通的
 *  <v,w)表示有向边，边始于v, 终于w

图可以分为有权图和无权图

*  有权图：每条边都有权重值，通常是一个数字
 *  无权图：每条边都没有权重，通常可以理解为权重为1

图又可以分为连通图和非连通图

*  连通图：所有的顶点都有路径相连
 *  非连通图：存在某两个顶点没有路径相连

图中的顶点有度的概念

*  度：所有和它连接点的个数之和
 *  出度：存在于有向图中，所有接入该点的边数之和
 *  入度：存在于有向图中，所有从接出该点的边数之和

## 图的表示方法 ##

要表示一个图G=（V，E）（注：V：vertex、E：edge），有两种方法，即邻接表和邻接矩阵。这两种方法既**可以用于有向图**，也**可以用于无向图**。

// 图1，无向图
    1 ----- 2
    |       |  \
    |       |  / 3
    5 ----- 4

# 邻接表 #

邻接表表示法通常表示稀疏图（图中 |E| 远小于 |V|^2）比较紧凑。

// 邻接表数据结构表示无向图
    
    // 定义图中最多100个节顶点
    #define MAX 100
    
    // 邻接表中的顶点定义
    typedef struct Vertex
    {
            int v; 
            struct Vertex *next;
            
    } Vertex;
    
    // 邻接表
    Vertex Adj[MAX];
    
    // 创建顶点
    Vertex* makeVertex(int v)
    {
            Vertex *pVertex = (Vertex*) malloc(sizeof(Vertex));
            pVertex->v = v; 
            pVertex->next = NULL;
            return pVertex;
    }
    // 删除顶点
    void destroyVertex(Vertex *pVertex)
    {
            free(pVertex);
    }

// 完整代码
    #include <stdio.h>
    #include <malloc.h>
    
    #define MAX 100
    
    typedef struct Vertex
    {
            int v; 
            struct Vertex *next;
            
    } Vertex;
    
    Vertex Adj[MAX];
    
    Vertex* makeVertex(int v)
    {
            Vertex *pVertex = (Vertex*) malloc(sizeof(Vertex));
            pVertex->v = v;
            pVertex->next = NULL;
            return pVertex;
    }
    void destroyVertex(Vertex *pVertex)
    {
            free(pVertex);
    }
    
    // 初始化图
    void initGraph()
    {
            printf("input edges:\nlike 1,2\n-1,-1\n");
            int v1 = 0, v2 = 0;
            while (1){
                    scanf("%d,%d", &v1, &v2);
                    
    				// 输入-1,-1表示输入结束
                    if (v1 == -1 && v2 == -1)
                            break;
    
                    Adj[v1].v = v1;
                    Vertex *pVertex = &Adj[v1];
                    while ( pVertex->next ) {
                            pVertex = pVertex->next;
                    }
                    pVertex->next = makeVertex(v2);
            }
    }
    
    // 打印当前图
    void printGraph(int n)
    {
            for (int i = 1; i <= n; i++) {
                    printf("%d", Adj[i].v);
                    Vertex *pVertex = Adj[i].next;
                    while (pVertex) {
                            printf("--%d", pVertex->v);
                            pVertex = pVertex->next;
                    } 
                    printf("\n");
            }
    }
    // 销毁图中的节点
    void uninitGraph(int n) {
            for (int i = 1; i <= n; i++) {
                    Vertex *pVertex = Adj[i].next;
                    Adj[i].next = NULL;
                    while (pVertex) {
                            Vertex *pTemp = pVertex->next;
                            destroyVertex(pVertex);
                            pVertex = pTemp;
                    }
                    printf("destroy vertex[%d]\n", i);
            }
    }
    
    int main()
    {
            int n = 0;
            printf("input vertex's number\n");
            scanf("%d", &n);
    
            initGraph();
            printGraph(n);
            uninitGraph(n);
            printGraph(n);
            return 0;
    }
    
    // 执行方式
    input vertex's number
    5
    1,2
    1,5
    ...
    -1,-1 // 结束输入

## 邻接表的长度 ##

若G是一个有向图，则所有邻接表的长度之和为 |E|。  
若G是一个无向图，则所有邻接表的长度之和为 2|E|。  
无论有向图还是无向图，邻接表需要的**存储空间为O(V+E)。**

## 加权图 ##

图的每条边有着相应权值。  
设G=（V，E）是一个加权函数为w的加权图。对每一条边（u，v）且（u，v）属于E，权值为w（u，v）和顶点v一起存储在u的邻接表中。

typedef struct Vertex
    {
            int v; // 顶点
    	    int w; // 加权值
            struct Vertex *next;
            
    } Vertex;

# 邻接矩阵 #

邻接矩阵表示法通常用于表示稠密图（图中|E| 接近于 |V|^2）**或必须很快判别两个顶点是否存在连接边时使用**。

// 邻接矩阵表示无向图
    
    #define MAX 100
    
    int  G[MAX][MAX] = {0};

// 完整代码
    
    #include <stdio.h>
    
    #define MAX 100
    
    int  G[MAX][MAX] = {0};
    
    // 初始化图
    void initGraph()
    {
            printf("input edges:\nlike 1,2\n");
            int v1 = 0, v2 = 0;
            while (1){
                    scanf("%d,%d", &v1, &v2);
    
                    if (v1 == -1 && v2 == -1)
                            break;
    
                    G[v1][v2] = 1;
                    G[v2][v1] = 1;
            }
    
    }
    
    // 打印图
    void printGraph(int n)
    {
            for (int i = 1; i <= n; i++) {
                    printf("%d", i);
                    for (int j = 1; j <= n; j++) {
                            if (G[i][j] == 1) {
                                    printf("--%d", j);
                            }
                    }
                    printf("\n");
            }
    }
    
    int main()
    {
            int n = 0;
            printf("input vertex's number\n");
            scanf("%d", &n);
    
            initGraph();
            printGraph(n);
    
            return 0;
     }

## 邻接矩阵的特点 ##

一个图的邻接矩阵表示需要占用**O（V^2）的存储空间**，它与图中的边数多少是无关的。

**无向图的邻接矩阵A就是它自己的转置矩阵**：A=A^T。在某些应用中只需要存储临街觉着呢的对角线及对角线以上的部分，图所占的存储空间几乎可以减少一半。

邻接矩阵的也可以用来表示加权图。矩阵中相应的元素可以存储边的权值，如果边不存在就用0或无限大的值来表示权值。

如果一个图不是加权的，邻接矩阵的每个元素只用一个二进制位，而不必用一个字的空间。