算法之美-java图的表示(邻接矩阵、邻接表、有向、无向图)

算法之美-java图的表示(邻接矩阵、邻接表、有向、无向图)

图是用来表示结点之间相互连接的一种状态，无向图是一种特殊的有向图。

所以无论是邻接矩阵还是邻接表都可以用来表示有向或者无向图。

一般情况下直接告诉你那个节点是互相连接的问题相对比较简单的，而给出一个二维矩阵的时候需要根据条件进行判断了，并不一定上下左右相邻的节点就是相互连接的节点。

一般有些时候会很明确的告诉你哪些点是连接在一起的，比如下面的例子：

7 12
1 2
6 1
3 1
2 3
2 4
2 5
2 7
3 4
4 5
5 6
5 7
6 7

直接告诉你1和2、6和1是互相连接的了

 

而在二维矩阵中，告诉你移动的规则，需要进一步的加工来确定节点间有无连接

只能向右或向下移动，经过1最多的路线。向右向下表示下边的和右边的节点与本身节点是相连的。

6
0 0 0 0 0 0
0 0 1 0 0 0
0 0 0 1 0 0
1 1 0 0 0 0
1 0 1 0 0 0 
1 0 0 1 0 0 

只能向左或向右移动矩阵中值的步数，到右下角经过的最小的路线

4
1 2 0 3
1 3 2 1
2 3 2 3
1 2 1 1 

只能由高的数字往低的数字移动，经过的最长路线，表示上下左右数字低的节点与自己是相连的

4 4
7 8 9 10
6 15 16 11
5 14 13 12
4 3 2 1

当然了，矩阵也可以是无向图

比如下面计算有几个区块，表示上下左右只要是1的就与自己相连了。

4 5
1 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 0 1 1

 

经典案例：

广度优先下的邻接表的使用

需要把要遍历的点放入队列中

只能从高的数字往低的数字移动，计算可以移动的最大距离

 4 4
 7 8 9 10
 6 15 16 11
 5 14 13 12
 4 3 2 1

需要把二维数组转为一维数组，从上下左右的相对位置来查看点与点之间哪些是直接连接的

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Test{
	static List totallist;
	static int[][] Map;
	static boolean[] visited;
	static int MaxCount;
	static int Count;
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int R = scanner.nextInt();
		int C = scanner.nextInt();
		totallist = new ArrayList();
		Map = new int[R][C];
		for(int i=0;i0) {
					totallist.get(i*C+j).add(i*C+j-1);
				}
				if(j+10) {
					totallist.get(i*C+j).add(i*C+j+1);
				}
			}
		}
		MaxCount=0;
		for(int i=0;iCount?MaxCount:Count;
		}
		System.out.println(MaxCount);
		
	}
}

输出：

 

广度优先下的邻接矩阵

统计区块的个数(相邻的结点统计数要除2然后四舍五入)

4 5
1 1 0 1 0
1 0 1 0 1
0 1 0 1 0 
1 0 0 1 1

通过上下左右就可以判断哪些节点是直接连接的

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Test{
static int R;
static int C;
static int[][] Map;
static boolean[][] visited;
static int count;
public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	R = scanner.nextInt();
	C = scanner.nextInt();
	Map = new int[R][C];
	visited = new boolean[R][C];
	for(int i=0;i