每周学习日志（三）

学习图的基本概念及基本术语和邻接矩阵

Graph=(V,R)

V是顶点的非空有限集，R是边的有限集，可为空集。

---

图的分类

有向图、无向图、简单图、完全图、稀疏图、稠密图、赋权图。

有向图：有序对<>。 无向图：无序对()。

简单图：不考虑顶点到其自身的边，既（u，v）是图G的边，则u不等于v，且如果图中没有相同边，则称图为简单图。

完全图：完全图具有最多的边数，任一对顶点都有边相连，有向图n(n-1)，无向图n(n-1)/2.

稀疏图：又很少条边的图（e<nlogn）。

稠密图：相反于稀疏图的图。

赋权图：·无向图的每条边都有带一个权，则称相应的图为赋权无向图。 ·有向图的每条边都带一个权，则称相应的图为赋权有向图。

邻接矩阵c语言描述

#define max_vertex_num 20
#define infinity 32768
typedef emum{DG,DN,UDG,UDN}Graphkind;
typedef char vertexdata;
typedef struct ArCNOde{
      AdjType adj; //1、0相邻？（无权图）|权值类型（赋权图）
      OtherIrfo info;
}ArCNode;

typedef struct{
      vertexdata vexs[max_vertex_num];  //顶点向量
      ArCNode arcs[max_vertex_num][max_vertex_num];  //矩阵
      int vexnum,arcnum; //顶点数和弧数
      Graphkind kind; //种类
}Adjmatrix;

一条边可看作两条相反方向的弧，如——插入一条（i，j）的操作：

G->arcs[i][j].adj=1;
G->arcs[j][i].adj=1;