Java編程如何實(shí)現(xiàn)鄰接矩陣表示稠密圖-創(chuàng)新互聯(lián)

這篇文章主要介紹了Java編程如何實(shí)現(xiàn)鄰接矩陣表示稠密圖，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)擁有一支富有激情的企業(yè)網(wǎng)站制作團(tuán)隊(duì)，在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)深耕10多年，專業(yè)且經(jīng)驗(yàn)豐富。10多年網(wǎng)站優(yōu)化營銷經(jīng)驗(yàn)，我們已為上千余家中小企業(yè)提供了成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站制作解決方案，按需設(shè)計(jì)網(wǎng)站，設(shè)計(jì)滿意，售后服務(wù)無憂。所有客戶皆提供一年免費(fèi)網(wǎng)站維護(hù)!

我們知道，要表示結(jié)點(diǎn)，我們可以用一個(gè)一維數(shù)組來表示，然而對于結(jié)點(diǎn)和結(jié)點(diǎn)之間的關(guān)系，則無法簡單地用一維數(shù)組來表示了，我們可以用二維數(shù)組來表示，也就是一個(gè)矩陣形式的表示方法。

我們假設(shè)A是這個(gè)二維數(shù)組，那么A中的一個(gè)元素aij不僅體現(xiàn)出了結(jié)點(diǎn)vi和結(jié)點(diǎn)vj的關(guān)系，而且aij的值正可以表示權(quán)值的大小。

鄰接矩陣模型類

鄰接矩陣模型類的類名為AMWGraph.java，能夠通過該類構(gòu)造一個(gè)鄰接矩陣表示的圖，且提供插入結(jié)點(diǎn)，插入邊，取得某一結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)和下一個(gè)鄰接結(jié)點(diǎn)。

import java.util.ArrayList;
import java.util.LinkedList;

public class AMWGraph {
 private ArrayList vertexList;
 //存儲點(diǎn)的鏈表
 private int[][] edges;
 //鄰接矩陣，用來存儲邊
 private int numOfEdges;
 //邊的數(shù)目
 public AMWGraph(int n) {
  //初始化矩陣，一維數(shù)組，和邊的數(shù)目
  edges=new int[n][n];
  vertexList=new ArrayList(n);
  numOfEdges=0;
 }
 //得到結(jié)點(diǎn)的個(gè)數(shù)
 public int getNumOfVertex() {
  return vertexList.size();
 }
 //得到邊的數(shù)目
 public int getNumOfEdges() {
  return numOfEdges;
 }
 //返回結(jié)點(diǎn)i的數(shù)據(jù)
 public Object getValueByIndex(int i) {
  return vertexList.get(i);
 }
 //返回v1,v2的權(quán)值
 public int getWeight(int v1,int v2) {
  return edges[v1][v2];
 }
 //插入結(jié)點(diǎn)
 public void insertVertex(Object vertex) {
  vertexList.add(vertexList.size(),vertex);
 }
 //插入結(jié)點(diǎn)
 public void insertEdge(int v1,int v2,int weight) {
  edges[v1][v2]=weight;
  numOfEdges++;
 }
 //刪除結(jié)點(diǎn)
 public void deleteEdge(int v1,int v2) {
  edges[v1][v2]=0;
  numOfEdges--;
 }
 //得到第一個(gè)鄰接結(jié)點(diǎn)的下標(biāo)
 public int getFirstNeighbor(int index) {
  for (int j=0;j<vertexList.size();j++) {
   if (edges[index][j]>0) {
    return j;
   }
  }
  return -1;
 }
 //根據(jù)前一個(gè)鄰接結(jié)點(diǎn)的下標(biāo)來取得下一個(gè)鄰接結(jié)點(diǎn)
 public int getNextNeighbor(int v1,int v2) {
  for (int j=v2+1;j<vertexList.size();j++) {
   if (edges[v1][j]>0) {
    return j;
   }
  }
  return -1;
 }
}

下面再看看java編程實(shí)現(xiàn)鄰接矩陣表示稠密圖代碼：

