图形结构，多对多的关系
G = (V,E) V:顶点Vertex，有穷非空集合
E: 边Edge，非空集合
无向完全图：若有n个顶点，则有n(n-1)/2条边
有向完全图：若有n个顶点，则有n(n-1)条边
D（v）Degree在有向图中，顶点的度又分为入度和出度并且顶点的度等于入度+出度，入度ID(v)Input Degree,出度OD(v)Output Degree非简单回路：又回到终点，并且路径无重叠。
1建立一个顶点表：A = (V,E),Vexs[n]
2.建立邻接矩阵：二维数组A.arcs[n][n]
如果属于E的子集，或者（i,j）属于E的子集则添加1
否则添加0
顶点和它自身不存在邻接关系
邻接矩阵非对称
顶点的度数 = 所在行元素之和 + 所在列元素之和
邻接矩阵的元素为两个顶点之间的权重，如果两个顶点之间没有弧则记该元素为无穷大
#define MVN 100 // Matrix Vertex Number
#define Maxlnt 32767 // 无穷大
typedef char VerTexType; // Vertex type
typedef int ArcType;//Arc type
typedef struct
{
VerTexType vex[MVN];// Vertext array
ArcType arcs[MVN][MVN];// Adjacency Matrix Graph
int Vexnum,Arcnum;// Current vertex nums & arc nums
}AMGraph;
输入总顶点数和总变数
以此输入点的信息存入顶点表中
初始化邻接矩阵，使每个权值初始化为极大值
构造邻接矩阵
Status CreateUDN(AMGraph &G)// Create Un Direction Net
{
cin >> G.vexnum>>G.arcnum;//输入总的顶点数，创建无向有权图（也成为网）网
for(int i = 0; i < G.vexnum;i++)
cin>>G.vexs[i];// 以此输入顶点的值
for(int i = 0; i< G.vexnum; i++)
for(int j = 0; j < G.vexnum; j++)
G.arcs[i][j] = MaxInt;// 把邻接矩阵元素全部设为极大值
for(int k = 0; k < G.arcnum; k++)
{
cin>>v1>>v2>>w;// 输入确定边的两个点和边的权值
i = LocateVex(G,v1);//在顶点表中查找顶点的下标
j = LocateVex(G,v2);
G.arcs[i][j] = w;// 边确定的权值为w
G.arcs[j][i] = G.arcs[i][j];//无向有权图矩阵特性：沿对角线对称
}
return OK;
// 悟：邻接矩阵中的元素若不为极大值，则标志v1 和v2 是连通的，并且元素的值代表着边的权值。
// 悟：学好邻接矩阵的关键在于心中要有图，要有表。
}
int LocateVex(AMGraph G, VertexType u)
{
int i;
for(i = 0;i < G.vexnum;i++)
{
if(u == G.vexs[i])// 如果该顶点和顶点表中的值相匹配的话。
return i;// 返回顶点表中该顶点的下标。
}
}
十字链表来存储，无向图我们用邻接多重表来存储。struct {
VertexType data;
ArcBox *firstin,*firstout;//分别指向该顶点第一条入弧和出弧
}
顶点构造：Data, firstedge,边节点:mark, ivex, ilink, jvex, jlink, infomark 显示该边是否被搜索过，ivex搭配jvex指示该边所依附的两个顶点在数组中的位置，ilink 搭配ivex指示ivex的其他连通的情况，jlink 搭配 jvex指示 jvex的其他连通情况。如果是网的话，info可以用来存储权值等信息。
基本运算。visited[n]用来标记每个被访问过的顶点。初始状态为0,被访问过则修改为1.一条道走到黑沿着某一分支搜索到底，然后折返，看看折返后的顶点有没有未被访问过的分支，如果有搜索到底，然后折返重复以上动作，直到所有顶点的所有分支都被访问过为止。
void DFS(AMGraph G, int v)
{
printf("%d",v);
visited[v] = true;//已被访问过，打上标记
for(int w = 0; w < G.Vexnum; w++)// 访问v的邻接点w
if((G.arcs[v][w]!=0)&&(!visited[w]))//如果是邻接点，且未被访问过，则访问
DFS(G,w);// 递归调用DFS继续访问
}
n^2,邻接表 n + e
这些节点被访问的先后次序依次访问与他们相邻接的所有未被访问的顶点。重复此过程，直到所有顶点都被访问完为止。使用邻接表来存储顶点
需要一个visited数组，用以记录该节点是否被访问过
需要一个循环队列，类似于树的层次遍历，从根节点到孩子节点依次入队
void BFS(Graph G, int v)//Breadth First Search
{
printf("%d",v);
visited[v] = true;
InitQueue(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])
{
printf("%d",w);// 输出下一个节点
visited[w] = true;//标记为已访问
EnQueue(Q,w);// v的邻接点w入队
}// if
}//while
}//BFS
生成树：所有顶点均由边连接在一起，但是不存在回路的图
一个图可以有许多生成树
生成树的顶点个数与图的顶点个数相同
生成树是图的极小连通子图，去掉一个边则不连通
在生成树中再加一条边必然形成回路
若图的节点个数是n则生成树的边数是n-1生成树要包含图中所有顶点
生成树中任意两个顶点间的路径是唯一的
具有n个节点，n-1条边的树不一定是生成树（主要考虑：连通性和回路）
最小生成树，也叫最小代价生成树。**最小生成树性质：**设G=(V，E)是一个连通网络，U是顶点集V的一个真子集。若(u，v)是G中一条“一个端点在U中(例如：u∈U)，另一个端点不在U中的边(例如：v∈V-U)，且(u，v)具有最小权值，则一定存在G的一棵最小生成树包括此边(u，v)。附带书面笔记。
迪克牛仔斯特拉：有效的程序员不应该浪费时间用于调试程序，而应该在一开始就把故障引入。
有向无环图：Directed Acycline Graphy DAG
解决拓扑排序问题在AOV网中没有回路的前提下，我们把图中的全部顶点（活动）排成一个有序序列，使得这个序列中的元素仍然能保持AOV网中前驱与后继的关系，那么这个有序序列也叫做拓扑有序序列。相应的算法，叫做拓扑排序。
AOE网： 用一个有向图表示一个工程的各个子工程及其相互制约关系，以弧表示活动本身，以顶点表示活动的开始或结束，我们称这种图为边表示活动的网（Activity of Edge network）解决关键路径问题
ve(vj) early, 事件vj的最早发生时间。
vl(vj) late，事件vj最晚发生时间。
e(i) 表示活动i的最早开始时间。
l(i) 表示活动i的最晚开始时间。
时间余量：最晚开始时间减去最早开始时间。
关键活动：没有时间余量， l(i) - e(i) = 0;
只需找出该活动所在两个顶点（事件）中，一事件的最早发生时间，一事件的最晚发生时间，求差值即可。
1.计算Ve(i),Vl(j)即每一个顶点的最早和最晚发生时间
2.求e(i),l(i)
3.计算l(i) - e(i)
1.若网中有几条关键路径存在，则需加快同时在几条关键路径上的关键活动
2.如果一个活动处于所有的关键路径上，那么提高这个活动的速度就能缩短整个工程完成的时间。
3 处于所有关键路径上的活动完成时间也不能缩短太多，否则会使原来的关键路径变成不是关键路径。这时，就需要重新寻找关键路径，这可能导致时间资源的浪费。