PS：图在数据结构中有着非常大的分量，它比树有着更为复杂的形式结构，这里就不再说图的基本概念，直接就说图的存储结构，邻接矩阵和邻接表。图是有方向的，有方向的叫做弧，无方向的叫做边。存储图中各顶点本身数据，使用一维数组就足够了；存储顶点之间的关系时，要记录每个顶点和其它所有顶点之间的关系，所以需要使用二维数组。图在大多行业中的使用也是很多的，比如说游戏中两个人物的寻址，自动寻路，就是图与图直接经过计算然后移动。后序还会介绍Dijkstra（迪杰斯特拉)算法计算最短路径问题。

下面介绍邻接矩阵原理：

下面可以看到顶点之间有一定的联系，如果想要把他们存放在计算机中怎么存入呢，首先我们想到的是把顶点存在一维数组中，那么他们的关系存在在二维数组中，就好像是如下格式，A->B 权值是10，B->E 权值30。(下方1为有关系，0为没有关系，未加入权值)

思路

首先把要知道顶点和边数，然后单独把顶点存在一维数组中，根据边来确定两个顶点之间的联系，比如说第一条边，是A->B。归根结底也是通过数组来存储。当然这是邻接矩阵。

步骤

1. 定义结构体
2. 输入顶点和边数
3. 通过顶点和边数初始化数据（内部全是0或者是无穷）
4. 打印表
5. 遍历（深度和广度优先遍历）

1：结构体定义

typedef char VertexType;typedef int EdgeType;#define MAXVEX 100#define IUNFINITY 65535typedef struct {    VertexType vexs[MAXVEX];        /* 顶点表*/    EdgeType arc[MAXVEX][MAXVEX];   /* 邻接矩阵 */    int vnum, edgenum;               /*定点的个数和边的个数*/} MGraphy;

2：数据初始化

代码中有很多注释，有没有用到的，但是一种经验。 

//加入权值void createGraphyWeight(MGraphy *g) {    printf("输入总顶点(空格)边数\n");    scanf("%d %d", &g->vnum, &g->edgenum);    printf("输入 顶点表示:\n");    //顶点请输入;    for (int i = 0; i < g->vnum; i++) {        printf("请输入第%d个顶点", (i + 1));//        fflush(stdin);//不起作用，资料显示一些linux平台下一些库没有定义这个方法。//        flushall(); //清除多余的回车符。        //如果不加入getchar的话，在for循环中就会先执行一遍scanf，因为上面可能会有一些回车，导致执行一遍scanf。需要清除之前的回车。        getchar();        scanf("%c", &g->vexs[i]);    }    for (int i = 0; i < g->vnum; i++) {                               // 初始化数组元素 Infonity        for (int j = 0; j < g->vnum; j++) {//            g->arc[i][j] = IUNFINITY;//对于加权值的默认全部设置为最大值，            g->arc[i][j] = 0;//对于未加权值的默认全部设置为0        }    }    printf("输入边有关的两个顶点，\n");    for (int i = 0; i < g->edgenum; i++) {        char a, b;        int c ;        printf("输入第 %d 条边有关的两个顶点加权值（空格隔开）,没有权值输入0\n ", (i + 1));        getchar();//        setbuf(stdin,NULL);        scanf("%c %c %d", &a, &b,&c);        int ii = localGV(g, a);        int jj = localGV(g, b);        if(c == 0){            c=1;        }//        printf("c的值是%d",c);        g->arc[ii][jj] = c;        g->arc[jj][ii] = c;    // 无向图    }    printfL(g);}

 3：打印表

void printfL(MGraphy *g) {    //输出图的信息    printf("表为 :\n");    int i = 0;    //先打印行标题；顶点标题    for (i = 0; i < g->vnum + 1; i++) {        if (i > 0) {            printf("%c\t", g->vexs[i - 1]);        } else {            printf("\\\t");        }    }    printf("\n");    for (i = 0; i < g->vnum; i++) {        printf("%c\t", g->vexs[i]);        for (int j = 0; j < g->vnum; j++) {            printf("%d\t", g->arc[i][j]);        }        printf("\n");    }}

 4：深度优先遍历

这里的深度优先遍历只给出代码，原理后序会给出。

//深度优先搜索void DFSTraverse(MGraphy *G){//    int v;    //将用做标记的visit数组初始化为false    for( v = 0; v < G->vnum; ++v){        visited[v] = false;    }    //对于每个标记为false的顶点调用深度优先搜索函数    for( v = 0; v < G->vnum; v++){        //如果该顶点的标记位为false，则调用深度优先搜索函数        if(!visited[v]){            DFS(G, v);        }    }}int FirstAdjVex(MGraphy *g,int v){    //查找与数组下标为v的顶点之间有边的顶点，返回它在数组中的下标    for(int i = 0; i
     
      vnum; i++){        if( g->arc[v][i]){            return i;        }    }    return -1;}int NextAdjVex(MGraphy *G,int v,int w){    //从前一个访问位置w的下一个位置开始，查找之间有边的顶点    for(int i = w+1; i
      
       vnum; i++){        //最关键的一个判断，调试了很久，让其等于'1'或者 !=0 ,否则该字符不知道后面还是否有值相连接。        if(G->arc[v][i] != 0){            return i;        }    }    return -1;}void DFS(MGraphy *g,int v){    visited[v]= true;    printf("%c",g->vexs[v]);//输入data值    //从该顶点的第一个边开始，一直到最后一个边，对处于边另一端的顶点调用DFS函数    int w;    for( w= FirstAdjVex(g,v); w>=0; w = NextAdjVex(g,v,w)){        //如果该顶点的标记位false，证明未被访问，调用深度优先搜索函数        if(!visited[w]){            DFS(g,w);        }    }}
      
     

完