基本概念
完全图：图中有n个结点，n(n-1
)/2条边的无向图。
有向完全图：图中有n个结点，n(n-1
)条弧的有向图。
稀疏图：假设图中有n个结点e条边，若边的个数 e < nlogn, 则称为稀疏图。
简单路径：顶点不重复的路径称为简单路径。
回路：首尾顶点相同的路径称为回路。
连通图：任意两个结点间都有路径连通。
强连通图：在有向图中，
任意两个顶点之间存在一条有向路径。
生成树：包含连通图中的全部顶点的极小连通子图称为该图的生成树，假设一个连通图有n个顶点，其中n个顶点和n-1条边构成一个极小的连通图。
邻接矩阵：可以表示图中顶点之间的相邻关系。对于具有n个顶点的无向图，只需n(n-1)/2个空间。矩阵对称。对于有向图，邻接矩阵不一定对称，所以需要n^2个空间。
邻接表：用于解决稀疏图时使用邻接矩阵造成的空间浪费问题，逆邻接矩阵的结构与邻接表完全相同，只是边表中每个结点存放的是该顶点通过入度弧所邻接的所有顶点。
十字链表：有向图的另一种链式存储结构，可以看成邻接表和逆邻接表的结合。
数据类型描述：
typedef struct ArcNode
{
int tailvex, headvex; //起点终点的顶点序号
int weight;
struct ArcNode *hnextarc, *tnextarc; //指向具有同一起点或者终点的下一条弧
}ArcNode;
typedef struct VertexNode
{
char vexdata;
ArcNode *head, *tail;
}VertexNode;
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum; //顶点数
int arcnum; //弧数
}OrthList;
多重链表：适用于无向图的链式存储方式，在多重链表中存放的是真正的边。
邻接矩阵：可以表示图中顶点之间的相邻关系。对于具有n个顶点的无向图，只需n(n-1)/2个空间。矩阵对称。对于有向图，邻接矩阵不一定对称，所以需要n^2个空间。
邻接表：用于解决稀疏图时使用邻接矩阵造成的空间浪费问题，逆邻接矩阵的结构与邻接表完全相同，只是边表中每个结点存放的是该顶点通过入度弧所邻接的所有顶点。
十字链表：有向图的另一种链式存储结构，可以看成邻接表和逆邻接表的结合。
数据类型描述：
typedef struct ArcNode
{
int tailvex, headvex; //起点终点的顶点序号
int weight;
struct ArcNode *hnextarc, *tnextarc; //指向具有同一起点或者终点的下一条弧
}ArcNode;
typedef struct VertexNode
{
char vexdata;
ArcNode *head, *tail;
}VertexNode;
typedef struct
{
VertexNode vertex[MAXVEX];
int vexnum; //顶点数
int arcnum; //弧数
}OrthList;
多重链表：适用于无向图的链式存储方式，在多重链表中存放的是真正的边。
递归深度优先搜索遍历连通子图
int visited[MAXVEX
] = {0
};
void DFS (Graph g, int v0
)
{
visit(v0
);
visited[v0] = 1
;
w = FirstAdjVex(g, v0
);
while (w != -1
) {
if (
!visited[w]
)
DFS(g, w
);
w = NexAdjVex(g, v0, w );
w = NexAdjVex(g, v0, w );
}
}
非递归深度优先搜索遍历连通子图
void DFS (Graph g, int v0
)
{
InitStack(S
);
int visited[MAXEX
] = {0
};
Push(S, v0
);
while ( ! Empty(S
)
) {
v= Pop(S
);
if (
!visited[v
]
) {
visit(v
);
visited[v
] = 1;
}
w = FirstAdjVertex(g, v
)
; //图g中顶点v的第一个邻接点
whil
e ( w != -1
) {
if ( !visit[w]) Push(S, w
);
w = NextAdjVertex(g, v, w
);
//图g中顶点v的下一个邻接点
}
}
}
对于具有n个顶点e条边的无向图或有向图，用邻接矩阵存储，时间复杂度O(n^2)。用邻接表存储，时间复杂度为O(e)。对应的深度优先搜索遍历算法的时间复杂度为O(n+e)。
广度优先搜索遍历连通子图
void BFS (Graph g, int v0
)
{
visit(v0
);
visited[0
] = 1;
InitQueue(Q
);
EnterQueue(&Q, v0
);
while ( !Empty(Q
)
) {
DeleteQueue(&Q, &v
);
w = FirstAdj(g , v
);
while ( w != -1
) {
if ( !visited[w]) {
visit(w
);
visited[w] = 1;
EnterQueue(&Q, w
);
}
w = NextAdj(g, v, w
);
}
}
}
若在遍历过程中不止一次的调用搜索过程，则说明该图是一个非连通图，而且调用几次遍历过程，说明该图有几个连通分量。判断图中是否有回路，DFS可以，BFS不行。
图的应用
概念
图G的生成树是指该图的一个极小的连通子图，含有图中的全部n个顶点，但只有足以构成一棵树的n-1条边。生成树不唯一，n-1条边权值之和最小的生成树就是最小代价生成树。
1.Prim算法
加点法。从连通图某一顶点v0出发，选择与它关联的具有最小权值的边将其顶点加入到生成树的集合U
中。
2.Kruskal算法（主要由边的排序、判断以及合并连通分量实现）
加边法。先构造一个只含n个顶点的子图SG,然后从权值最小的开始，若他的添加不使SG产生回路，则在SG中加入该边。（将边的权值从小到大
排序，
依次加入
）时间复杂度O(elog2
(e
)
)。
拓扑排序
从有向图中选取一个没有前驱的顶点并输出。
从有向图中删去该顶点以及所有以他为尾的弧。
重复上述两步，直到图空。拓扑序列可以检查有向图中是否存在回路。