1.定义：
图的遍历，指的是从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历操作和树的遍历操作功能相似。图的遍历是图的一种基本操作，图的许多其它操作都是建立在遍历操作的基础之上。
由于图结构本身的复杂性，所以图的遍历操作也较复杂，主要表现在以下四个方面：
① 在图结构中，没有一个“自然”的首结点，图中任意一个顶点都可作为第一个被访问的结点。
② 在非连通图中，从一个顶点出发，只能够访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中其余的连通分量。
③ 在图结构中，如果有回路存在，那么一个顶点被访问之后，有可能沿回路又回到该顶点。
④ 在图结构中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，存在如何选取下一个要访问的顶点的问题。
2.算法：
图的遍历方法目前有深度优先搜索法和广度（宽度）优先搜索法两种算法。
深度优先搜索法
深度优先搜索法是树的先根遍历的推广，它的基本思想是：
从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。其递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void DFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum; ++v)
visited[v] = FALSE; //访问标志数组初始化
for(v=0; v<G.vexnum; ++v)
if(!visited[v])
DFS(G, v); //对尚未访问的顶点调用DFS
}
void DFS(Graph G, int v){ //从第v个顶点出发递归地深度优先遍历图G
visited[v]=TRUE; VisitFunc(v); //访问第v个顶点
for(w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w))
//FirstAdjVex返回v的第一个邻接顶点，若顶点在G中没有邻接顶点，则返回空（0）。
//若w是v的邻接顶点，NextAdjVex返回v的（相对于w的）下一个邻接顶点。
//若w是v的最后一个邻接点，则返回空（0）。
if(!visited[w])
DFS(G, w); //对v的尚未访问的邻接顶点w调用DFS
}
广度优先搜索法
图的广度优先搜索是树的按层次遍历的推广，它的基本思想是：
首先访问初始点vi，并将其标记为已访问过，接着访问vi的所有未被访问过的邻接点vi1,vi2,…, vi t，并均标记已访问过，然后再按照vi1,vi2,…, vi t的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依次类推，直到图中所有和初始点vi有路径相通的顶点都被访问过为止。其非递归算法如下：
Boolean visited[MAX_VERTEX_NUM]; //访问标志数组
Status (*VisitFunc)(int v); //VisitFunc是访问函数，对图的每个顶点调用该函数
void BFSTraverse (Graph G, Status(*Visit)(int v)){
VisitFunc = Visit;
for(v=0; v<G.vexnum, ++v)
visited[v] = FALSE;
initQueue(Q); //置空辅助队列Q
for(v=0; v<G.vexnum; ++v)
if(!visited[v]){
visited[v]=TRUE; VisitFunc(v);
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]){ //w为u的尚未访问的邻接顶点
Visited[w]=TRUE; VisitFunc(w);
EnQueue(Q, w);
}
}
}
}
3.实现
实现包括：
1 邻接矩阵实现无向图
2 邻接表实现无向图
3 邻接矩阵实现有向图
4 邻接表实现有向图
- Java:邻接矩阵实现的"无向图"
/*
* Java:邻接矩阵表示的"无向图"
*/
import java.io.IOException;
import java.util.Scanner;
public class MatrixUDG {
private char[] mVexs; // 顶点集合
private int[][] mMatrix; // 邻接矩阵
/*
* 创建图(自己输入数据)
*/
public MatrixUDG() {
// 输入"顶点数"和"边数"
System.out.printf("input vertex number: ");
int vlen = readInt();
System.out.printf("input edge number: ");
int elen = readInt();
if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
System.out.printf("input error: invalid parameters!\n");
return ;
}
// 初始化"顶点"
mVexs = new char[vlen];
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("vertex(%d): ", i);
mVexs[i] = readChar();
}
// 初始化"边"
mMatrix = new int[vlen][vlen];
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
System.out.printf("edge(%d):", i);
char c1 = readChar();
char c2 = readChar();
int p1 = getPosition(c1);
int p2 = getPosition(c2);
if (p1==-1 || p2==-1) {
System.out.printf("input error: invalid edge!\n");
return ;
}
mMatrix[p1][p2] = 1;
mMatrix[p2][p1] = 1;
}
}
/*
* 创建图(用已提供的矩阵)
*
* 参数说明：
* vexs -- 顶点数组
* edges -- 边数组
*/
public MatrixUDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new char[vlen];
for (int i = 0; i < mVexs.length; i++)
mVexs[i] = vexs[i];
// 初始化"边"
mMatrix = new int[vlen][vlen];
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
mMatrix[p1][p2] = 1;
mMatrix[p2][p1] = 1;
}
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i]==ch)
return i;
return -1;
}
/*
* 读取一个输入字符
*/
private char readChar() {
char ch='0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
e.printStackTrace();
}
} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
return ch;
}
/*
* 读取一个输入字符
*/
private int readInt() {
Scanner scanner = new Scanner(System.in);
return scanner.nextInt();
}
/*
* 返回顶点v的第一个邻接顶点的索引，失败则返回-1
*/
private int firstVertex(int v) {
if (v<0 || v>(mVexs.length-1))
return -1;
for (int i = 0; i < mVexs.length; i++)
if (mMatrix[v][i] == 1)
return i;
return -1;
}
/*
* 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
*/
private int nextVertex(int v, int w) {
if (v<0 || v>(mVexs.length-1) || w<0 || w>(mVexs.length-1))
return -1;
for (int i = w + 1; i < mVexs.length; i++)
if (mMatrix[v][i] == 1)
return i;
return -1;
}
/*
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.printf("%c ", mVexs[i]);
// 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w])
DFS(w, visited);
}
}
/*
* 深度优先搜索遍历图
*/
public void DFS() {
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("DFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i])
DFS(i, visited);
}
System.out.printf("\n");
}
/*
* 广度优先搜索（类似于树的层次遍历）
*/
public void BFS() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 辅组队列
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("BFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.printf("%c ", mVexs[i]);
queue[rear++] = i; // 入队列
}
while (head != rear) {
int j = queue[head++]; // 出队列
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) { //k是为访问的邻接顶点
if (!visited[k]) {
visited[k] = true;
System.out.printf("%c ", mVexs[k]);
queue[rear++] = k;
}
}
}
}
System.out.printf("\n");
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("Martix Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
for (int j = 0; j < mVexs.length; j++)
System.out.printf("%d ", mMatrix[i][j]);
System.out.printf("\n");
}
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'C'},
{'A', 'D'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'F', 'G'}};
MatrixUDG pG;
// 自定义"图"(输入矩阵队列)
//pG = new MatrixUDG();
// 采用已有的"图"
pG = new MatrixUDG(vexs, edges);
pG.print(); // 打印图
pG.DFS(); // 深度优先遍历
pG.BFS(); // 广度优先遍历
}
}
- 邻接表实现无向图：
/*
* Java: 邻接表表示的"无向图"
*/
import java.io.IOException;
import java.util.Scanner;
public class ListUDG {
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private VNode[] mVexs; // 顶点数组
/*
* 创建图(自己输入数据)
*/
public ListUDG() {
// 输入"顶点数"和"边数"
System.out.printf("input vertex number: ");
int vlen = readInt();
System.out.printf("input edge number: ");
int elen = readInt();
if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
System.out.printf("input error: invalid parameters!\n");
return ;
}
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("vertex(%d): ", i);
mVexs[i] = new VNode();
mVexs[i].data = readChar();
mVexs[i].firstEdge = null;
}
// 初始化"边"
//mMatrix = new int[vlen][vlen];
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
System.out.printf("edge(%d):", i);
char c1 = readChar();
char c2 = readChar();
int p1 = getPosition(c1);
int p2 = getPosition(c2);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 将node2链接到"p2所在链表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 创建图(用已提供的矩阵)
*
* 参数说明：
* vexs -- 顶点数组
* edges -- 边数组
*/
public ListUDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"边"
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
char c1 = edges[i][0];
char c2 = edges[i][1];
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
// 初始化node2
ENode node2 = new ENode();
node2.ivex = p1;
// 将node2链接到"p2所在链表的末尾"
if(mVexs[p2].firstEdge == null)
mVexs[p2].firstEdge = node2;
else
linkLast(mVexs[p2].firstEdge, node2);
}
}
/*
* 将node节点链接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while(p.nextEdge!=null)
p = p.nextEdge;
p.nextEdge = node;
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i].data==ch)
return i;
return -1;
}
/*
* 读取一个输入字符
*/
private char readChar() {
char ch='0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
e.printStackTrace();
}
} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
return ch;
}
/*
* 读取一个输入字符
*/
private int readInt() {
Scanner scanner = new Scanner(System.in);
return scanner.nextInt();
}
/*
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
ENode node;
visited[i] = true;
System.out.printf("%c ", mVexs[i].data);
node = mVexs[i].firstEdge;
while (node != null) {
if (!visited[node.ivex])
DFS(node.ivex, visited);
node = node.nextEdge;
}
}
/*
* 深度优先搜索遍历图
*/
public void DFS() {
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("DFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i])
DFS(i, visited);
}
System.out.printf("\n");
}
/*
* 广度优先搜索（类似于树的层次遍历）
*/
public void BFS() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 辅组队列
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("BFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.printf("%c ", mVexs[i].data);
queue[rear++] = i; // 入队列
}
while (head != rear) {
int j = queue[head++]; // 出队列
ENode node = mVexs[j].firstEdge;
while (node != null) {
int k = node.ivex;
if (!visited[k])
{
visited[k] = true;
System.out.printf("%c ", mVexs[k].data);
queue[rear++] = k;
}
node = node.nextEdge;
}
}
}
System.out.printf("\n");
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'C'},
{'A', 'D'},
{'A', 'F'},
{'B', 'C'},
{'C', 'D'},
{'E', 'G'},
{'F', 'G'}};
ListUDG pG;
// 自定义"图"(输入矩阵队列)
//pG = new ListUDG();
// 采用已有的"图"
pG = new ListUDG(vexs, edges);
pG.print(); // 打印图
pG.DFS(); // 深度优先遍历
pG.BFS(); // 广度优先遍历
}
}
- 邻接矩阵实现的有向图：
import java.io.IOException;
import java.util.Scanner;
public class MatrixDG {
private char[] mVexs; // 顶点集合
private int[][] mMatrix; // 邻接矩阵
/*
* 创建图(自己输入数据)
*/
public MatrixDG() {
// 输入"顶点数"和"边数"
System.out.printf("input vertex number: ");
int vlen = readInt();
System.out.printf("input edge number: ");
int elen = readInt();
if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
System.out.printf("input error: invalid parameters!\n");
return ;
}
// 初始化"顶点"
mVexs = new char[vlen];
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("vertex(%d): ", i);
mVexs[i] = readChar();
}
// 初始化"边"
mMatrix = new int[vlen][vlen];
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
System.out.printf("edge(%d):", i);
char c1 = readChar();
char c2 = readChar();
int p1 = getPosition(c1);
int p2 = getPosition(c2);
if (p1==-1 || p2==-1) {
System.out.printf("input error: invalid edge!\n");
return ;
}
mMatrix[p1][p2] = 1;
}
}
/*
* 创建图(用已提供的矩阵)
*
* 参数说明：
* vexs -- 顶点数组
* edges -- 边数组
*/
public MatrixDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new char[vlen];
for (int i = 0; i < mVexs.length; i++)
mVexs[i] = vexs[i];
// 初始化"边"
mMatrix = new int[vlen][vlen];
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
mMatrix[p1][p2] = 1;
}
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i]==ch)
return i;
return -1;
}
/*
* 读取一个输入字符
*/
private char readChar() {
char ch='0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
e.printStackTrace();
}
} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
return ch;
}
/*
* 读取一个输入字符
*/
private int readInt() {
Scanner scanner = new Scanner(System.in);
return scanner.nextInt();
}
/*
* 返回顶点v的第一个邻接顶点的索引，失败则返回-1
*/
private int firstVertex(int v) {
if (v<0 || v>(mVexs.length-1))
return -1;
for (int i = 0; i < mVexs.length; i++)
if (mMatrix[v][i] == 1)
return i;
return -1;
}
/*
* 返回顶点v相对于w的下一个邻接顶点的索引，失败则返回-1
*/
private int nextVertex(int v, int w) {
if (v<0 || v>(mVexs.length-1) || w<0 || w>(mVexs.length-1))
return -1;
for (int i = w + 1; i < mVexs.length; i++)
if (mMatrix[v][i] == 1)
return i;
return -1;
}
/*
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
visited[i] = true;
System.out.printf("%c ", mVexs[i]);
// 遍历该顶点的所有邻接顶点。若是没有访问过，那么继续往下走
for (int w = firstVertex(i); w >= 0; w = nextVertex(i, w)) {
if (!visited[w])
DFS(w, visited);
}
}
/*
* 深度优先搜索遍历图
*/
public void DFS() {
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("DFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i])
DFS(i, visited);
}
System.out.printf("\n");
}
/*
* 广度优先搜索（类似于树的层次遍历）
*/
public void BFS() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 辅组队列
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("BFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.printf("%c ", mVexs[i]);
queue[rear++] = i; // 入队列
}
while (head != rear) {
int j = queue[head++]; // 出队列
for (int k = firstVertex(j); k >= 0; k = nextVertex(j, k)) { //k是为访问的邻接顶点
if (!visited[k]) {
visited[k] = true;
System.out.printf("%c ", mVexs[k]);
queue[rear++] = k;
}
}
}
}
System.out.printf("\n");
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("Martix Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
for (int j = 0; j < mVexs.length; j++)
System.out.printf("%d ", mMatrix[i][j]);
System.out.printf("\n");
}
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'B'},
{'B', 'C'},
{'B', 'E'},
{'B', 'F'},
{'C', 'E'},
{'D', 'C'},
{'E', 'B'},
{'E', 'D'},
{'F', 'G'}};
MatrixDG pG;
// 自定义"图"(输入矩阵队列)
//pG = new MatrixDG();
// 采用已有的"图"
pG = new MatrixDG(vexs, edges);
pG.print(); // 打印图
pG.DFS(); // 深度优先遍历
pG.BFS(); // 广度优先遍历
}
}
- 邻接表实现有向图：
/*
* Java: 邻接矩阵图
*/
import java.io.IOException;
import java.util.Scanner;
public class ListDG {
// 邻接表中表对应的链表的顶点
private class ENode {
int ivex; // 该边所指向的顶点的位置
ENode nextEdge; // 指向下一条弧的指针
}
// 邻接表中表的顶点
private class VNode {
char data; // 顶点信息
ENode firstEdge; // 指向第一条依附该顶点的弧
};
private VNode[] mVexs; // 顶点数组
/*
* 创建图(自己输入数据)
*/
public ListDG() {
// 输入"顶点数"和"边数"
System.out.printf("input vertex number: ");
int vlen = readInt();
System.out.printf("input edge number: ");
int elen = readInt();
if ( vlen < 1 || elen < 1 || (elen > (vlen*(vlen - 1)))) {
System.out.printf("input error: invalid parameters!\n");
return ;
}
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("vertex(%d): ", i);
mVexs[i] = new VNode();
mVexs[i].data = readChar();
mVexs[i].firstEdge = null;
}
// 初始化"边"
//mMatrix = new int[vlen][vlen];
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
System.out.printf("edge(%d):", i);
char c1 = readChar();
char c2 = readChar();
int p1 = getPosition(c1);
int p2 = getPosition(c2);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
}
}
/*
* 创建图(用已提供的矩阵)
*
* 参数说明：
* vexs -- 顶点数组
* edges -- 边数组
*/
public ListDG(char[] vexs, char[][] edges) {
// 初始化"顶点数"和"边数"
int vlen = vexs.length;
int elen = edges.length;
// 初始化"顶点"
mVexs = new VNode[vlen];
for (int i = 0; i < mVexs.length; i++) {
mVexs[i] = new VNode();
mVexs[i].data = vexs[i];
mVexs[i].firstEdge = null;
}
// 初始化"边"
for (int i = 0; i < elen; i++) {
// 读取边的起始顶点和结束顶点
char c1 = edges[i][0];
char c2 = edges[i][1];
// 读取边的起始顶点和结束顶点
int p1 = getPosition(edges[i][0]);
int p2 = getPosition(edges[i][1]);
// 初始化node1
ENode node1 = new ENode();
node1.ivex = p2;
// 将node1链接到"p1所在链表的末尾"
if(mVexs[p1].firstEdge == null)
mVexs[p1].firstEdge = node1;
else
linkLast(mVexs[p1].firstEdge, node1);
}
}
/*
* 将node节点链接到list的最后
*/
private void linkLast(ENode list, ENode node) {
ENode p = list;
while(p.nextEdge!=null)
p = p.nextEdge;
p.nextEdge = node;
}
/*
* 返回ch位置
*/
private int getPosition(char ch) {
for(int i=0; i<mVexs.length; i++)
if(mVexs[i].data==ch)
return i;
return -1;
}
/*
* 读取一个输入字符
*/
private char readChar() {
char ch='0';
do {
try {
ch = (char)System.in.read();
} catch (IOException e) {
e.printStackTrace();
}
} while(!((ch>='a'&&ch<='z') || (ch>='A'&&ch<='Z')));
return ch;
}
/*
* 读取一个输入字符
*/
private int readInt() {
Scanner scanner = new Scanner(System.in);
return scanner.nextInt();
}
/*
* 深度优先搜索遍历图的递归实现
*/
private void DFS(int i, boolean[] visited) {
ENode node;
visited[i] = true;
System.out.printf("%c ", mVexs[i].data);
node = mVexs[i].firstEdge;
while (node != null) {
if (!visited[node.ivex])
DFS(node.ivex, visited);
node = node.nextEdge;
}
}
/*
* 深度优先搜索遍历图
*/
public void DFS() {
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
// 初始化所有顶点都没有被访问
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("DFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i])
DFS(i, visited);
}
System.out.printf("\n");
}
/*
* 广度优先搜索（类似于树的层次遍历）
*/
public void BFS() {
int head = 0;
int rear = 0;
int[] queue = new int[mVexs.length]; // 辅组队列
boolean[] visited = new boolean[mVexs.length]; // 顶点访问标记
for (int i = 0; i < mVexs.length; i++)
visited[i] = false;
System.out.printf("BFS: ");
for (int i = 0; i < mVexs.length; i++) {
if (!visited[i]) {
visited[i] = true;
System.out.printf("%c ", mVexs[i].data);
queue[rear++] = i; // 入队列
}
while (head != rear) {
int j = queue[head++]; // 出队列
ENode node = mVexs[j].firstEdge;
while (node != null) {
int k = node.ivex;
if (!visited[k])
{
visited[k] = true;
System.out.printf("%c ", mVexs[k].data);
queue[rear++] = k;
}
node = node.nextEdge;
}
}
}
System.out.printf("\n");
}
/*
* 打印矩阵队列图
*/
public void print() {
System.out.printf("List Graph:\n");
for (int i = 0; i < mVexs.length; i++) {
System.out.printf("%d(%c): ", i, mVexs[i].data);
ENode node = mVexs[i].firstEdge;
while (node != null) {
System.out.printf("%d(%c) ", node.ivex, mVexs[node.ivex].data);
node = node.nextEdge;
}
System.out.printf("\n");
}
}
public static void main(String[] args) {
char[] vexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
char[][] edges = new char[][]{
{'A', 'B'},
{'B', 'C'},
{'B', 'E'},
{'B', 'F'},
{'C', 'E'},
{'D', 'C'},
{'E', 'B'},
{'E', 'D'},
{'F', 'G'}};
ListDG pG;
// 自定义"图"(输入矩阵队列)
//pG = new ListDG();
// 采用已有的"图"
pG = new ListDG(vexs, edges);
pG.print(); // 打印图
pG.DFS(); // 深度优先遍历
pG.BFS(); // 广度优先遍历
}
}