图论图的表示

图的定义：
表示多对多的关系；包含顶点和边；分为有向图和无向图；无向图是对称的；
如图
图论图的表示
图有两种表示方式；
邻接矩阵：
二维数组表示；下标表示节点，内容可以是权重，如G[i][j] ,表示i和j节点的关系，如果
G[i][j] 中的内容0，表示无连接，1表示有连接，或可以用其它值表示权重;

图的邻接矩阵表示;
#define Maxnum 100  //最大节点数
#define  null  0 // 空值
typedef struct ENode* Edge;
struct ENode
{
	int V1,V2; 两个顶点; <V1,V2> V1->V2的有向边
	int weight; //权值
}
typedef struct GNode * MGraph;
struct GNode
{
	int Nv; // 图中的顶点数;
	int Ne; // 图中的边数;
	int G[Maxnum][Maxnum] //矩阵保存数据;
}
MGraph CreateGraph(int VertexNum) //建立空图
{
	MGraph G = (MGraph)malloc(sizeof(struct GNode));
	G->Nv = VertexNum;
	G->Ne = 0;
	for(int i=0;i<G->Nv;i++)
		for(int j=0;j<G->Nv;j++)
			G->G[i][j] = null;
	return MGraph;
}
void InsertEdge(MGraph Graph, Edge E) //向图中插入边
{
	Graph->G[E->V1][E->V2] = E->weight;
	//若为无向边，还要再存一边;
	Graph->G[E->V2][E->V1] = E->weight;
}
MGraph BuildGraph() //初始化图
{
	MGraph G;
	Edge E;
	int Nv;
	scanf("%d",&Nv); //输入顶点数
	G =  CreateGraph(Nv);
	scanf("%d",&G->Ne); //输入边数
	if(G->Ne!=0) 
	{
		E = (Edge)malloc(sizeof(struct ENode));
		for(int i=0;i<G->Ne;i++) //插入边数
		{
			 scanf("%d%d%d",&E->V1,&E->V2,&E->weight); //输入边
			 InsertEdge(G,E);// 插入边;
		}
	}
	return G;
}

邻接表实现图
图论图的表示

图的邻接表实现
#define Maxnum 100  // 最大顶点个数
typedef struct ENode * Edge;
struct ENode
{
	int V1,V2; // <V1,V2>;
	int weight; // 权值
}

typedef struct AdjNode * PtrToAdjVNode;
struct AdjNode
{
	int AdjV; // 下标
	int weight;//权值
	PtrToAdjVNode next; // 指向下一个节点;
}

typedef struct Vnode
{
	PtrToAdjVNode FirstEdge; // 头指针;
}AdjList[Maxnum];

typedef struct GNode * LGraph ;
struct GNode
 {
	int Nv;     /* 顶点数 */
	int Ne;     /* 边数   */
	AdjList G;  /* 邻接表 */
};
LGraph CreateGraph(int VertexNum) // 初始化一个无边的图
{
	LGraph  G = (LGraph)malloc(sizeof(struct GNode));
	G->Nv = VertexNum;
	G->Ne = 0;
	for(int i=0;i<G->G->Nv;i++)
	{
		G->G[i].FirstEdge = NULL;
	}
}
void InsertEdge(LGraph Graph, Edge E) // 插入边
{
	PtrToAdjVNode  NewNode;
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode));
	NewNode = E->V2;
	NewNode = E->weight;
	NewNode->next = Graph->G[E->V1];
	Graph->G[E->V1].FirstEdge = NewNode;
	// 若是无向图，则V2->V1;
	NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
	NewNode = E->V1;
	NewNode = E->weight;
	NewNode->next = Graph->G[E->V2];
	Graph->G[E->V2].FirstEdge = NewNode;
}
LGraph BuildGraph() // 初始化图
{
	LGraph Graph;
	Edge E;
	int Nv;
	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);
			InsertEdge(Graph, E);
		}
	}
	return Graph;
}

图论 图的表示

相关推荐