图的存储结构_牛客博客

文章目录

一、邻接矩阵

二、邻接矩阵的主要特点

三、邻接链表

四、邻接矩阵的建立

五、邻接链表的建立

一、邻接矩阵

用两个数组来表示图。一个一位数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。

举例：无向图和有向图的对比

无向图邻接矩阵对称
但有向图的邻接矩阵不一定都不对称

二、邻接矩阵的主要特点：

一个图的邻接矩阵表示是唯一的
适合于稠密图的存储
存储空间为O（N^2）
邻接矩阵的好处：

无向图：

有向图：

网：需要存权值（W）

这里“∞”表示一个计算机允许的、大于所有边上权值的值。是一个不可能的极限值

四、邻接矩阵的建立

无向网图邻接矩阵的建立：


#define MAXWEX 100 //最大顶点数，自定义 
#define INFINITY 65535 //用65535表示∞
typedef struct
{
   
	char vesx[MAXWEX];  //顶点表
	int arc[MAXWEX][MAXWEX];  //邻接矩阵(边表)
	int numv;  //顶点数
	int nume;  //边数
}MGraph;
void CreateMGraph(MGraph* G)
{
   
	int i, j, k, w;
	printf("请分别输入顶点数和边数：\n");
	scanf("%d %d",&G->numv,&G->nume);
	//读入顶点信息
	for (i = 0; i < G->numv; i++)
	{
   
		scanf("%c",&G->vesx[i]);
	}
	
	for (i = 0; i < G->nume; i++)
	{
   
		for (j = 0; j < G->nume; j++)
		{
   
			G->arc[i][j] = INFINITY;  //邻接矩阵初始化为∞
		}	
	}
	//建立邻接矩阵
	for (k = 0; k < G->nume; 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];  //无向图矩阵对称
	}
}

邻接矩阵的综合建立：

/* 图的邻接矩阵表示法 */
 
#define MaxVertexNum 100 /* 最大顶点数设为100 */
#define INFINITY 65535 /* ∞设为双字节无符号整数的最大值65535*/
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;        /* 边的权值设为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
 
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
   
    Vertex V1, V2;      /* 有向边<V1, V2> */
    WeightType Weight;  /* 权重 */
};
typedef PtrToENode Edge;
        
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{
   
    int Nv;  /* 顶点数 */
    int Ne;  /* 边数 */
    WeightType G[MaxVertexNum][MaxVertexNum]; /* 邻接矩阵 */
    DataType Data[MaxVertexNum];      /* 存顶点的数据 */
    /* 注意：很多情况下，顶点无数据，此时Data[]可以不用出现 */
};
typedef PtrToGNode MGraph; /* 以邻接矩阵存储的图类型 */
 
 
 
MGraph CreateGraph( int VertexNum )
{
    /* 初始化一个有VertexNum个顶点但没有边的图 */
    Vertex V, W;
    MGraph Graph;
     
    Graph = (MGraph)malloc(sizeof(struct GNode)); /* 建立图 */
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    /* 初始化邻接矩阵 */
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
    for (V=0; V<Graph->Nv; V++)
        for (W=0; W<Graph->Nv; W++)  
            Graph->G[V][W] = INFINITY;
             
    return Graph; 
}
        
void InsertEdge( MGraph Graph, Edge E )
{
   
     /* 插入边 <V1, V2> */
     Graph->G[E->V1][E->V2] = E->Weight;    
     /* 若是无向图，还要插入边<V2, V1> */
     Graph->G[E->V2][E->V1] = E->Weight;
}
 
MGraph BuildGraph()
{
   
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
     
    scanf("%d", &Nv);   /* 读入顶点个数 */
    Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
     
    scanf("%d", &(Graph->Ne));   /* 读入边数 */
    if ( Graph->Ne != 0 ) {
    /* 如果有边 */ 
        E = (Edge)malloc(sizeof(struct ENode)); /* 建立边结点 */ 
        /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
        for (i=0; i<Graph->Ne; i++) {
   
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
            /* 注意：如果权重不是整型，Weight的读入格式要改 */
            InsertEdge( Graph, E );
        }
    } 
 
    /* 如果顶点有数据的话，读入数据 */
    for (V=0; V<Graph->Nv; V++) 
        scanf(" %c", &(Graph->Data[V]));
 
    return Graph;
}

