图的邻接表表示法

图的邻接表表示法

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#define MaxVertexNum 1010
#define INF (1<<31)-1

using namespace std;

//图的邻接矩阵表示法

//边结构
typedef struct ENode
{
    int V1, V2;         //一组边
    int Weight;         //边的权重
}*Edge;

//邻接点结构
struct AdjNode
{
    int Adj;            //邻接点下标
    int Weight;         //边权重
    AdjNode *Next;      //指向下一个表头
};

//表头邻接点结构
typedef struct VNode
{
    AdjNode *Next;     //指向下一个邻接点
    int Data;           //顶点数据
}*AdjList[MaxVertexNum];

//图结构
typedef struct GNode
{
    int Vertex_num;     //顶点数目
    int EdgeNum;        //边数目
    AdjList G;          //邻接表
}*Graph;

//图初始化
Graph InitGraph(int VertexNum)
{
    Graph G;

    G = (Graph)malloc(sizeof(GNode));
    G->Vertex_num = VertexNum;
    G->EdgeNum = 0;
    for(int i = 0; i < G->Vertex_num; i++)
        G->G[i]->Next = NULL;

    return G;
}

//图中边的插入
void InsertEdge(Graph G, Edge E)
{
    AdjNode *NewNode;
    //为V2建立邻接点
    NewNode = (AdjNode*)malloc(sizeof(AdjNode));
    NewNode->Adj = E->V2;
    NewNode->Weight = E->Weight;
    //将V2插入V1的表头------头插法
    NewNode->Next = G->G[E->V1]->Next;
    G->G[E->V1]->Next = NewNode;

    //若为无向图
    //为V1建立邻接点
    NewNode = (AdjNode*)malloc(sizeof(AdjNode));
    NewNode->Adj = E->V1;
    NewNode->Weight = E->Weight;
    //将V1插入V2的表头
    NewNode->Next = G->G[E->V2]->Next;
    G->G[E->V2]->Next= NewNode;
}

Graph CreatGraph()
{
    Graph G;
    Edge E;
    int Vertex;
    cin >> Vertex;
    G = InitGraph(Vertex);          //图初始化
    cin >> G->EdgeNum;              //输入边数

    if(G->EdgeNum)
    {
        E = (Edge)malloc(sizeof(ENode));

        for(int i = 0; i < G->Vertex_num; i++)
        {
            cin >> E->V1 >> E->V2 >> E->Weight;
            InsertEdge(G, E);       //将边插入G
        }
    }

    //输入顶点数据
    for(int i = 0; i < G->Vertex_num; i++) cin >> G->G[i]->Data;
}

int main()
{

    return 0;
}