图是由顶点和边组成的集合，其中每条边连接两个顶点。通常用 G=(V, E) 表示图，其中 V 表示顶点集合，E 表示边集合。图的大小表示为 n = |V| 及 m = |E|。
无向图中，每条边连接的两个顶点是一致的。而有向图中，每条边都是一个有序对，边 e=(u, v) 中 u 和 v 的地位是不能交换的。
用 n * n 矩阵 A 表示一个图，其中 A[u][v] = 1 表示 (u, v) 是一条边，反之则不构成一条边。注意这里说的图是无权重图，对于有权重的图，用 A[u][v] = infinity 表示不构成一条边。
图的邻接矩阵表示
用 n 个链表来表示，每个链表存储的都是所有与该结点连接的结点。
图的邻接链表表示
邻接矩阵的好处是可以在常数时间内判断两个顶点是否有边，缺点是如果图是稀疏的，此时的存储是十分不高效的 (Θ(n^2))。
邻接链表在存储更加高效 (Θ(m+n))，尤其是在查找与某个结点相邻的结点时。但邻接链表判断两个顶点是否有边会比较麻烦 (O(degree(u)))。
图的各种算法中，一般使用图的邻接链表表示，但 Floyd-Warshall 算法使用邻接矩阵。
v1, v2, ..., vk，其中任何相邻的两点之间都存在边。当这些点都不相同时，称该路径为简单路径。u 和 v，都存在一条从 u 到 v 的路径，则称该图是连通的。