小白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;V<Graph->Nv;V++)
for((W=0;W<Graph->Nv;W++))
Graph->G[V][M] = 0;//或者INFINITY，表示这两个顶点之间是没有边的
return Graph
}
小白BG.3 邻接矩阵表示的图——插入边
typedef struct ENode *PtrToENode;
struct ENode{
Vertex V1,V2;//有向边<V1,V2>，V1V2两个顶点一个出发点一个终点
WeightType Weight;//权重，有权图才需要。权重的类型是WeightType
};
typedef PtrToENode Edge;
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;
}
小白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;V<Graph->Nv;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<Nv;i++)
for(j=0;j<Nv;j++)
G[i][j] = 0;//或INFINITY，把矩阵所有元素先初始化为0或者无穷大
scanf("%d",&Ne);
for(i = 0;i < Ne; i++){
scanf("%d %d %d",&v1,&v2,&w);
//InsertEdge
G[v1][v2] = w;
G[v2][v1] = w;
}
}
小白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;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 AdjNode));
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 AdjNode));
NewNode->AdjV = E->V1;
NewNode->Weight = E->Weight
//将V2插入到V1的表头
NewNode->Next = Graph->G[E->V2].FirstEdge;
Graph->G[E->V2].FirstEdge = NewNode;
}
