经典数据结构 — 图

图.png

图[Graph] 是由顶点的有穷非空集合和顶点之间边的集合组成.通常表示为: G[V,E] 其中，G 表示一个图，V 是 图G 中的顶点集合，E 是 图G 中边的集合.

各种图

无向图&无向边

无向图&无向边.png

有向图&有向边

有向图&有向边.png

无向完全图

无向完全图.png

有向完全图

有向完全图.png

网

网.png

图的存储

快手面试真题

【数据结构与算法设计】 将下边图存储到计算机中.请设计一个数据结构并将其合理存储起来。

有向图的存储.png

其邻接矩阵如下图:

邻接矩阵.png
结论：设图G有n个顶点，则邻接矩阵是一个n*n的方阵，定义为:
定义.png

邻接矩阵的思考

针对邻接矩阵的思考.png

针对上面的面试题，对应的邻接矩阵为:

邻接矩阵.png

邻接矩阵矩阵存储的数据结构设计

#define MAXVEX 100 /* 最大顶点数，应由用户定义 */
#define INFINITYC 0 

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

邻接矩阵矩阵存储代码的实现思路

1. 缺点地点数和边树
2. 读取顶点信息
3. 初始化邻接矩阵
4. 读取边信息
5. 循环打印

void CreateMGraph(MGraph *G){
    int i,j,k,w;
    printf("输入顶点数和边数:\n");
    //1. 输入顶点数/边数
    scanf("%d,%d",&G->numNodes,&G->numEdges);
    printf("顶点数:%d,边数:%d\n",G->numNodes,G->numEdges);
    
    //2.输入顶点信息/顶点表
    printf("输入顶点信息:\n");
    for(i = 0; i<= G->numNodes;i++)
        scanf("%c",&G->vexs[i]);
    
    //3.初始化邻接矩阵
    for(i = 0; i < G->numNodes;i++)
         for(j = 0; j < G->numNodes;j++)
             G->arc[i][j] = INFINITYC;
    
    //4.输入边表信息
    for(k = 0; k < G->numEdges;k++){
        printf("输入边(vi,vj)上的下标i,下标j,权w\n");
        scanf("%d,%d,%d",&i,&j,&w);
        
        G->arc[i][j] = w;
        //如果无向图,矩阵对称;
        G->arc[j][i] = G->arc[i][j];
        
    }
    /*5.打印邻接矩阵*/
    for (int i = 0; i < G->numNodes; i++) {
        printf("\n");
        for (int j = 0; j < G->numNodes; j++) {
            printf("%d ",G->arc[i][j]);
        }
    }
    printf("\n");
}

使用并打印：

printf("邻接矩阵实现图的存储\n");
/*图的存储-邻接矩阵*/
MGraph G;
CreateMGraph(&G);

打印结果.png