Comment utiliser la matrice de contiguïté pour stocker un graphique en Java ?

1. La touche finale

La matrice de contiguïté utilise généralement un tableau unidimensionnel pour stocker les informations des nœuds dans le graphique, et utilise un tableau bidimensionnel pour stocker la relation de contiguïté entre les nœuds du graphique. graphique.

La matrice d'adjacence peut être utilisée pour représenter des graphiques non orientés, des graphiques orientés et des réseaux.

1. Matrice de contiguïté du graphe non orienté

Dans le graphe non orienté, s'il y a une arête du nœud Vi au nœud Vj, alors la matrice de contiguïté M[i][j] = M[j][i]= 1, sinon M[i][j] = 0.

La matrice de contiguïté d'un graphe non orienté est spécifiée comme suit.

a La matrice de contiguïté d'un graphe non orienté est une matrice symétrique et unique.

b Le nombre de non-zéros dans la i-ème ligne ou la i-ème colonne est exactement le degré du i-ème nœud.

2. Matrice d'adjacence du graphe orienté

Dans le graphe orienté, s'il y a une arête du nœud Vi au nœud Vj, alors la matrice d'adjacence M[i][j]=1, sinon M[i][j] = 0.

La matrice d'adjacence d'un graphe orienté est spécifiée comme suit.

a La matrice d'adjacence d'un graphe orienté n'est pas nécessairement symétrique.

b Le nombre d'éléments non nuls dans la i-ème ligne est exactement le degré extérieur du i-ème nœud, et le nombre d'éléments non nuls dans la i-ème colonne est exactement le degré entrant de le ième nœud.

3. La matrice de contiguïté du réseau

Le réseau est un graphe pondéré et doit stocker les poids des arêtes s'exprime comme : M[i][j] = Wij, et c'est le cas. infini dans les autres cas.

2. Étapes de l'algorithme

1 Entrez le nombre de nœuds et d'arêtes.

2 Entrez tour à tour les informations du nœud et stockez-les dans le tableau de nœuds Vex[].

3 Initialisez la matrice d'adjacence, si c'est un graphe, initialisez-la à 0, si c'est un réseau, initialisez-la à l'infini.

4 Saisissez tour à tour les deux nœuds attachés à chaque bord. S'il s'agit d'un réseau, vous devez également saisir le poids du bord.

• S'il s'agit d'un graphe non orienté, saisissez a et b, interrogez les indices de stockage i et j des nœuds a et b dans le tableau de nœuds Vex[], laissez Edge[i][j]=Edge[j][ je]=1.

• S'il s'agit d'un graphe orienté, saisissez a, b, interrogez les indices de stockage i, j des nœuds a, b dans le tableau de nœuds Vex[], laissez Edge[i][j]=1.

• S'il s'agit d'un réseau non orienté, saisissez a, b, w, interrogez les indices de stockage i et j des nœuds a et b dans le tableau de nœuds Vex[], laissez Edge[i][j]=Edge[j ][je]=w.

• S'il s'agit d'un réseau dirigé, saisissez a, b, w, interrogez les indices de stockage i et j des nœuds a et b dans le tableau de nœuds Vex[], laissez Edge[i][j]=w.

3. Implémentation

package graph;
 
import java.util.Scanner;
 
public class CreateAMGraph {
    static final int MaxVnum = 100;  // 顶点数最大值
 
    static int locatevex(AMGraph G, char x) {
        for (int i = 0; i < G.vexnum; i++) // 查找顶点信息的下标
            if (x == G.Vex[i])
                return i;
        return -1; // 没找到
    }
 
    static void CreateAMGraph(AMGraph G) {
        Scanner scanner = new Scanner(System.in);
        int i, j;
        char u, v;
        System.out.println("请输入顶点数：");
        G.vexnum = scanner.nextInt();
        System.out.println("请输入边数:");
        G.edgenum = scanner.nextInt();
        System.out.println("请输入顶点信息:");
 
        // 输入顶点信息，存入顶点信息数组
        for (int k = 0; k < G.vexnum; k++) {
            G.Vex[k] = scanner.next().charAt(0);
        }
        //初始化邻接矩阵所有值为0，如果是网，则初始化邻接矩阵为无穷大
        for (int m = 0; m < G.vexnum; m++)
            for (int n = 0; n < G.vexnum; n++)
                G.Edge[m][n] = 0;
 
        System.out.println("请输入每条边依附的两个顶点：");
        while (G.edgenum-- > 0) {
            u = scanner.next().charAt(0);
            v = scanner.next().charAt(0);
 
            i = locatevex(G, u);// 查找顶点 u 的存储下标
            j = locatevex(G, v);// 查找顶点 v 的存储下标
            if (i != -1 && j != -1)
                G.Edge[i][j] = G.Edge[j][i] = 1; //邻接矩阵储置1
            else {
                System.out.println("输入顶点信息错！请重新输入！");
                G.edgenum++; // 本次输入不算
            }
        }
    }
 
    static void print(AMGraph G) { // 输出邻接矩阵
        System.out.println("图的邻接矩阵为：");
        for (int i = 0; i < G.vexnum; i++) {
            for (int j = 0; j < G.vexnum; j++)
                System.out.print(G.Edge[i][j] + "\t");
            System.out.println();
        }
    }
 
    public static void main(String[] args) {
        AMGraph G = new AMGraph();
        CreateAMGraph(G);
        print(G);
    }
}
 
class AMGraph {
    char Vex[] = new char[CreateAMGraph.MaxVnum];
    int Edge[][] = new int[CreateAMGraph.MaxVnum][CreateAMGraph.MaxVnum];
    int vexnum; // 顶点数
    int edgenum; // 边数
}

4. Test

Le vert est l'entrée et le blanc est la sortie.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!