图的创建（邻接表，邻接矩阵）（浙大数据结构代码）

 邻接矩阵的定义：

/**
    邻接矩阵的定义：
*/
/**
#include 
#include 
 
using namespace std;
 
#define MaxVertexNum 100
#define INF 1e9
typedef int Vertex; //vertex : 顶点
typedef int WeightType;
typedef char DataType;
 
//图结点的定义：
typedef struct GNode* PtrToGNode;
struct GNode
{
    int Ne; //边数
    int Nv; //顶点数
    WeightType G[MaxVertexNum][MaxVertexNum]; //邻接矩阵
    DataType Data[MaxVertexNum]; //存放顶点的数据
};
typedef PtrToGNode MGraph;
 
//边的定义
typedef struct ENode* PtrToENode;
struct ENode
{
    Vertex v1,v2;
    WeightType weight;
};
typedef PtrToENode Edge;
 
MGraph CreateGraph(int VertexNum); //初始化一个空图（只有顶点，没有边）
void InsertEdge(MGraph Graph,Edge E); //在图中插入一条边
MGraph BuildGraph(); //读入顶点和边建立一个完整的图
 
int main()
{
    int a[3][2];
    fill(*a,*(a+3),5);
    for(int i=0;i<3;++i)
        for(int j=0;j<2;++j)
            cout << a[i][j] << endl;
    cout << "Hello world!" << endl;
 
    BuildGraph();
    return 0;
}
 
 
MGraph CreateGraph(int VertexNum) //初始化一个空图（只有顶点，没有边）
{
    MGraph Graph;
    Graph=new GNode;
    Graph->Nv=VertexNum;
    Graph->Ne=0;
    for(Vertex v=0;vNv;++v)
        for(Vertex w=0;wNv;++w)
            Graph->G[v][w]=INF;
    return Graph;
}
 
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 Graph;
    int Nv;
    Edge E;
 
    scanf("%d",&Nv);
    Graph=CreateGraph(Nv);
 
    scanf("%d",&Graph->Ne);
 
    if(Graph->Ne!=0)
    {
        E=new ENode;
        for(Vertex i=0;iNe;++i)
        {
            scanf("%d%d%d",&E->v1,&E->v2,&E->weight);
            InsertEdge(Graph,E);
        }
    }
 
    // 如果有顶点数据，还要读入顶点数据
    for(Vertex i=0;iNe;++i)
        scanf("%d",&Graph->Data[i]);
    return Graph;
}
*/

 2)邻接表的定义：
    还是用vector 代替邻接表简便许多；

/**
    2)邻接表的定义：
    还是用vector 代替邻接表简便许多；
*/
 
#include 
#include 
 
using namespace std;
 
#define MaxVertexNum 100
#define INF 1e9
typedef int Vertex; //vertex : 顶点
typedef int WeightType;
typedef char DataType;
 
 
//边的定义
typedef struct ENode* PtrToENode;
struct ENode
{
    Vertex v1,v2; //边的两个顶点
    WeightType weight; //边的权值
};
typedef PtrToENode Edge;
 
//邻接点的定义：
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode
{
    Vertex AdjV; //邻接点下标
    WeightType weight; //边权重
    PtrToAdjVNode next; //指向下一个邻接点的指针
};
 
// 顶点表头结点的定义：
typedef struct VNode
{
    PtrToAdjVNode FirstEdge; //边表头指针
    DataType Data; //存放顶点的数据
}AdjList[MaxVertexNum];
 
//图结点的定义：
typedef struct GNode* PtrToGNode;
struct GNode
{
    int Ne; //边数
    int Nv; //顶点数
    AdjList G;
};
typedef PtrToGNode LGraph; //以邻接表方式存储图的类型
 
LGraph CreateGraph(int VertexNum); //初始化一个空图（只有顶点，没有边）
void InsertEdge(LGraph Graph,Edge E); //在图中插入一条边
LGraph BuildGraph(); //读入顶点和边建立一个完整的图
 
int main()
{
    int a[3][2];
    fill(*a,*(a+3),5);
    for(int i=0;i<3;++i)
        for(int j=0;j<2;++j)
            cout << a[i][j] << endl;
    cout << "Hello world!" << endl;
 
    BuildGraph();
    return 0;
}
 
 
LGraph CreateGraph(int VertexNum) //初始化一个空图（只有顶点，没有边）
{
    LGraph Graph;
    Graph=new GNode;
    Graph->Nv=VertexNum;
    Graph->Ne=0;
 
    for(Vertex v=0;vNv;++v) //初始化邻接表头指针
        Graph->G[v].FirstEdge=NULL;
 
    return Graph;
}
 
void InsertEdge(LGraph Graph,Edge E) //在图中插入一条边
{
    //加入一条边 
    PtrToAdjVNode NewNode;//加入一条边 
    NewNode = new AdjVNode;
    NewNode->weight=E->weight;
    NewNode->AdjV=E->v2;
    NewNode->next=Graph->G[E->v1].FirstEdge;
    Graph->G[E->v1].FirstEdge=NewNode;
 
    //无向图还要再加一条边
    NewNode = new AdjVNode;
    NewNode->weight=E->weight;
    NewNode->AdjV=E->v1;
    NewNode->next=Graph->G[E->v2].FirstEdge;
    Graph->G[E->v2].FirstEdge=NewNode;
}
 
LGraph BuildGraph() //读入顶点和边建立一个完整的图
{
    LGraph Graph;
    int Nv;
    Edge E;
 
    scanf("%d",&Nv);
    Graph=CreateGraph(Nv);
 
    scanf("%d",&Graph->Ne);
 
    if(Graph->Ne!=0)
    {
        E=new ENode;
        for(Vertex i=0;iNe;++i)
        {
            scanf("%d%d%d",&E->v1,&E->v2,&E->weight);
            InsertEdge(Graph,E);
        }
    }
 
    // 如果有顶点数据，还要读入顶点数据
    for(Vertex v=0;vNe;++v)
        scanf("%d",&Graph->G[v].Data);
    return Graph;
}//加入一条边