图

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

邻接矩阵

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

	v0	v1	v2	v3
v0
v1
v2
v3

代码实现

结构

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");
 }
}

图的存储方式

图的存储方式

图

相关定义

邻接矩阵

代码实现

邻接表