图(Graph)G由两个集合V和E组成，记为：G=(V,E)，其中V是顶点的有穷非空集合(其实就是顶点)，E是V中顶点偶对的有穷集合(就是边)。V(G)和E(G)通常分别表示图G的顶点集合以及边集合，E(G)可以为空集合，但是此时的图只有顶点，没有边。
分类：
下面是图的示例：
#pragma once
# include <stdio.h>
# include <stdlib.h>
# define MaxVertexnum 100
typedef int ElemType;
//邻接矩阵
typedef struct graph
{
int Nv; //顶点数
int Ne; //边数
int Data[MaxVertexnum]; //存放顶点数据
int Weight[MaxVertexnum][MaxVertexnum]; //存放权重
}graph,*MGraph;
typedef struct edge
{
int V1, V2; //V1到V2
int Weight; //边用来存放权重
}*Edge;
//初始化有Vertnex个顶点的图
void InitGraph(MGraph G, int Vertnex)
{
G->Nv = Vertnex; //有Vertnex个顶点
G->Ne = 0; //边数为0
//初始化每条边的权重
for (int i = 0; i < Vertnex; i++)
{
for (int j = 0; j < Vertnex; j++)
G->Weight[i][j] = 0;
}
}
//插入边的权重
void InsertEdge(MGraph G,Edge E)
{
G->Weight[E->V1][E->V2] = E->Weight;
G->Weight[E->V2][E->V1] = E->Weight;
}表头结点表：由所有的表头结点以顺序结构的形式存储，以便计算机随机访问任一顶点的边链表 。表头结点包括**数据域和链域(指向边表指针)**两部分组成。
边表：
边链表中边结点包括邻接点域，数据域，链域三部分。邻接点域指的是指向同类的指针，数据域指的是存放与边相关的一些信息(权重),链域指的是与头结点链域中指针所指向的指针域。
相信大家对于这个理解还是比较的深刻的，我这个小菜鸡就不瞎哔哔了^ - ^。
现在脑子里应该有这样一副画面，有一个长方形块，这个长方形块有若干个小块组成，每个小块有两个部分，第一部分是数据域，第二部分是指针域，这个指针域就指向边表。
代码奉上：
typedef struct EdgeNode //边结点
{
int weight; //存放权重
struct EdgeNode *next; //指向边结点
int local; //该边指向的顶点
}EdgeNode;
/*边链表中边结点包括邻接点域，数据域，链域，邻接点域指示与顶点v邻接的位置(指针)，数据域存放与边相关的数据，如：权重。链域指示与顶点v
邻接的下一条边的结点*/
typedef struct VNode //顶点结点
{
int data; //顶点数据
EdgeNode *firstVertnex; //指向边
}VNode,AdjList[MaxVertexnum];
/*表头结点表：由所有表头结点以顺序结构的形式存储，以便可以随机访问任一顶点的边链表
表头结点包括数据域，链域，数据域存放顶点的一些数据,链域用于指向链表中第一个结点(即与定点v邻接的第一个邻接点)*/
typedef struct Adjgraph
{
int Nv;
int Ne;
AdjList List;
}AdjMGraph;
void InitAdjGraph(AdjMGraph* G)
{
printf("请输入顶点数和边数(空格分隔)!\n");
int Nv, Ne;
scanf("%d %d", &G->Nv, &G->Ne);
printf("请输入顶点数据:\n");
for (int i = 1; i <= G->Nv; i++)
{
printf("第%d个顶点数据为:\n",i);
scanf("%d", &G->List[i].data); //收入每一个顶点的数据
G->List[i].firstVertnex = NULL; //每个顶点的指针域置为空
}
getchar();
}
/*接下来要进行放入有效数据，把权重放入邻接表中,由于是生成无向图，所以此时要生成两个结点*/
void CreateAdjGraph(AdjMGraph *G)
{
printf("一共有%d条边!\n", G->Ne);
printf("请输入两个顶点以及二者之间的权重(中间用空格分隔):\n");
int W, V,weight;
for (int i = 1; i <= G->Ne; i++)
{
scanf("%d %d %d", &W, &V,&weight);
EdgeNode *p = (EdgeNode*)malloc(sizeof(EdgeNode));
p->local = V;
p->weight = weight;
p->next = G->List[W].firstVertnex;
G->List[W].firstVertnex= p;
EdgeNode *q = (EdgeNode*)malloc(sizeof(EdgeNode));
q->local = W;
q->weight = weight;
q->next = G->List[V].firstVertnex;
G->List[V].firstVertnex = q;
}
}打印出邻接矩阵：
void PrintAdjGraph(AdjMGraph *G)
{
printf("将打印出邻接表的示意图!\n");
for (int i = 1; i <= G->Nv; i++)
{
printf("%-3d->", i);
while (G->List[i].firstVertnex != NULL)
{
printf("%-3d---weight:%-3d->",G->List[i].firstVertnex->local,G->List[i].firstVertnex->weight);
G->List[i].firstVertnex = G->List[i].firstVertnex->next;
}
if (G->List[i].firstVertnex == NULL)
printf("!\n");
}
}接下来，main函数(里面包含了邻接矩阵的打印)
# include <stdio.h>
# include <stdlib.h>
# include "Graph.h"
int main()
{
printf("用邻接矩阵创建无向图!\n");
//要建立一个有vertnex个顶点无边的图
int vertnex;
printf("请输入有图中有多少个顶点:\n");
scanf("%d", &vertnex);
//建立一个图，首先要声明一个图
MGraph G;
G = (MGraph)malloc(sizeof(graph));
//接着要初始化图
InitGraph(G, vertnex);
//接着往图中插入数据
printf("请输入边数:\n");
int Ne;
scanf("%d", &Ne);
if (Ne != 0)
{
printf("请输入顶点和权重(空格分隔!)\n");
for (int i = 0; i < Ne; i++)
{
Edge E;
E = (Edge)malloc(sizeof(edge));
scanf("%d %d %d",&E->V1,&E->V2,&E->Weight );
//接下来把这些数据放入图中和边中
InsertEdge(G, E);
}
printf("请输入顶点的数据:\n");
for (int i = 0; i < vertnex; i++)
scanf("%d", &G->Data[i]);
}
printf("------------------------------------------------\n");
printf("将打印出邻接矩阵!\n\n");
for (int j = 0; j < vertnex; j++)
{
for (int i = 0; i < vertnex; i++)
printf("%5d", G->Weight[i][j]);
printf("\n");
}
printf("将打印顶点元素中的数据!\n");
for (int i = 0; i < vertnex; i++)
printf("%3d", G->Data[i]);
printf("-------------------------------------------------\n");
printf("用邻接表创建无向图\n");
AdjMGraph *Graph = (Adjgraph*)malloc(sizeof(Adjgraph));
InitAdjGraph(Graph);
CreateAdjGraph(Graph);
PrintAdjGraph(Graph);
system("pause");
return 0;
}代码运行截图：
