邻接表表示图的实例代码

#include<iostream>
#include<malloc.h>

using namespace std;

#define VERTEX_MAX 20

typedef struct edgeNode{
    int Vertex;//顶点序号
    int weight;//权值
    struct edgeNode *next;//指向有边的下一个顶点 
}EdgeNode;

typedef struct{
    EdgeNode* AdjList[VERTEX_MAX];//指向每个顶点的指针 
    int VertexBum,EdgeNum;//图的顶点的数量和边的数量 
    int GraphType;//图的类型：0：有向图 1：无向图 
}ListGraph;

void CreatGraph(ListGraph *G);//生成图的邻接表 
void OutList(ListGraph *G);//输出邻接表 

void CreatGraph(ListGraph *G){
    int i,weight;
    int start,end;
    EdgeNode *s;
    for(int i=1;i<=G->VertexBum;i++)//清空图的顶点 
        G->AdjList[i]=NULL;
    for(int i=1;i<=G->EdgeNum;i++){//输入各边的两个顶点 
        getchar();
        cout<<"第"<<i<<"条边:"; 
        cin>>start>>end>>weight;                //输入边的起点个终点 
        s=(EdgeNode *)malloc(sizeof(EdgeNode));//申请一个保存顶点的内存 
        s->next=G->AdjList[start];              //插入到邻接表中   
        s->Vertex= end;                         //保存终点编号 
        s->weight=weight;                       //保存权值 
        G->AdjList[start]=s;                    //邻接表对应顶点指向该点
        if(G->GraphType==0){                    //若是无向图，再插入到终点的边链中 
            s=(EdgeNode *)malloc(sizeof(EdgeNode)); 
            s->next = G->AdjList[end];
            s->Vertex = start;
            s->weight = weight;
            G->AdjList[end] = s;
        } 
    }
}

void OutList(ListGraph *G){
    int i;
    EdgeNode *s;
    for(int i=1;i<=G->VertexBum;i++){
        cout<<"顶点"<<i;
        s=G->AdjList[i];
        while(s){
            cout<<"->"<<s->Vertex<<"("<<s->weight<<")";
            s = s->next;
        }
        cout<<endl;
    } 
}

int main(){
    ListGraph G;
    cout<<"输入生成图的类型（0：无向图   1：有向图）";
    cin>>G.GraphType;
    cout<<"请输入图的顶点数量个边数量:";
    cin>>G.VertexBum>>G.EdgeNum;
    cout<<"输入构造各边的两个顶点及权值（用空格分隔）"<<endl;
    CreatGraph(&G);
    cout<<"输出图的邻接表";
    OutList(&G);
    getchar();
    
return 0;
}

实例输入：

运行结果截图:

运行截图.png

邻接表表示图的实例代码

推荐阅读更多精彩内容