图

  顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G=(V,E),其中G表示一个图，V是图G中的顶点的非空集合，E是图G的边的集合。

相关定义

1. 边没有方向的图称为无向图，边称为无向边；
2. 有n(n-1)/2条边的无向图称无向完全图；
3. 边有对应的顶点，称为有向边，图称为有向图；
4. 图中各边都有方向的图称为有向完全图，有向完全图有n(n-1)条边；
5. 第一个顶点到最后一个顶点是闭合有回路的，称之为环。
6. 如果图中任意两点都是连通的，那么图被称作连通图。

邻接矩阵

  用一个一维数组存放图中所有顶点数据V；用一个二维数组存放顶点间关系边的数据，这个二维数组称为邻接矩阵。图G有n个顶点 则邻接矩阵是一个的矩阵。
  邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵。

代码实现

• 结构

  typedef char VertexType;//顶点类型
  typedef int EdgeType;//边上的权值类型
  typedef struct  {
         VertexType vexs[MaxVertexNum];//顶点表
         EdgeType edges[MaxVertexNum][MaxVertexNum];//邻接矩阵
         int VCount;//顶点个数
        int ECount;//边个数
  }Graph;
  

• 创建

   void CreateMGraph(Graph *G)
  {//建立邻接矩阵表示
   int i,j,k,w;
   scanf("%d%d",&G->VCount,&G->ECount); //输入顶点数和边数
   for(i = 0;i < G->VCount;i++) //读入顶点信息，建立顶点表
   {
       scanf("%c",&G->vexs[i]); //输入顶点数和边数
   }
   for(i = 0;i < G->VCount;i++)
   {
       for(j = 0;j <G->VCount;j++)
    {
           G->edges[i][j] = INTMAX; //邻接矩阵初始化
       }
   }
   for(k = 0;k < G->ECount;k++)
   {//读入e条边，建立邻接矩阵
       scanf("%d%d%d",&i,&j,&w); //输入边(v i ,v j )上的权w
       G->edges[i][j]=w;
       //如果是无向图，矩阵对称
       G->edges[j][i]=w;
   }
  }//CreateMGraph
  

邻接表

  邻接表，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
  对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点Vi的所有邻接顶点。

• 结构

    //邻接表的节点
  typedef struct Node{
    int adj_vex_index;  //弧头的下标，也就是被指向的下标
    Element data;       //权重值
    struct Node * next; //边指针
  }EdgeNode;
  //顶点节点表
  typedef struct vNode{
    Element data;          //顶点的权值
    EdgeNode * firstedge;  //顶点下一个是谁？
  }VertexNode, Adjlist[M];
    //总图的一些信息
  typedef struct Graph{
    Adjlist adjlist;       //顶点表
    int arc_num;           //边的个数
    int node_num;          //节点个数
    BOOL is_directed;      //是不是有向图
  }Graph, *GraphLink;
  

• 创建

     void creatGraph(GraphLink *g){
   int i,j,k;
   EdgeNode *p;
   
   //1. 顶点,边,是否有向
   printf("输入顶点数目,边数和有向？：\n");
   scanf("%d %d %d", &(*g)->node_num, &(*g)->arc_num, &(*g)->is_directed);
   //2.顶点表
    printf("输入顶点信息：\n");
   for (i = 0; i < (*g)->node_num; i++) {
       getchar();
       scanf("%c", &(*g)->adjlist[i].data);
       (*g)->adjlist[i].firstedge = NULL;
   }
   
   //3.
   printf("输入边信息：\n");
   for (k = 0; k < (*g)->arc_num; k++){
       getchar();
       scanf("%d %d", &i, &j);
       
       //①新建一个节点
       p = (EdgeNode *)malloc(sizeof(EdgeNode));
       //②弧头的下标
       p->adj_vex_index = j;
       //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
       p->next = (*g)->adjlist[i].firstedge;
       //④将顶点数组[i].firstedge 设置为p
       (*g)->adjlist[i].firstedge = p;
       
       //j->i
       if(!(*g)->is_directed)
       {
           // j -----> i
           //①新建一个节点
           p = (EdgeNode *)malloc(sizeof(EdgeNode));
           //②弧头的下标i
           p->adj_vex_index = i;
           //③头插法插进去，插的时候要找到弧尾，那就是顶点数组的下标i
           p->next = (*g)->adjlist[j].firstedge;
           //④将顶点数组[i].firstedge 设置为p
           (*g)->adjlist[j].firstedge = p;
       }
   }
  }
  void putGraph(GraphLink g){
   int i;
   printf("邻接表中存储信息:\n");
   //遍历一遍顶点坐标，每个再进去走一次
   for (i = 0; i < g->node_num; i++) {
       EdgeNode * p = g->adjlist[i].firstedge;
       while (p) {
           printf("%c->%c ", g->adjlist[i].data, g->adjlist[p->adj_vex_index].data);
           p = p->next;
       }
       printf("\n");
   }
  }