数据结构和算法之如何建立图

小白BG.1 邻接矩阵表示的图结点的结构

typedef struct GNode *PtrToGNode;//PtrToGNode是指向GNode的一个指针
struct GNode{
int Nv;//顶点数
int Ne;//边数
WeightType G[MaxVertexNum][MaxVertexNum];
DataType Data[MaxVertexNum];//存顶点的数据
};
typedef PtrToGNode MGraph;//以邻接矩阵存储的图类型。定义为指向节点的指针。因为要用到的时候
一个指针远远比一整个图来的快捷

小白BG.2 邻接矩阵表示的图——初始化

初始化一个有VertexNum个顶点但没有边的图

typedef int Vertex;//用顶点下标表示顶点，为整型
MGraph CreateGraph(int VertexNum)//VertexNum这个顶点数真的是整数，
{
Vertex V , W;//我们在说V跟W的时候不是在说整数，而是顶点
MGraph Graph;
Graph = (MGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
//注意：这里默认顶点编号从0开始，到(Graph->Nv - 1)
for(V=0;VNv;V++)
for((W=0;WNv;W++))
Graph->G[V][M] = 0;//或者INFINITY，表示这两个顶点之间是没有边的
return Graph
}

小白BG.3 邻接矩阵表示的图——插入边

typedef struct ENode *PtrToENode;
struct ENode{
Vertex V1,V2;//有向边，V1V2两个顶点一个出发点一个终点
WeightType Weight;//权重，有权图才需要。权重的类型是WeightType
};
typedef PtrToENode Edge;
void InsertEdge(MGraph Graph,Edge E)
{
//插入边，这是一条边
Graph->G[E->V1][E->V2] = E->Weight;
//无向图的话还需要一条边(一共两条)，
Graph->G[E->V2][E->V1] = E->Weight;
}

小白BG.4 邻接矩阵表示的图——建立图

完整的建立一个MGraph

输入格式

1. Nv Ne

2. V1 V2 Weight

3. ......

MGraph BuildGraph()
{
MGraph Graph;
scanf("%d",&Nv);
Graph = CreateGraph(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);
}
}
//如果顶点有数据的话，读入数据
for(V=0;VNv;V++)
scanf("%c",&(Graph->Data[V]));
return Graph;
}

简易建法

int G[MAXN][MAXN],Nv,Ne;//声明为全局变量
void BuildGraph()
{
int i,j,v1,v2,w;
scanf("%d",&Nv);
//CreateGraph
for(i=0;i 
 
小白BG.5 邻接表表示的图结点的结构
 

邻接表：G[N]为指针数组，对应矩阵每一行一个链表，只存非0元素

typedef struct GNode *PtrToGNode;
struct GNode {
int Nv;//顶点数
int Ne;//边数
AdjList G;//邻接表
};
typedef PtrToGNode LGraph;
//以邻接表方式存储的图类型
//AdjList是自己定义的
typedef struct Vnode{
PtrToAdjVNode FirstEdge;
DataType Data;//存顶点的数据
}AdjList[MaxVertexNum];//AdjList是邻接表类型
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
Vertex AdjV;//邻接点下标，定义为整型
WeightType Weight;//边权重
PtrToAdjVNode Next;
};

小白BG.6 邻接表表示的图——建立图

初始化一个有VertexNum个顶点但没有边的图

typedef int Vertex;//用顶点下标表示顶点，为整型
LGraph CreateGraph(int VertexNum)
{
Vertex V,W;
LGraph Graph;
Graph = (LGraph)malloc(sizeof(struct GNode));
Graph->Nv = VertexNum;
Graph->Ne = 0;
//没有边的意思是每个顶点跟着的那个链表都是空的
//注意：这里默认顶点编号从0开始，到(Graph->Nv - 1)
for(V=0;VNv;V++)
Graph->G[V].FirstEdge = NULL;
return Graph;
}

void InsertEdge(LGraph Graph,Edge E)
{
PtrToAdjVNode NewNode;
//-------------------插入边------------------------------
//为V2建立新的邻接点
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode));
NewNode->AdjV = E->V2;
NewNode->Weight = E->Weight
//将V2插入到V1的表头
NewNode->Next = Graph->G[E->V1].FirstEdge;
Graph->G[E->V1].FirstEdge = NewNode;
//-------------------若是无向图，还需插入边------------------
//为V1建立新的邻接点
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjNode));
NewNode->AdjV = E->V1;
NewNode->Weight = E->Weight
//将V2插入到V1的表头
NewNode->Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}