三、邻接链表：数组与链表相结合

邻接表基本概念：

N个头指针+2E个结点（每个结点至少2个域）
方便计算度吗？
对于无向图：方便计算度
对于有向图：只能计算初度，需要构造逆邻接表（存指向自己的边）来方便计算入度
不方便检查任意一对顶点存在边

邻接表特点：

邻接表表示不唯一

适合于稀疏图存储
存储空间O（n+e）

无向图的邻接表

有向图的邻接表

五、邻接链表的建立

无向图邻接表：

//边表结点
typedef struct EdgeNode
{
   
	int adjvex;  //该顶点对应的下标
	int weight;  //权值，非网图不需要
	struct EdgeNode* next; //指向下一个邻接点
}EdgeNode;

//顶点表结点
typedef struct VertexNode
{
   
	char data; //存储顶点信息
	EdgeNode* fistedge; //边表头指针
}VertexNode，AdjList[MAXWEX];

typedef struct
{
   
	AdjList adjList;  //顶点表
	int nume;  //图中当前边数
	int numv;  //图中当前顶点数
}GraphAdjList;
void CreateALGraph(GraphAdjList* G)
{
   
	int i, j, k;
	EdgeNode* e; //边表结点
	printf("请分别输入顶点数和边数：\n");//若有权值，可在加入 w
	scanf("%d %d",&G->numv,&G->nume);
	//读入顶点信息
	for (i = 0; i < G->numv; i++)
	{
   
		scanf("%c", &G->adjList[i].data); //输入顶点信息
		G->adjList[i].fistedge = NULL;    //边表置为空表
	}

	//建立边表
	for (k = 0; k < G->nume; k++)
	{
   
		printf("请输入边（Vi,Vj）上的顶点序号：\n");
		scanf("%d %d", &i, &j);

		//类似于头插法
		e = (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = j;   //邻接序号为 j -> i 指向的顶点的下标
		//e->weight = w;//存储该边的权值
		e->next = G->adjList[i].fistedge;  //将 e 的指针指向当前顶点指向的结点
		G->adjList[i].fistedge = e;   //将当前顶点是指针指向 e
		//对于无向图而言,对称的
		e = (EdgeNode*)malloc(sizeof(EdgeNode));
		e->adjvex = i;    //邻接序号为 i -> j 指向的顶点的下标
		//e->weight = w;//存储该边的权值
		e->next = G->adjList[j].fistedge;  //将 e 的指针指向当前顶点指向的结点
		G->adjList[j].fistedge = e;   //将当前顶点是指针指向 e
	}
}

邻接表的综合建立：

/* 图的邻接表表示法 */
 
#define MaxVertexNum 100 /* 最大顶点数设为100 */
typedef int Vertex;         /* 用顶点下标表示顶点,为整型 */
typedef int WeightType;        /* 边的权值设为整型 */
typedef char DataType;        /* 顶点存储的数据类型设为字符型 */
 
/* 边的定义 */
typedef struct ENode *PtrToENode;
struct ENode{
   
    Vertex V1, V2;      /* 有向边<V1, V2> */
    WeightType Weight;  /* 权重 */
};
typedef PtrToENode Edge;
 
/* 邻接点的定义 */
typedef struct AdjVNode *PtrToAdjVNode; 
struct AdjVNode{
   
    Vertex AdjV;        /* 邻接点下标 */
    WeightType Weight;  /* 边权重 */
    PtrToAdjVNode Next;    /* 指向下一个邻接点的指针 */
};
 
/* 顶点表头结点的定义 */
typedef struct Vnode{
   
    PtrToAdjVNode FirstEdge;/* 边表头指针 */
    DataType Data;            /* 存顶点的数据 */
    /* 注意：很多情况下，顶点无数据，此时Data可以不用出现 */
} AdjList[MaxVertexNum];    /* AdjList是邻接表类型 */
 
/* 图结点的定义 */
typedef struct GNode *PtrToGNode;
struct GNode{
     
    int Nv;     /* 顶点数 */
    int Ne;     /* 边数 */
    AdjList G;  /* 邻接表 */
};
typedef PtrToGNode LGraph; /* 以邻接表方式存储的图类型 */
 
 
 
LGraph CreateGraph( int VertexNum )
{
    /* 初始化一个有VertexNum个顶点但没有边的图 */
    Vertex V;
    LGraph Graph;
     
    Graph = (LGraph)malloc( sizeof(struct GNode) ); /* 建立图 */
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    /* 初始化邻接表头指针 */
    /* 注意：这里默认顶点编号从0开始，到(Graph->Nv - 1) */
       for (V=0; V<Graph->Nv; V++)
        Graph->G[V].FirstEdge = NULL;
             
    return Graph; 
}
        
void InsertEdge( LGraph Graph, Edge E )
{
   
    PtrToAdjVNode NewNode;
     
    /* 插入边 <V1, V2> */
    /* 为V2建立新的邻接点 */
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V2;
    NewNode->Weight = E->Weight;
    /* 将V2插入V1的表头 */
    NewNode->Next = Graph->G[E->V1].FirstEdge;
    Graph->G[E->V1].FirstEdge = NewNode;
         
    /* 若是无向图，还要插入边 <V2, V1> */
    /* 为V1建立新的邻接点 */
    NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
    NewNode->AdjV = E->V1;
    NewNode->Weight = E->Weight;
    /* 将V1插入V2的表头 */
    NewNode->Next = Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge = NewNode;
}
 
LGraph BuildGraph()
{
   
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
     
    scanf("%d", &Nv);   /* 读入顶点个数 */
    Graph = CreateGraph(Nv); /* 初始化有Nv个顶点但没有边的图 */ 
     
    scanf("%d", &(Graph->Ne));   /* 读入边数 */
    if ( Graph->Ne != 0 ) {
    /* 如果有边 */ 
        E = (Edge)malloc( sizeof(struct ENode) ); /* 建立边结点 */ 
        /* 读入边，格式为"起点 终点 权重"，插入邻接矩阵 */
        for (i=0; i<Graph->Ne; i++) {
   
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight); 
            /* 注意：如果权重不是整型，Weight的读入格式要改 */
            InsertEdge( Graph, E );
        }
    } 
 
    /* 如果顶点有数据的话，读入数据 */
    for (V=0; V<Graph->Nv; V++) 
        scanf(" %c", &(Graph->G[V].Data));
 
    return Graph;
}

