图论是计算机科学中的一个重要分支，它研究图的数学结构及其性质。图和树在结构上有一定的相似性，实际上，树是从图这种数据结构中衍生出来的。然而，树和图之间存在两个重要的区别：首先，与树不同，图中的一个节点可以有多个父节点；其次，节点之间的连接线可能带有值或权重。图非常适合用来模拟现实世界中的问题，比如表示由道路连接的城市并寻找城市之间的路径，或者模拟空中交通管制系统等。这些问题很难用简单的树结构来表示。
在编程语言中，图由节点和边两部分组成。以Java为例，可以通过类、结构体或链表节点来表示节点。例如，对于上述图，可以如下表示节点：
public class Node {
char data;
public Node(char c) {
this.data = c;
}
}
边表示节点之间的连接。边的表示方法有两种：邻接矩阵和邻接表。邻接矩阵是一个二维数组，其中包含布尔标志。例如，对于上述图，A节点与B、C和D节点相连，因此邻接矩阵在'A'行的'B'、'C'和'D'列将有1。使用邻接矩阵表示边的优点是实现简单，创建或删除边也很容易，只需更新布尔值即可。但是，邻接矩阵的缺点是内存消耗大，因为需要声明N*N的矩阵，其中N是节点总数。此外，信息冗余，即表示A到B和B到A之间的边需要在邻接矩阵中设置两个布尔标志。在Java中，可以将邻接矩阵表示为整数或布尔值的二维数组。
邻接表是一个链表数组。换句话说，它就像一个列表，其元素是链表。对于给定的图示例，边将由下面的邻接表表示：
ArrayList[] adjacencyList = new ArrayList[V];
for (int i = 0; i < V; ++i)
adjacencyList[i] = new ArrayList();
邻接表的优点是节省内存，因为它只需要存储实际存在的边。缺点是对于稀疏图，查找特定节点的邻居可能需要遍历整个链表。
深度优先搜索（DFS）和广度优先搜索（BFS）是遍历和搜索图中节点的两种算法。它们也可以用来找出一个节点是否可达另一个节点。
DFS算法的目标是以尽可能远离根节点的方式遍历图。在DFS的实现中使用了栈。以下是DFS算法的步骤：
public void dfs() {
Stack s = new Stack();
s.push(this.rootNode);
rootNode.visited = true;
printNode(rootNode);
while (!s.isEmpty()) {
Node n = (Node)s.peek();
Node child = getUnvisitedChildNode(n);
if (child != null) {
child.visited = true;
printNode(child);
s.push(child);
} else {
s.pop();
}
}
clearNodes();
}
DFS从根节点开始，然后访问其子节点，直到到达末端节点，然后回溯到父节点。
BFS算法的目标是以尽可能接近根节点的方式遍历图。在BFS的实现中使用了队列。以下是BFS算法的步骤：
public void bfs() {
Queue q = new LinkedList();
q.add(this.rootNode);
printNode(this.rootNode);
rootNode.visited = true;
while (!q.isEmpty()) {
Node n = (Node)q.remove();
Node child = null;
while ((child = getUnvisitedChildNode(n)) != null) {
child.visited = true;
printNode(child);
q.add(child);
}
}
clearNodes();
}
BFS按层遍历节点，因此它将从根节点开始，然后移动到下一层的节点，依此类推。