图的存储结构
标签(空格分隔): 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;
}
标签:存储,adjList,struct,int,邻接矩阵,arc,顶点,结构
From: https://www.cnblogs.com/wa2211lq/p/17461451.html