1. 图的定义与性质
（1）从任意顶点是否连通的角度，图分为：连通图和非连通图；从顶点之间的边的方向性的角度，又分为：有向图和无向图。
（2）一个连通图的连通分量是其本身，一个非连通图的连通分量是其所有极大连通子图。
2.图的存储结构
（1）*邻接矩阵：用一维数组来存储顶点信息，用二维数组存储邻接矩阵，较适用于稠密图 和 已知点和边的图；
（2）*邻接表：用一个单链表存储图中每个顶点V，再分别用链表存储与 V相邻接的所有顶点；适用于稀疏图，也方便删改图中顶点，但有时候定义比较麻烦复杂（个人感觉）。
（3） 十字链表：针对有向图，看成是有向图邻接表和逆邻接表的结合，十字链表也可以看成是邻接矩阵的链表存储结构；
（4） 邻接多重表：无向图的另一种链式存储结构，可用于边的删改。
3.图的遍历：
（1）DFS深度优先搜索：类似树的先序遍历
void DFS(Graph &G, int j)
{
visited[j] = 1;
cout<<j<<" ";
for(int i=0; i<G.Nnum; i++)
{
if(G.edges[i][j] == 1 && visited[i] == false)
{ DFS(G, i); }
}
}
（2）BFS广度优先搜索：类似树的层次遍历
void BFS(Graph &G, int j)
{//宽度优先分析
visited[j] = true;
queue<int> qu;
qu.push(j);
while(qu.size() != 0)
{
int mark = qu.front();
qu.pop();
cout<<mark<<" ";
for(int i=0; i<G.Nnum; i++)
{
if(G.edges[i][mark] == 1 && visited[i] == false)
{
visited[i] = true;
qu.push(i);
}
}
}
}
4.最小生成树
（1）普里姆算法Prim：算法核心是归并点，适用于稠密网
（2）克鲁斯卡尔算法：算法核心是归并边，适用于稀疏网
5.最短路径