[数据结构与算法]c++实现图的表示，数据结构之图（一）

数据结构之图（一）

1. 邻接矩阵

将图表示为一个矩阵。

输入：

5 6          #顶点数和边数
A B C D E    #顶点信息
0 4 6        #边的下标(0,4)-->6和权值
1 0 9
1 2 3
2 0 2
2 3 5
3 4 1

1. 代码实现：创建邻接矩阵并打印。

#include <iostream>
using namespace std;

#define MAXVEX 100
#define INF_M 65535
typedef char VertexType; //顶点类型
typedef int EdgeType;   //边上权值

typedef struct{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;


void CreateGraph(MGraph *G){
    int i,j,k,w;
    cout<<"请输入顶点数和边数："<<endl;
    //scanf("%d,%d",&G->numVertexes,&G->numEdges);
    cin>>G->numVertexes>>G->numEdges;
    for(i = 0; i < G->numVertexes; i++){
        //scanf("%d",&G->vexs[i]);
        cin>>G->vexs[i];
    }
    for(i = 0; i < G->numVertexes; i++){
        for(i = 0; i < G->numVertexes; i++){
            G->arc[i][j] = 0;
        }
    }
    for(k = 0; k < G->numEdges; k++){
        //printf("请输入边的下标和权重：\n")；
        cout<<"请输入边的下标和权重:"<<endl;
        //scanf("%d %d %d",&i,&j,&w);
        cin>>i>>j>>w;
        G->arc[i][j] = w;
        G->arc[j][i] = G->arc[i][j];//无向图是一个对称的。
    }

}

void printGraph(MGraph *G){
    int i,j;
    for(i = 0; i < G->numVertexes; i++){
        for(j = 0; j < G->numVertexes; j++){
            //printf("%d\t", G->arc[i][j]);
            cout<<G->arc[i][j]<<"\t";
        }
        cout<<endl;
    }
}

int main()
{
    MGraph *G = new MGraph;
    CreateGraph(G);
    printGraph(G);
    return 0;
}

2. 邻接表

用邻接表来表示图数据

1. 代码实现：创建邻接表并打印。

//边表节点
typedef struct EdgeNode{
    int adjvex;
    EdgeType weight;
    struct EdgeNode *next;
}EdgeNode;

//顶点表节点
typedef struct VertexNode{
    VertexType data;
    EdgeNode *firstedge; //边表类型的指针
}VertexNode,AdjList[MAXVEX];

//邻接表
typedef struct{
    AdjList adjList;
    int numVertexes,numEdges;
}GraphAdjList;
//结构体指针变量用->,普通结构体变量用.;

void CreateGraphA(GraphAdjList *G){
    int i,j,k,w;
    EdgeNode *e; //生成一个边表类型的指针
    cout<<"请输入顶点数和边数：\n";
    cin>>G->numVertexes>>G->numEdges;
    for(i = 0; i < G->numVertexes; i++){
        cin>>G->adjList[i].data;
        G->adjList[i].firstedge = NULL;
    }
    for(k = 0;k < G->numEdges; k++){
        cout<<"请输入边的顶点信息：\n";
        cin>>i>>j>>w;
        //头插法插入边表结点。
        e = (EdgeNode*)malloc(sizeof(EdgeNode));//申请内存空间，生成内存结点。
        e->adjvex = j;
        e->next = G->adjList[i].firstedge;
        e->weight = w;
        G->adjList[i].firstedge = e;

        e = (EdgeNode*)malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->adjList[j].firstedge;
        e->weight = w;
        G->adjList[j].firstedge = e;
    }
}

void printGraphA(GraphAdjList *G){
    int i,j;
    EdgeNode *GA;
    for(i = 0; i < G->numVertexes; i++){
        GA = G->adjList[i].firstedge;
        cout<<G->adjList[i].data<<":";
        while(GA != NULL){
            cout<<GA->adjvex<<" "<<GA->weight<<";";
            GA = GA->next;
        }
      cout<<endl;
    }
}

int main()
{
    GraphAdjList *G = new GraphAdjList;
    CreateGraphA(G);
    printGraphA(G);
    return 0;
}