數據結構實驗十一 圖的創建與存儲

一、實驗目的

1、 理解圖的存儲結構與基本操作；
2、 掌握圖的創建過程

二、實驗內容

1.請把下圖以鄰接矩陣的結構存儲，并打印輸出此鄰接矩陣。
圖的創建代碼參考教材例題.
提示:首先構建圖的邏輯模型，得出該圖的頂點集和邊集，調用相應的函數生成圖的鄰接矩陣，并打印出鄰接矩陣。
2.用鄰接表存儲上圖，并輸出鄰接表。（此題為選做）

三、【實驗源代碼】

🍻 CPP版

#include<iostream>
using namespace std;const int MAX_N = 6;
const int MAX_M = 6 * 5;int g[MAX_N][MAX_N]; // 鄰接矩陣
int h[MAX_N], e[MAX_M], w[MAX_M], ne[MAX_M]; // 鄰接表
int n = 6, m = 0, idx = 0; // n為節點數，m為邊數，idx為鄰接表中下一條邊的索引void add(int a, int b, int c)
{// 鄰接矩陣加邊g[a][b] = c;// 鄰接表加邊 (頭插法)e[idx] = b; // b表示當前邊的終點w[idx] = c; // c表示當前邊的權值ne[idx] = h[a]; // h[a]表示節點a的第一條邊在鄰接表中的位置，ne[idx]表示a節點的下一條邊在鄰接表中的位置h[a] = idx++; // 更新節點a的第一條邊的位置
}void init()
{// A B C D E F// 0 1 2 3 4 5// 初始化鄰接表的頭結點for (int i = 0; i < n; i++)h[i] = -1;// 加邊add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);
}void print()
{// 輸出鄰接矩陣cout << "輸出鄰接矩陣:" << endl;cout << "   A  B  C  D  E  F" << endl;char c = 'A';for (int i = 0; i < n; i++){cout << c++ << "  ";for (int j = 0; j < n; j++)printf("%-2d ",g[i][j]);
//          cout << g[i][j] << " ";cout << endl;}// 輸出鄰接表cout << "\n	輸出鄰接表:" << endl;for (int i = 0; i < n; i++){cout << (char)('A' + i); // 輸出當前節點的名稱int x = h[i]; // 獲取當前節點的第一條邊在鄰接表中的位置while (x != -1){cout << " --[" << w[x] << "]--> " << (char)('A' + e[x]); // 輸出當前邊的權值和終點x = ne[x]; // 移動到下一條邊}cout << endl;}
}int main()
{n = 6; // 設置節點數為6char nodes[] = { 'A', 'B', 'C', 'D', 'E', 'F' }; // 節點名稱init(); // 初始化圖print(); // 輸出鄰接矩陣和鄰接表return 0;
}

🍻 c 語言版

#include <stdio.h>#define MAX_N 6
#define MAX_M (6 * 5)int g[MAX_N][MAX_N]; // 鄰接矩陣
int h[MAX_N], e[MAX_M], w[MAX_M], ne[MAX_M]; // 鄰接表
int n = 6, m = 0, idx = 0; // n為節點數，m為邊數，idx為鄰接表中下一條邊的索引void add(int a, int b, int c)
{// 鄰接矩陣加邊g[a][b] = c;// 鄰接表加邊 (頭插法)e[idx] = b; // b表示當前邊的終點w[idx] = c; // c表示當前邊的權值ne[idx] = h[a]; // h[a]表示節點a的第一條邊在鄰接表中的位置，ne[idx]表示a節點的下一條邊在鄰接表中的位置h[a] = idx++; // 更新節點a的第一條邊的位置
}void init()
{// A B C D E F// 0 1 2 3 4 5// 初始化鄰接表的頭結點for (int i = 0; i < n; i++)h[i] = -1;// 加邊add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);
}void print()
{// 輸出鄰接矩陣printf("輸出鄰接矩陣:\n");printf("   A  B  C  D  E  F\n");char c = 'A';for (int i = 0; i < n; i++){printf("%c  ", c++);for (int j = 0; j < n; j++)printf("%-2d ", g[i][j]);printf("\n");}// 輸出鄰接表printf("\n	輸出鄰接表:\n");for (int i = 0; i < n; i++){printf("%c", (char)('A' + i)); // 輸出當前節點的名稱int x = h[i]; // 獲取當前節點的第一條邊在鄰接表中的位置while (x != -1){printf(" --[%d]--> %c", w[x], (char)('A' + e[x])); // 輸出當前邊的權值和終點x = ne[x]; // 移動到下一條邊}printf("\n");}
}int main()
{n = 6; // 設置節點數為6char nodes[] = { 'A', 'B', 'C', 'D', 'E', 'F' }; // 節點名稱init(); // 初始化圖print(); // 輸出鄰接矩陣和鄰接表return 0;
}

🍻 java版

package 數據結構實驗;public class 圖的創建和存儲
{static int[][] g;// （鄰接矩陣）static int n = 6, m = 6 * 5, idx = 0;static int[] h = new int[n];static int[] e = new int[m];static int[] w = new int[m];static int[] ne = new int[m];static void add(int a, int b, int c){
//		鄰接矩陣加邊g[a][b] = c;
//		鄰接表加邊 (頭插法)e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;}static void init(){
//		A B C D E F
//		0 1 2 3 4 5
//		初始化鄰接表的頭結點for (int i = 0; i < n; i++)h[i] = -1;//		加邊add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);}static void print(){
//		輸出鄰接矩陣System.out.println("輸出鄰接矩陣:");// 表頭System.out.println("   A  B  C  D  E  F");char c = 'A';for (int i = 0; i < n; i++){System.out.print(c++ + "  ");for (int j = 0; j < n; j++)System.out.printf("%-2d ", g[i][j]);System.out.println();}
//		輸出鄰接表System.out.println("\n輸出鄰接表:");for (int i = 0; i < n; i++){System.out.print((char) ('A' + i));int x = h[i];while (x != -1){System.out.print(" --" + w[x] + "--> " + (char) ('A' + e[x]));x = ne[x];}System.out.println();}}public static void main(String[] args){n = 6;char[] nodes = { 'A', 'B', 'C', 'D', 'E', 'F' };g = new int[n][n];init();print();}
}

四、【實驗結果】

五、【實驗總結】

balabala