《数据结构基础知识》如何建立一张图

存储图的两种主要方法

• 邻接矩阵
• 邻接表

用邻接矩阵表示图

$$G[i][j]= \begin{cases} 1 &若<Vi,Vj>是G中的边\\ 0 &无边 \end{cases}$$

上述为无权图，如果是有权图则将1改为权值

以邻接矩阵存储的图结构

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  //顶点数
    int Ne;  //边数
    WeightType G[MaxVertexNum][MaxVertexNum];
      DataType Data[MaxVertexNum];
};
typedef PtrToGNode MGraph; //以邻接矩阵存储的图类型

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

typedef int Vertex;
MGraph CreateGraph(int VertexNum)
{
    vertex V,W;
    MGraph Graph;

    Graph=(MGraph)malloc(sizeof(struct GNode));
    Graph->Nv=VertexNum;
    Graph->Ne=0;

    for(V=0;V<Graph->Nv;V++){
        for(W=0;W<Graph->Nv;W++){
            Graph->G[V][W]=0;
        }
    }

    return Graph;
}

向MGraph中插入边

typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1,V2;       //有向边<V1,V2>
    WeightType Weight;  //权重
};
typedef PtrToENode Edge;

void InsertEdge(MGraph Graph,Edge E)
{
    //插入边<V1,V2>
    Graph->G[E->V1][E->V2]=E->Weight;
    //如果是无向图，还需要插入边<V1,V2>
    Graph->G[E->V2][E->V1]=E->Weight;
}

完整的建立一个MGraph

输入格式

Nv Ne
V1 V2 Weight
……

标准版本

MGraph BuildGraph()
{
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv,i;

    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("%d",&(Graph->Data[V]));
    }

    return Graph;
}

简略版本

在我们做题时，时间不是很充裕，不足以让我们一个一个函数写清楚的情况下
我们可以直接将上述多个函数合并

int G[MAXN][MAXN],Nv,Ne;
void BuildGraph()
{
    int i,j,v1,v2,w;

    scanf("%d",&Nv);
    // CrertGraph
    for(i=0;i<Nv;i++){
        for(j=0;j<Nv;j++){
            G[i][j]=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;
    }
}

用邻接表表示图

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

邻接表结构

typedef struct GNode *PtrToGNode;
struct GNode{
    int Nv;  //顶点数
    int Ne;  //边数
    AdjList G;  //邻接表
};
typedef PtrToGNode LGraph; //以邻接表存储的图类型

//邻接表结点数组G[N]
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    DataType Data;
}AdjList[MaxVertexNum];//邻接表G[N]类型--指针数组

//边结点结构
typedef struct AdjVNode *PtrToAdjVNode;
struct AdjVNode{
  Vertex AdjV;  //邻接点的G[N]下标
  WeightType Weight; //边权重
  PtrToAdjVNode Next;
};

LGraph初始化有顶点没有边

typedef int Vertex;
LGraph CreateGraph(int VertexNum)
{
    vertex V,W;
    LGraph Graph;

    Graph=(LGraph)malloc(sizeof(struct GNode));
    Graph->Nv=VertexNum;
    Graph->Ne=0;

    for(V=0;V<Graph->Nv;V++){
        Graph->G[V].FirstEdge=NULL;
    }

    return Graph;
}

向LGraph中插入边

typedef struct ENode *PtrToENode;
struct ENode{
    Vertex V1,V2;       //有向边<V1,V2>
    WeightType Weight;  //权重
};
typedef PtrToENode Edge;

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;
    //将V1插入V2的表头
    NewNode->Next=Graph->G[E->V2].FirstEdge;
    Graph->G[E->V2].FirstEdge=NewNode;
}

完整建立一个LGraph

完整版本的代码（同邻接矩阵）

LGraph BuildGraph()
{
    LGraph Graph;
    Edge E;
    Vertex V;
    int Nv,i;

    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("%d",&(Graph->Data[V]));
    }

    return Graph;
}