Поиграйте с алгоритмом теории графов (1) Основное представление графа

График, показанный в 1.1(а), может быть выражен как

Элементы в являются вершинами (представлены порядковыми номерами, в других графах элементы в наборе вершин также могут быть другими символами, идентифицирующими вершины,

как буквы

Набор ребер:

масса(вес): ребро некоторого графа имеет связанное с ним число, называемое весом.

Следующие диаграммы представляют:Неориентированный граф, ориентированный граф

На приведенном выше рисунке а: Показанная ненаправленная сеть может быть выражена как

Поэтому его можно разделить на 4 категории по направлению и весу графика:

​

В неориентированном графе, если существует путь из вершины u в v, то вершины u и v называютсясвязанный(связанный).

Если любая пара вершин неориентированного графа соединена, то такой граф называетсясвязный граф(связныйграф);

Наоборот, если неориентированный граф несвязен, он называетсяОтключенный граф(несвязный график).

Если неориентированный граф несвязен, то его максимально связный подграф называетсяподключенные компоненты(

​

остовное дерево(остовное дерево): остовным деревом неориентированного связного графа называется его минимальный связный подграф, содержащий все вершины, так называемое минимальное здесь — это минимальное количество ребер.

Если фигура имеетnвершины, остовное дерево имеетn-1 край. Неориентированный связный граф может иметь несколько остовных деревьев.

​

В методе хранения матрицы смежности в дополнение к записи информации о каждой вершинемассив вершинКроме того, существует также представление каждой вершины

Матрица отношений междуматрица смежности(). 1, если две вершины смежные, 0, если не смежные.

import java.io.File;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;

//只是处理简单的图
public class AdjMatrix {
	
	private int V;  // 图的顶点的数量
	private int E;  // 图的边的数量
	private int[][] adj;  // 邻接矩阵
	
	public AdjMatrix(String filename) {
		File file = new File(filename);
		
		try {
			// 读取文件
			Scanner scanner = new Scanner(file);
			V = scanner.nextInt();
			// 判断顶点数量是否有误
			if (V < 0) throw new IllegalArgumentException("V 必须是个不为负数的数值");
			adj = new int[V][V];  // 创建二维矩阵
			
			E = scanner.nextInt();
			if (V < 0) throw new IllegalArgumentException("E 必须是个不为负数的数值");
			for (int i = 0; i< E; i++) {
				int a = scanner.nextInt();
				validateVertex(a);
				int b = scanner.nextInt();
				validateVertex(b);
				// 判断是否是自环边
				if (a == b) throw new IllegalArgumentException("不允许存在自环边");
				if (adj[a][b] == 1) throw new IllegalArgumentException("不允许存在平行边");
				adj[a][b] = 1;
				adj[b][a] = 1;
			}
			
		} catch (IOException e) {
			e.printStackTrace();
		}
	}
	
	private void validateVertex(int v) {
		if (v < 0 || v > V) {
			throw new IllegalArgumentException("输入的数值" + v +"不合法");
		}
	}
	
	// 获取指定结点相邻的结点
	public ArrayList<Integer> adj(int v){
		validateVertex(v);
		ArrayList<Integer> res = new ArrayList<>();
		
		for (int i = 0; i < V; i++) {  // 顶点的数量
			if (adj[v][i] == 1) {
				res.add(i);
			}
		}
		return res;
	}
	
	// 获取指定结点的度，即相邻的结点的数量
	public int degree(int v) {
		return adj(v).size();
	}
	
	public int V() {
		return V;
	}
	
	public int E() {
		return E;
	}
	
	public boolean hasEdge(int x, int y) {  // 依据两个顶点判断边是否存在
		validateVertex(x);
		validateVertex(y);
		return adj[x][y] == 1;
	}
	
	public String toString() {
		
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append(String.format("V = %d, E = %d \n", V, E)); 
		// 打印出矩阵
		for (int i =0; i< V; i++) {
			for (int j = 0; j < V; j++) {
				stringBuilder.append(String.format("%d ", adj[i][j]));
			}
			stringBuilder.append("\n");
		}
		
		return stringBuilder.toString();
		
	}

	public static void main(String[] args) {
		AdjMatrix adjMatrix = new AdjMatrix("g.txt");
		System.out.println(adjMatrix);
//		V = 7, E = 9 
//		0 1 0 1 0 0 0 
//		1 0 1 0 0 0 1 
//		0 1 0 1 0 1 0 
//		1 0 1 0 1 0 0 
//		0 0 0 1 0 1 0 
//		0 0 1 0 1 0 1 
//		0 1 0 0 0 1 0 
		System.out.println(adjMatrix.adj(2).toString());
		System.out.println(adjMatrix.degree(2));

	}

}

​