一、图的基本概念和术语
定义：图是顶点和边的集合
无向图：每条边都是无方向的
有向图：每条边都是有方向的
完全图：任意两个点都有一条边相连
图、网、邻接、关联
顶点的度：
简单路径与回路
联通图（无方向）、强连通图（有方向）
权与网
子图
连通分量（无方向）
强连通分量（有方向）
级小连通子图与生成树
图的类型定义
图的操作
二、图的存储结构
1、邻接矩阵表示法
图的表示方法
无向图的邻接矩阵表示法
（两个顶点之间有边，则相关的值则为1）
分析1：无向图的邻接矩阵是对称的，其斜线全部为0。
分析2：顶点i的度 = 第i行(列)中1的个数。
分析3：完全图的邻接矩阵中，对角线元素为0，其余为1。
有向图的邻接矩阵表示法
（以自身为起点，到其他的点，则记为1）
分析1：不再对称，由于具有方向性，但对角线依然为0。
分析2：顶点的出度 = 第i行元素之和
分析3：顶点的入度 = 第i列元素之和
分析4：顶点的度 = 第i行元素之和 + 第i列元素之和
网的邻接矩阵表示法
（边上带有权值的图表示方式）
邻接矩阵存储表示
方法：用两个数组分别存储顶点表和邻接矩阵
代码如下：
//采用邻接矩阵表示法创建无向网 #define MaxInt 32767 //表示极大值，既∞ #define MVNum100 //最大顶点数 typedef char VerTexType; //设顶点数据类型为字符型 typedef int ArcType; //假设边的权值类型为整形 typedef struct{ VerTexType vex[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum arcnum; //图的当前点数和边数 }AMGraph; //Adjacency Matrix Graph //在图中查找顶点 int LocateVex(AMGraph G, VertexType u){ //在图G中查找顶点u，存在则返回顶点表中的小标，否则返回-1 int i; for(i = 0; i < G.vexnum; i++) if( u == G.vexs[i] ) return i; return -1; } Status CreateUDN(AMGraph &G){ //采用邻接矩阵表示法，创建无向网G cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数 for( i = 0; i < G.vexnum; i++) //依次输入点的信息 cin >> G.vexs[i]; for(i = 0; i < G.vexnum; i++) //初始化邻接矩阵，边的权值均设置为极大值 for( j = 0; j < G.vexnum; j++) G.arcs[i][j] = MaxInt; for( k = 0; k < G.arcnum; k++){ //构建邻接矩阵 cin >> v1 >> v2 >> w; //输入一条边所依附的顶点及边的权值 i = LocateVex(G,v1); //确定v1，v2在G中的位置 j = LocateVex(G,v2); G.arcs[i][j] = w; //置权值 G.arcs[j][i] = G.arcs[i][j]; } return OK; }
ps：有向图，有向网，无向图，无向网
如果创建的为无向图，此时没有权值，所以只需要把权值更改为01；
如果创建的为有向网，此时是有方向的，所以只需要构建一条弧，其不是对称矩阵，也就是对称的元素不需要赋值。
权值与1，无穷大与0。
邻接矩阵存储表示的优缺点
优点：
缺点
2、邻接表表示法
表示方法，以无向图为例，如下所示：
无向图邻接表表示方式
表示方法：
（如果是一个网，则可以在边的表示结构中再增加一个内容–权值）
邻接矩阵是唯一的，但是邻接表是不唯一的，节点可以交换顺序。（哈夫曼树的构造也不算唯一的）
特点：
有向图临界表表示方式
（在有向图中，由于具有方向，因此不需要把同一条表保存两次）
表示方法：只记录以其为结尾的为弧
出度简单，就是节点的个数。
但是入度的计算比较的麻烦，需要遍历整个邻接表来寻找该结点。
此外，还可以有逆邻接表，也就是入度链接表，而通常的邻接表为出度临界表。
其区别与特点如下：（根据实际来做选择）
例子：根据邻接表（出度表），画出该网络
图的邻接表存储表示
边结点结构
代码如下：
#define MVNum 100 //最大顶点数 typedef struct ArcNode{ //边结点 int adjvex; //该边所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 OtherInfo info; //和边相关的信息 }ArcNode;
顶点结构表示
代码如下：
typedef struct VNode{ VerTexType data; //顶点信息 ArcNode *firstarc; //指向第一条衣服该顶点的边的指针 }VNode,AdjList[MVNum]; //AdjList表示邻接表类型 //AdjList v; 相当于：VNode v[MVNum];
图的结构定义
typedef struct{ AdjList vertices; //图，邻接表的数据 int vexnum,arcnum; //图当前顶点数和弧数 }
邻接表的操作举例说明：
创建无向网算法
算法思想
采用邻接表表示法创建无向网
代码如下：
Status CreateUDG(ALGaph &G){ //采用邻接表示法，创建无向图G cin >> G.vexnum >> G.arcnum; //输入总顶点数，总边数 for( i = 0; i < G.vexnum; i++){ //输入各点，构造表头结点表 cin >> G.vertices[i].data; //输入顶点值 G.vertices[i].firstarc = NULL; //初始化表头结点的指针域 } for( k = 0; k < G.arcnum; k++){ //输入各边，构造邻接表 cin >> v1 >> v2; //输入一条边依附的两个顶点 i = LocateVex(G,v1); //找到v1数据的下标 j = LocateVex(G,v2); //找到v2数据的下标 //只要这四语句，建立出度边（邻接表） p1 = new ArcNode; //生成一个新的边结点*p1 p1->adjvex = j; //邻接点序号为j p1->nextarc = G.vertices[i].firstarc; G.vertices[i].firstarc = p1; //将新节点*p1头插到vi的边表头部 //值要这四语句，建立入度边（逆邻接矩阵） p2 = new ArcNode; //生成一个新的边结点*p2 p2->adjvex = i; //邻接点序号为i p2->nextarc = G.vertices[j].firstarc; G.vertices[j].firstarc = p2; //将新节点*p2头插到vi的边表头部 } return OK; }
邻接表的特点
特点：
- 邻接矩阵与邻接表的联系：邻接表汇总每个链表对应于邻接矩阵中的一行，链表中结点个数等于一行中非零元素的个数。
- 邻接矩阵与邻接表的区别：
- 对于任一确定的无向图，邻接矩阵是唯一的（行列号与顶点编号一致），但邻接表是不唯一的（链接次序与顶点编号无关）。
- 邻接矩阵的空间复杂度为O(n2)，而邻接表的空间复制度为O(n+e)（顶点数加边数）。
总结：邻接矩阵多用于稠密图；而邻接表多用于稀疏图。
3、十字链表（简单介绍）
- 引子
由上诉的邻接表的特点可知，对于求有有向图的度比较麻烦，需要遍历整个的邻接表，这里提出了一种改进的方法：十字链表（将邻接表与逆邻接表结合在 一起）
- 顶点节点结构：
data：数据域
firstin：第一条入弧
firstout：第一条出弧
- 弧结点结构：
tailvex：弧尾位置
headvex：弧头位置
hlink：弧头相同的下一条弧
tlink：弧尾相同的下一条弧
- 十字链表例子：
总结：
以上，便可以顺着一个链表找到这个节点的所以出度和入读，也就知道了这个节点的度的大小。出度的多少，入度的多少都非常容易计算，不再需要遍历整个邻接表。
4、邻接多重表（简单介绍）
解决的问题
解决的思路：存储边的时候，只存储一条。
使用的例子
