图G是由两个集合V和E组成，记为G=(V,E) V(G)和E(G)表示图的顶点集和边集。其中E(G)可以为空， 表示这个图只有定点没有边
有向图和无向图
其中第一个图就是无向图：G1=（{V1,V2,V3,V4,V5},{(v1,v2),(v1,v3),(v2,v5)(v3,v5),(V4,V5)}） 第二幅图就是有向图：G2=({V1,V2,V3,V4,V5},{<V1,V2>,<V1,V3>,<V3,V4>,<V4,V5>,<V5,V3>}) 要注意的是，在有向图中，边集中的边需要用尖括号表示，在无向图中，边集需要用小括号表示。
用n表示定点数，用e表示边的数目 （1）子图：在一个图中，一个图的顶点和边是另外一个图的顶点和边的子集，那么这个图就是原来的图的子图（类比数学中的子集的概念） （2）无向完全图和有向完全图：对于无向图，如果边为n(n+1)/2，那么就是无向完全图 在有向图中，如果边n(n+1)——有向完全图 （3）稀疏图和稠密图：边很多的就是稠密图，相应的，少的就是稀疏图 （4）权和网：权这个跟数学中的相类似，网就是带权的图 （5）邻接点：两个点有同一个边。如果一条边e连接了两个顶点v和v1，那么我们可以称边e依附于顶点v和v1，或者说，边e和v和v1相关联 （6）度，入度和出度：很好理解不解释 但是要知道的是，入度和出度这种说法是对于有向图而言的，无向图中没有入度和出度这种说法。在有向图中，节点的度=入度+出度 （7）路径和路径长度 （8）回路或环 （9）简单路径，简单回路或简单环：顶点不重复出现的路径称为简单路径。 除了第一个和最后一个顶点以外，其他顶点都不重复出现的就是简单回路或简单环 （10）连通，连通图，连通分量：连通分量，就是无向图中的极大连通子图 极大连通子图，如果再增加一个顶点就是不连通的了 在上面中，我们会发现，图a有三个子图我们拆分成左边这样，b，c和d都是a的极大连通子图
(11)强连通图和强连通分量：（注意，强连通图和强连通分量都是相对于有向图而言的） 在有向图中，任意两个顶点之间都有路径——强连通图 在强连通图G中的极大强连通子图——强连通分量 （12）连通图的生成树：一个极小连通子图，包含图中的所有顶点，但是只有n-1条边（首先，一定是连通的） 注意：一棵有n个顶点的生成树有且仅有n-1条边 如果一个图有n个顶点或者小于n-1条边，那就是非连通图 如果他多于n-1条边，那一定有环 但是，有n-1条边的图不一定是生成树 （13）有向树和生成森林：有一个顶点入度是0，其余顶点的入度全部是1的有向图就是有向树，由若干颗有向树构成的不相交的就是生成森林。 （14）极小连通子图：如果再删除一条边就是不连通的了 （15）生成树：包含了无向图G的所有顶点的极小连通子图
1.邻接矩阵表示法（数组表示法） 表示顶点之间相邻关系的矩阵。 如果两个顶点之间有边，就用1表示，如果没有就用0表示。 邻接矩阵一定是方阵 如果是一个网的话（边之间有权），那么如果两个顶点之间有边，就用边的权值表示，如果没有，就用无穷表示
建立一个顶点表（记录各个顶点的信息）和邻接矩阵（表示各个顶点之间的关系） 无向图的邻接矩阵表示： 分析：（1）无向图的邻接矩阵是对称的 （2）顶点i的度=第i行（列）中1的个数 （3）特别的，完全图中，对角线元素都是0，其余的都是1
有向图的邻接矩阵表示 注意：第i行表示以当前节点为弧尾的出度边 第i列表示以当前为节点的弧头的入度边
分析：（1）有向图的邻接矩阵可能不是对称的 （2）顶点的出度=第i行元素之和 顶点的入度=第i列的元素之和 顶点的度=第i行元素之和和第i列的元素之和
网的邻接矩阵表示
邻接矩阵
#define MaxInt 32767 //表示极大值，即无穷 #define MVNum 100 //最大顶点数 typedef char VerTexType //设顶点的数据类型为字符型 typedef int ArcType //假设边的权值类型为int型 typedef struct { VerTexType vexs[MVNum]; //顶点表 ArcType arcs[MVNum][MVNum]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和边数 }AMGraph;采用邻接矩阵法创建无向网 步骤： （1）输入总顶点数和总边数 （2）依次输入顶点信息（初始化顶点表） （3）将邻接矩阵全部元素初始化为无穷 （4）初始化邻接矩阵
Status creatUDN(AMGraph &G) { cin>>G.vexnum>>G.arcnum; //输入总顶点数和总边数 for(int i=0;i<vexnum;i++) { cin>>G.vexs[i]; //依次输入顶点信息 } for(int i=0;i<vexnum;i++) //初始化邻接矩阵 for(int j=0;j<arcnum;j++) G.arcs[i][j]=MaxInt; //边的权值全为极大值 for(int i=0;i<arcnum;i++) //构造邻接矩阵 { cin>>v1>>v2>>w; //输入一条边所依附的顶点及边的权值 int a=LocateVex(G,v1); int b=LocateVex(G,v2); //确定v1和v2在G中的位置 G.arcs[a][b]=w; //边<v1,v2>的权值置为w G.arcs[b][a]=G.arcs[a][b]; //（无向）对称邻接矩阵 } return OK； }在图中查找顶点
int LocateCVex(AMGraph G,VerTexType u) { //在图G中查找顶点u，存在则返回顶点所在的下标，否则返回-1 int i; for(i=0;i<vexnum;i++) { if(G.vexs[i]==u) return i; } return -1; }邻接矩阵表示法的优点： （1）便于判断两个顶点之间是否有边，根据A[i][j]=0或1来判断 （2）便于计算节点的度 对于无向图，邻接矩阵的第i行元素之和就是顶点i的度 对于有向图，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度 邻接矩阵表示法缺点： （1）不便于增肌和删除节点 （2）不便于统计边的数目，要扫描整个矩阵才可以 （3）空间复杂度高
所以，下面就使用了邻接表法——适合稀疏图
在邻接表中，对图中的每一个顶点建立一个单链表。邻接表中的单链表的第一个节点存放有关顶点的信息，把这一节点看成链表的表头，其余节点存放有关边的信息，这样邻接表便由两部分组成：表头节点和边表
（1）表头节点表：由所有的表头节点以顺序存储的方式存储，以便可以访问任意顶点的边链表。 表头节点包括数据域和链域 数据域存储和边有关的信息，如权 链域指示与顶点邻接的下一条边的节点 若每条边还有权值，那么可以这样表示：
注意，在无向图中，顶点i的度为第i个链表中的节点数 但是，在有向图中，第i个链表中的节点数仅仅是代表了顶点i的出度，如果要求顶点i的度，必须要遍历整个邻接表。 有时候为了方便求入度，会建立有向图的逆邻接表
无向图的邻接表： 特点： （1）邻接表不唯一 （2）如果有n个节点，e条边，那么在邻接表中有n个头结点和2e个表节点，适合存储稀疏图 （3）无向图中求节点i的度就是其邻接表中单链表中表结点的个数
有向图的邻接表 特点： （1）节点Vi的出度=第i个单链表中节点的个数 （2）要找到节点的入度需要遍历整个邻接表，找到节点i在邻接表中出现的次数 如果需要方便找到入度有多少个，可以做一个逆邻接表
采用邻接表表示法创建无向图 （1）输入总顶点数和总边数 （2）依次输入点的信息存入顶点表中，使每个表头节点的指针域初始化为NULL （3）创建邻接表。依次输入每条边依附的两个顶点，确定这个顶点的序号i和j之后，将此边节点分别插入vi和vj对应的两个边链表头部
顶点的结构：
typedef struct VNode { VerTexType data; //顶点信息 ArcNode *firstarc; //指向第一条依附于该节点的边的指针 }VNode,AdjList[MVNum]; //AdjList表示邻接表类型 //说明：AdjList v 相当于 VNode v[MVNum]边的节点结构：
#define MVNum 100 //最大顶点数 typedef struct ArcNode //边节点 { int adjvex; //该边所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条边的指针 OtherInfo info; //和边相关的信息 }ArcNode;图的结构定义：
typedef struct { AdjList vertices; //存放了顶点集结构，因为他里面还有指向边的指针，那么就相当于整个图都找到了 int vexnum,arcnum; //图的当前节点数和弧数 }ALGraph;邻接表操作 采用邻接表表示法创建无向网 步骤： （1）输入总共有多少个顶点，多少条边 （2）建立顶点表 依次输入点的信息存入顶点表 使每个头结点的指针域都指向NULL （3）创建邻接表 依次输入每条边依附的两个顶点 确定两个顶点的序号i和j，建立边节点 将此边节点分别插入到Vi和Vj对应的两个边链表的头部
Status CreatUDG(ALGraph &G) //采用邻接表表示法创建无向图G { cin>>G.vexnum>>G.arcnum; //输入总顶点数和总边数 for(int i=0;i<G.vexnum;i++) //输入各节点，构造表头节点表 { cin>>G.vertices[i].data; //输入顶点值 G.vertices[i].firstarc=NULL; //初始化表头结点的指针域 } for(int j=0;j<arcnum;j++) //输入各边，构造邻接表 { cin>>v1>>v2; //输入每一条边依附的两个节点 int a=LocateVex(G,v1); int b=LocateVex(G,v2); //出度边 p1=new ArcNode; //生成一个新的边节点p p1->adjvex=j; //邻接点序号为j //头插法 p1->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p1; //将新节点*p插入到头结点vi的边表头部 //由于我们的图是无向网 p2=new ArcNode; p2->adjvex=i; p2->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p2; } }查询位置
int LocateVex(ALGraph G,VerTexType data) { for(int i=0;i<G.vexnum;i++) { if(G.vertices[i].data==data) return i; } return -1; }邻接表表示法的优点 （1）便于增加和删除顶点 （2）便于统计边的数目 （3）空间效率高 邻接表表示法的缺点 （1）不利于判断顶点之间是否有边 （2）不便于计算有向图中各个顶点的度
下面的十字链表，便于求出顶点的入度和出度
在顶点节点中，firstin—第一条入度边，firstout—第一条出度边 在弧节点中，tailvex弧尾位置，headvex弧头位置，hlink—弧头相同的下一条弧，tlink—弧尾相同的下一条弧
上面的边链表有3个空格，其中第2个空格表示与前面那个节点相关联的指针域，后面那个空格表示与第2个节点相关的指针域
由于图中可能存在回路，那么在遍历的时候，怎么避免多次访问呢？ 解决方案：我们可以设置一个辅助数组visited[]，用来标记每个被访问的顶点。 初始化状态为visited[]为0 顶点i被访问，就修改其中的visited[i]为1，防止多次访问
深度优先搜索（DFS） 广度优先搜索（BFS） 就像点亮灯的步骤一样，先一路到底点亮灯，如果发现没有路可以走了，再返回到原先的节点，走另外一条路点亮，不断重复这样的过程，直到最后返回到初始的点。
邻接矩阵表示的无向图的深度优先遍历：
void DFS(AMGraph G,int y) //图G为邻接矩阵类型 { cout<<v;visited[v]=true; //访问第v个顶点 for(int w=0;w<G.vexnum;w++) //依次检查邻接矩阵所在的行 { if((G.arc[v][w]!=0)&&(!visited[w])) { DFS(G,w); } //w是v的邻接点，如果w未访问，则递归调用DFS } }步骤： 从图的某一节点出发，点亮他的邻接节点，然后再进入其中的一个邻接节点，点亮邻接节点的邻接节点，不断的循环，直到点亮所有的节点。
按广度优先非递归遍历连通图G
void BFS(AMGraph G,int v) //按广度优先非递归遍历连通图G { cout<<v; visited[v]=true; //访问第v个顶点 InitQueue(Q); //辅助队列Q初始化，置空 EnQueue(Q,v); //v进队 while(!QueueEmpty(Q)) //队列非空 { DeQueue(Q,u); //队头元素出队并置为u for(w=FirstAdjVex(G,u);w>=0;w=NextAdjVex(G,u,w)) if(!(visited[w])) //w为u尚未访问的邻接节点 { cout<<w; visited[w]=true; EnQueue(G,w); //w进队 } } }