JZTXT

图的存储结构

发布时间 2023-06-06 18:54:04作者: 刘倩_网安2211

图的存储结构

标签（空格分隔）： DS 图 顺序存储 链式存储

图的邻接矩阵存储的结点结构

  邻接矩阵：
1.如果是无向图，则是对称矩阵，Vi与Vj有边则arc[i][j]和arc[j][i]为1，否则为0；arc[i][i]=0;
2.如果是有向图，则不是对称矩阵，vi->vj则arc[i][j]为1，否则为0；arc[i][i]=0;
3.如果是网，则vi和vj有边或弧，则arc[i][j]=权；否则a[i][j]=INFINITY；arc[i][i]=0;

#define INFINITY 65535//表示无穷
typedef struct
{
    char vexs[MAXVEX];//顶点表
    int arc[MAXVEX][MAXVEX];//邻接矩阵，边表
    int numVexs,numarc;//图当前顶点数和边数
}* MGraph;

建立无向网图的邻接矩阵表示

void CreateMGraph(MGraph G)
{
    int i,j,k,w;
    printf("输入顶点数和边数：\n");
    scanf("%d,%d",&G->numVexs,&G->numarc);
    
    //输入顶点信息
    for(i=0;i<G->numVexs;i++)
        scanf("%c",&G->Vexs[i]);
    
    //邻接矩阵初始化
    for(i=0;i<G->numVexs;i++)//邻接矩阵行循环
        for(j=0;j<G->numVexs;j++)//邻接矩阵列循环
            G->arc[i][j]=INFINITY;
          
    //输入边和权 
    for(k=0;k<G->numarc;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];
    }
}

邻接表结构

//边表结点
typedef struct EdgeNode
{
    int adjvex;//邻接点域，存储该顶点对应下标
    int weight;//用于存储权值
    struct EdgeNode* next;//指向下一个邻接点
}EdgeNode,* EdgePtr;

//顶点表结点
typedef struct VertexNode
{
    char data;
    EdgePtr firstedge;//边表头指针
}VexNode,AdjList[MAXVEX];

typedef struct
{
    AdjList adjList;
    int numVexs,numEdges;//图当前顶点数和边数
}GraphAdjList,* GPtr;

无向图的邻接表的创建

void CreateALGraph(GPtr G)
{
    int i,j,k;
    EdgePtr e;//边表指针
    printf("输入顶点数和边数：\n");
    scanf("%d,%d",&G->numVexs,&G->numEdges);
    
    //输入顶点表
    for(i=0;i<G->numVexs;i++)
    {
        scanf("%c",&G->adjList[i].data);
        G->adjList[i].firstedge=NULL;//将边表置为空
    }
    
    for(k=0;k<numEdges;k++)
    {
        printf("输入边(vi.vj)上的顶点序号：\n");
        scanf("%d,%d",&i,&j);
        
        e=(EdgePtr)malloc(sizeof(EdgeNode));
        e->adjvex=j;
        //尾插法
        e->next=G->adjList[i].firstadge;
        G->adjList[i].firstedge=e;
        
        e=(EdgePtr)malloc(sizeof(EdgeNode));
        e->adjvex=i;
        e->next=G->adjList[j].firstedge;
        G->adjList[j].firstedge=e;
    }