package com.dataStructure.graph;
//// 稠密圖 - 使用鄰接矩陣表示
//public class DenseGraph {
//
//  private int n; // 節(jié)點(diǎn)數(shù)
//  private int m; // 邊數(shù)
//  private boolean directed;  // 是否為有向圖
//  private boolean[][] g;   // 圖的具體數(shù)據(jù)
//
//  // 構(gòu)造函數(shù)
//  public DenseGraph(int n, boolean directed) {
//    assert n >= 0;
//    this.n = n;
//    this.m = 0;  // 初始化沒有任何邊
//    this.directed = directed;
//    // g初始化為n*n的布爾矩陣, 每一個(gè)g[i][j]均為false, 表示沒有任和邊
//    // false為boolean型變量的默認(rèn)值
//    g = new boolean[n][n];
//  }
//
//  public int V() {
//    return n;
//  } // 返回節(jié)點(diǎn)個(gè)數(shù)
//
//  public int E() {
//    return m;
//  } // 返回邊的個(gè)數(shù)
//
//  // 向圖中添加一個(gè)邊
//  public void addEdge(int v, int w) {
//
//    assert v >= 0 && v < n;
//    assert w >= 0 && w < n;
//
//    if (hasEdge(v, w))
//      return;
//
//    // 連接 v 和 w
//    g[v][w] = true;
//    if (!directed)
//      g[w][v] = true;
//
//    // 邊數(shù) ++
//    m++;
//  }
//
//  // 驗(yàn)證圖中是否有從v到w的邊
//  boolean hasEdge(int v, int w) {
//    assert v >= 0 && v < n;
//    assert w >= 0 && w < n;
//    return g[v][w];
//  }
//
//  // 返回圖中一個(gè)頂點(diǎn)的所有鄰邊
//  // 由于java使用引用機(jī)制，返回一個(gè)Vector不會(huì)帶來額外開銷,
//  public Iterable<Integer> adj(int v) {
//      assert v >= 0 && v < n;
//      Vector<Integer> adjV = new Vector<Integer>();
//      for(int i = 0 ; i < n ; i ++ )
//      if( g[v][i] )
//      adjV.add(i);
//      return adjV;
//      }
//}
import java.util.ArrayList;
import java.util.List;
// 使用 鄰接矩陣 表示 稠密圖
public class DenseGraph{
 private int n;
 // 圖中的節(jié)點(diǎn)數(shù)
 private int m;
 // 圖中的邊數(shù)
 private Boolean[][] g;
 // 鄰接矩陣g
 private Boolean directed;
 // 是否為有向圖
 public DenseGraph(int n, Boolean directed){
  this.n = n;
  // 初始化圖中的節(jié)點(diǎn)數(shù)量
  this.m = 0;
  // 圖中邊（edge）的數(shù)量初始化為0
  this.directed = directed;
  g = new Boolean[n][n];
  // 鄰接矩陣 g 初始化為一個(gè) n*n 的二維矩陣
  // 索引代表圖中的節(jié)點(diǎn)，g中存儲的值為 節(jié)點(diǎn)是否有邊
 }
 // 返回圖中邊的數(shù)量
 public int E(){
  return m;
 }
 // 返回圖中節(jié)點(diǎn)的數(shù)量
 public int V(){
  return n;
 }
 // 在圖中指定的兩節(jié)點(diǎn)之間加邊
 public void addEdge(int v, int w){
  if (!hasEdge(v, w)){
   // 連接[v][w]
   g[v][w] = true;
   // 無向圖
   if (!directed)
           g[w][v] = true;
   // 圖中邊的數(shù)量+1
   m++;
  }
 }
 // 判斷兩節(jié)點(diǎn)之間是否有邊
 private Boolean hasEdge(int v, int w){
  return g[v][w];
 }
 // 返回所有 節(jié)點(diǎn) v 的 鄰接節(jié)點(diǎn)
 public Iterable<Integer> adjacentNode(int v){
  // adjacentL 用于存儲 v 的鄰接節(jié)點(diǎn)
  List<Integer> adjacentL = new ArrayList<>();
  // 找到所有與 v 鄰接的節(jié)點(diǎn)，將其加入 adjacentL 中
  for (int i = 0; i < n;i++){
   if (g[v][i])
           adjacentL.add(i);
  }
  return adjacentL;
 }
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“Java編程如何實(shí)現(xiàn)鄰接矩陣表示稠密圖”這篇文章對大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識等著你來學(xué)習(xí)!

文章題目：Java編程如何實(shí)現(xiàn)鄰接矩陣表示稠密圖-創(chuàng)新互聯(lián)
鏈接URL：http://bm7419.com/article26/igscg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供虛擬主機(jī)、網(wǎng)站導(dǎo)航、網(wǎng)站策劃、微信公眾號、營銷型網(wǎng)站建設(shè)、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)