图的基本概念

图的定义

图是一种非线性结构，其中的元素是多对多的关系。

图是由非空的顶点的集合和描述顶点关系即边的集合组成。

图的特征

图的基本术语

  • 有向图：边是有方向的图
  • 无向图：边是无方向的图

图的存储结构

图的连接矩阵

  1. #define MAXVEX  100
  3. typedef char VertexType[3];        /*定义VertexType为char数组类型*/
  5. typedef struct vertex
  6. {    
  7.     int adjvex;                 /*顶点编号*/
  8.     VertexType data;             /*顶点的信息*/
  9. } VType;                        /*顶点类型*/
  11. typedef struct graph
  12. {
  13.     int n,e;                    /*n为实际顶点数,e为实际边数*/
  14.     VType vexs[MAXVEX];            /*顶点集合*/
  15.     int edges[MAXVEX][MAXVEX];    /*边的集合*/
  16. } AdjMatix;                        /*图的邻接矩阵类型*/

图的连接表

  1. #define MAXVEX 100
  3. typedef char VertexType[3];
  5. typedef struct edgenode
  6. {    
  7.     int adjvex;                  /*邻接点序号*/
  8.     int value;                  /*边的权值*/
  9.     struct edgenode *next;        /*下一条边的顶点*/
  10. } ArcNode;                        /*每个顶点建立的单链表中结点的类型*/
  12. typedef struct vexnode
  13. {
  14.     VertexType data;               /*结点信息*/
  15.     ArcNode *firstarc;             /*指向第一条边结点*/
  16. } VHeadNode;                    /*单链表的头结点类型*/
  18. typedef struct 
  19. {
  20.     int n,e;                    /*n为实际顶点数,e为实际边数*/
  21.     VHeadNode adjlist[MAXVEX];    /*单链表头结点数组*/
  22. } AdjList;                         /*图的邻接表类型*/

图的遍历

广度优先搜索

深度优先搜索