图(Graph)邻接矩阵表示

作者: 日常表白结衣 | 来源:发表于2017-08-09 10:17 被阅读0次

图(Graph)邻接矩阵表示
数据结构之图的存储结构邻接矩阵法
数据结构——图
图的五种存储结构
图的表示和存储结构
经典算法（三）最短路径
2019-03-13
数据结构课程第十周图
离散数学中的图矩阵
图 - Graph

图是一种表示多对多的关系
包含：
一组顶点：通常用V（Vertex）表示顶i点集合
一组边：通常用E（Edge）表示边的集合
边是顶点对：（v，w）<-E
有向边<v,w>表示从v指向w的边（单行线） v->w

邻接矩阵图表示

关于无向图的存储，可以使用一个长度为N(N+1)/2的一维数组A存储{G00,G01,G11,...,Gn-1 0,...,Gn-1 n-1}则Gij在A中对应的下标是(i*(i+1)/2+j)
在网络中，只要把G[i][j]的值定义为边<Vi,Vj>的权重即可。
关于图的度：从该点出发的边数为出度，指向该点的边数为入度。
无向图：对应行或者列非0元素的个数
有向图：对应行非0元素的个数是出度，对应列非0元素的个数是入度

/* 图的邻接矩阵表示法 */

#include<stdio.h>
#include<stdlib.h>

#define MaxVertexNum 100 //最大顶点数
#define INFINITY 0   

typedef int Vertex;     //顶点下标表示顶点
typedef int WeightType; //边的权值设置为整型
typedef char DataType;  //顶点存储的数据类型设为字符型

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

/* 图节点的定义 */
typedef struct GNode{
    int Nv; //顶点数
    int Ne; //边数
    WeightType G[MaxVertexNum][MaxVertexNum];   //邻接矩阵
    //DataType Data[MaxVertexNum];  //存储顶点的数据
    /* 若顶点无数据，则Data[]不必出现 */
}*MGraph; //以邻接矩阵存储的图的类型

/* 初始化一个有VertexNum个顶点但是没有边的图 */
MGraph CreateGraph(int VertexNum); 

void InsertEdge(MGraph Graph,Edge E);   //图的插入
MGraph BuildGraph();    //图的建立
void ShowGraph(MGraph Graph);   //显示图

int main()
{
    MGraph graph;
    int VertexNum = 8;

    graph=BuildGraph();

    ShowGraph(graph);

    system("pause");
    return 0;
}

/*
    初始化一个图：VertexNum * VertexNum 的矩阵
    * * ... * *
    . *     * .
    .         .
    . *     * .
    * * ... * *
*/
MGraph CreateGraph(int VertexNum)
{
    Vertex V,W;
    MGraph Graph;

    Graph=(MGraph)malloc(sizeof(struct GNode));
    Graph->Nv=VertexNum;
    Graph->Ne=0;
    /* 初始化邻接矩阵，从0-(Graph->Nv-1) */
    for(V=0;V<Graph->Nv;V++)
        for(W=0;W<Graph->Nv;W++)
            Graph->G[V][W]=INFINITY;

    return Graph;
}

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

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

    printf("please enter the Node:\n");
    scanf_s("%d",&Nv);  //顶点数
    Graph=CreateGraph(Nv);

    printf("please enter the Edge:\n");
    scanf_s("%d",&(Graph->Ne));
    if(Graph->Ne!=0){
        E=(Edge)malloc(sizeof(struct ENode)); /* 建立边节点 */
        for(i=0;i<Graph->Ne;i++){
            /* 起点、终点、权重 插入邻接矩阵 */
            printf("please enter V1 V2 Weight:\n");
            scanf_s("%d %d %d",&E->V1,&E->V2,&E->Weight);
            InsertEdge(Graph,E);
        }
    }

    /*
     读入顶点数据 
    for(V=0;V<Graph->Nv;V++)
        scanf_s("%c",&(Graph->Data[V]));
    */
    return Graph;
}

void ShowGraph(MGraph Graph)
{
    int i, j;
    printf("show the Graph:\n");
    for(i=0;i<Graph->Nv;i++){
        for(j=0;j<Graph->Nv;j++){
            printf("%d ", Graph->G[i][j]);
        }
        putchar('\n');
    }
    putchar('\n');
}

输入与输出示例：

please enter the Node:
10
please enter the Edge:
17
please enter V1 V2 Weight:
0 1 1
please enter V1 V2 Weight:
0 3 1
please enter V1 V2 Weight:
3 1 1
please enter V1 V2 Weight:
1 2 1
please enter V1 V2 Weight:
3 7 1
please enter V1 V2 Weight:
3 6 1
please enter V1 V2 Weight:
1 5 1
please enter V1 V2 Weight:
2 5 1
please enter V1 V2 Weight:
2 4 1
please enter V1 V2 Weight:
7 6 1
please enter V1 V2 Weight:
5 6 1
please enter V1 V2 Weight:
5 4 1
please enter V1 V2 Weight:
6 8 1
please enter V1 V2 Weight:
5 8 1
please enter V1 V2 Weight:
5 9 1
please enter V1 V2 Weight:
4 9 1
please enter V1 V2 Weight:
8 9 1
show the Graph:
0 1 0 1 0 0 0 0 0 0
1 0 1 1 0 1 0 0 0 0
0 1 0 0 1 1 0 0 0 0
1 1 0 0 0 0 1 1 0 0
0 0 1 0 0 1 0 0 0 1
0 1 1 0 1 0 1 0 1 1
0 0 0 1 0 1 0 1 1 0
0 0 0 1 0 0 1 0 0 0
0 0 0 0 0 1 1 0 0 1
0 0 0 0 1 1 0 0 1 0

请按任意键继续. . .