Duncan's Blog

判断无向图是否是一颗树

Veröffentlicht am | in

这是一个基本概念,且很重要,记录一下.

树的定义:用图的知识来表示即为,无环的连通图或者边数等于顶点数减1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
package questionCheckisTree;
import java.util.Scanner;
/**
 * Created by duncan on 17-7-30.
 */
//本题为判断一个无向图是否是一颗树
    //树为无环的连通图或者边数等于顶点数-1
class Graph{
    //邻接矩阵,从1开始存储
    int[][] graph = new int[501][501];
    //顶点数和边数
    int nodes,edges;
}
public class Main {
    //判断是否是连通图,并且顶点数-1是否是边数
    //判断是否是连通图深度遍历一遍,都遍历到了即为连通图
    public void DFS(int[] visited,Graph graph,int start){
        //如果该顶点没有访问过
        if(visited[start] == 0){
            visited[start] = 1;
            //继续访问与其相连的顶点
            for(int i = 1; i <= graph.nodes; i++){
                if(graph.graph[start][i] == 1)
                    DFS(visited,graph,i);
            }
        }
    }
    public static void main(String[] args) {
        Main solution = new Main();
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        for(int i = 0; i < num; i++){
            //输入顶点数和边数
            Graph graph = new Graph();
            graph.nodes = in.nextInt();
            graph.edges = in.nextInt();
            //初始化邻接矩阵
            for(int j = 0; j < graph.edges; j++){
                int a = in.nextInt();
                int b = in.nextInt();
                graph.graph[a][b] = 1;
                graph.graph[b][a] = 1;
            }
            if(graph.edges != graph.nodes - 1)
            {
                System.out.println("NO");
                continue;
            }
            //判断是否连通
            //初始化一个顶点访问数组,从1开始存储
            int[] visited = new int[graph.nodes+1];
            solution.DFS(visited,graph,1);
            //对visited数组判断
            boolean flag = true;
            for(int j = 1; j < graph.nodes; j++) {
                if (visited[j] == 0) {
                    flag = false;
                    break;
                }
            }
            if(flag)
                System.out.println("YES");
            else
                System.out.println("NO");
        }
    }
}
分享