认识图

• 图的定义：由顶点的有穷非空集合和顶点之间的边的集合组成。通常表示为G[V,E]，其中G表示一个图，V是图G中的顶点集合，E是图G中边的集合
• 各种图：

1. 无向图：图中顶点与顶点连接没有方向；无向边：图中边没有方向

   
   

2. 有向图：图中顶点与顶点之间有方向；有向边：图中边具有方向

   
   

3. 完全图：顶点与顶点之间完全连接

   
   

4. 网：当图的边加上权重后就是网。

   
   

图的存储

邻接矩阵存储

• 无向图的邻接矩阵
• 有向图的邻接矩阵
  

  
  

• 网的临界矩阵

  
  

• 代码实现：

  #include <stdio.h>
  #include <stdlib.h>
  #include <math.h>
  #include <time.h>
  
  #define OK 1
  #define ERROR 0
  #define TRUE 1
  #define FALSE 0
  #define MAXVEX 100 /* 最大顶点数，应由用户定义 */
  #define INFINITYC 0
  
  typedef int Status;    /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
  typedef char VertexType; /* 顶点类型应由用户定义  */
  typedef int EdgeType; /* 边上的权值类型应由用户定义 */
  typedef struct
  {
      VertexType vexs[MAXVEX]; /* 顶点表 */
      EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
      int numNodes, numEdges; /* 图中当前的顶点数和边数  */
  }MGraph;
  
  
  
  void CreatMGraph(MGraph *Map){
      VertexType top[] = {"A","B","C","D"};
      Map->numNodes = 4;
      Map->numEdges = 5;
      for (int i = 0; i<Map->numNodes; i++) {
          Map->vexs[i] = top[i];
      }
      for (int i = 0; i<Map->numNodes; i++) {
          for (int j = 0; j<Map->numNodes; j++) {
              //表示边没有连接
              Map->arc[i][j] = INFINITYC;
          }
      }
      int i,j,k,w;
      //01,02,03,12,23
      for(k = 0; k < Map->numEdges;k++){
          printf("输入边(vi,vj)上的下标i,下标j,权w\n");
          scanf("%d,%d,%d",&i,&j,&w);
          Map->arc[i][j] = w;
          //如果无向图,矩阵对称;
          Map->arc[j][i] = Map->arc[i][j];
      }
      printf("邻接矩阵是：\n");
      for (i = 0; i<Map->numNodes; i++) {
          printf("\n");
          for (j = 0; j<Map->numNodes; j++) {
              printf("%3d",Map->arc[i][j]);
          }
      }
      printf("\n");
  }
  
  int main(int argc, const char * argv[]) {
      // insert code here...
      printf("Hello, World!\n");
      MGraph map;
      CreatMGraph(&map);
      return 0;
  }
  
  复制代码

邻接表

• 无向图邻接表

  
  

• 有向图邻接表

  
  

• 邻接表的数据结构设计

  
  

• 邻接表的代码实现思路

  
  

• 邻接表的代码实现

  #include <stdio.h>
  #include "stdlib.h"
  #include "math.h"
  #include "time.h"
  
  #define M 100
  #define true 1
  #define false 0
  
  typedef char Element;
  typedef int BOOL;
  //邻接表的节点
  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;
  #pragma mark - 邻接表的存储
  void SaveGraph(GraphLink *Grap){
      int i,j,k;
      EdgeNode *p;
      printf("输入顶点数目,边数和有向？：\n");
      scanf("%d %d %d", &(*Grap)->node_num, &(*Grap)->arc_num, &(*Grap)->is_directed);
      for (i = 0; i<(*Grap)->node_num; i++) {
          getchar();
          scanf("%c",&(*Grap)->adjlist[i].data);
          (*Grap)->adjlist[i].firstedge = NULL;
      }
      printf("输入边信息\n");
      for (k = 0; k<(*Grap)->arc_num; k++) {
          getchar();
          scanf("%d %d",&i,&j);
          //创建结点
          p = (EdgeNode *)malloc(sizeof(EdgeNode));
          //设置弧头下标
          p->adj_vex_index = j;
          //使用头插法
          p->next = (*Grap)->adjlist[i].firstedge;
          (*Grap)->adjlist[i].firstedge = p;
          if (!(*Grap)->is_directed) {//无向图时
              //t无向图是对称的，所以代码给上面一致,唯一的区别是坐标变为j，j变为i
              //创建结点
              p = (EdgeNode *)malloc(sizeof(EdgeNode));
              //设置弧头下标
              p->adj_vex_index = i;
              //使用头插法
              p->next = (*Grap)->adjlist[j].firstedge;
              (*Grap)->adjlist[j].firstedge = p;
          }
      }
  }
  #pragma mark - 输出邻接表数据
  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");
      }
  }
  
  int main(int argc, const char * argv[]) {
      // insert code here...
      printf("Hello, World!\n");
      GraphLink Grap = (GraphLink)malloc(sizeof(Graph));
      SaveGraph(&Grap);
      putGraph(Grap);
      return 0;
  }
  
  
  复制代码