邻接表的遍历：


//不能传指针，防止遍历时改变原来结构
void PrintGraphAdjList(GraphAdjList G)
{
   
	for (int i = 0; i < G.numv; i++)
	{
   
		EdgeNode* p = G.adjList[i].fistedge;
		printf("该顶点为 %c：\n", G.adjList[i].data);
		while (p)
		{
   
			printf("（%c,%c），权值为 %d \n", G.adjList[i].data, G.adjList[p->adjvex].data, p->weight);
			p = p->next;
		}
		printf("\n");
	}
}

图的存储结构

文章目录

一、 邻接矩阵

二、 邻接矩阵的主要特点

三、邻接链表

四、 邻接矩阵的建立

五、 邻接链表的建立

一、邻接矩阵

举例：无向图和有向图的对比

二、邻接矩阵的主要特点：

无向图：

有向图：

网：需要存权值（W）

四、邻接矩阵的建立

无向网图邻接矩阵的建立：

邻接矩阵的综合建立：

三、邻接链表：数组与链表相结合

邻接表基本概念：

邻接表特点：

无向图的邻接表

有向图的邻接表

五、邻接链表的建立

无向图邻接表：

邻接表的综合建立：

邻接表的遍历：

一、邻接矩阵

二、邻接矩阵的主要特点

四、邻接矩阵的建立

五、邻接链表的建立