《数据结构》课程设计 实验报告 题 目 图的基本操作及应用 学 院 商学院 专 业 信息管理与信息系统 班 级 信息101 学 号 201052275125 学生姓名 陈蒋昊 同组成员 楼炜 江舟 张垚跃 曹伟明 费泽融 杨钰琨 指导教师 刘小晶 编写日期 2012年6月29日 一、 问题描述：
图的基本操作及应用主要解决的问题包括，图的建立，图的存储结构，图的遍历（广度和深度优先搜索算法）和一些图的应用，如最小生成树，最短路径，关键路径等。本课程设计解决图的基本操作问题，此外还添加图的应用举例，最小生成树和最短路径。
二、 问题分析：
我所负责的是图的广度遍历。所以我先假设给定图G的初态是所有顶点均未曾访问过。在G中任选一顶点v为初始出发点(源点)，首先访问出发点v，并将其标记为已访问过，输入队列中；然后访问v的任意一个邻接点w1、w2、```。然后再按此顺序访问w1、w2、```的各个还未被访问过的邻接点。重复上述过程，直到图中所有的点都被访问过为止。也就是说广度优先遍历是一种分层的搜索过程，每向前走一步就可能访问一批定点。并且该遍历不是一个递归的过程。
三、 数据结构描述：
图的存储结构我这次选择的是邻接矩阵，用来表示顶点之间的相邻关系。
四、 算法设计:
我负责的是图问题中的深度遍历。
开始在已建好的图中输入数据广度优先遍历队列将输入队列并输出找出v的所有邻接点w1、w2···wn。Wn是否被访问输出广度遍历顺序Y结束N
2、具体算法
package javaapplication1;
//用于实现广度优先搜索的队列类 class Queue {
private final int SIZE=20; private int[] queArray; private int front; private int rear; public Queue(){
queArray=new int[SIZE]; front=0; rear=-1; }
public void insert(int j){ if(rear==SIZE-1) rear=-1;
queArray[++rear]=j; }
public int remove(){
int temp=queArray[front++]; if(front==SIZE) front=0; return temp; }
public boolean isEmpty(){
return ((rear+1==front)||(front+SIZE-1==rear)); } }
package javaapplication1; //图类
class Graph {
private final int MAX_VERTS=20; private Vertex vertexList[]; private int adjMat[][]; private int nVerts;
private StackX theStack; private Queue theQueue;
public Graph() {
vertexList=new Vertex[MAX_VERTS];
adjMat=new int[MAX_VERTS][MAX_VERTS]; nVerts=0;
for (int j = 0; j < MAX_VERTS; j++){
for (int k = 0; k < MAX_VERTS; k++) { adjMat[j][k]=0; } }
theStack=new StackX(); theQueue=new Queue(); }
//增加一个顶点
public void addVertex(char lab){
vertexList[nVerts++]=new Vertex(lab); }
//增加一条边
public void addEdge(int start,int end){ adjMat[start][end]=1; adjMat[end][start]=1; }
public void displayVertex(int v){
System.out.print(vertexList[v].label+\ }
public void showGraphyMatrix(){ for(int i=0;i<5;i++){ for(int j=0;j<5;j++)
System.out.print(adjMat[i][j]); System.out.println(); } }
//得到与v顶点邻接且未访问过的顶点标号
public int getAdjUnvisitedVertex(int v){ for (int j = 0; j < nVerts; j++) {
if(adjMat[v][j]==1&&vertexList[j].wasVisited==false) return j; }
return -1; }
//广度优先搜索 public void bfs(){
vertexList[0].wasVisited=true; displayVertex(0);
theQueue.insert(0); int v2;
while(!theQueue.isEmpty()){ int v1=theQueue.remove();
while((v2=getAdjUnvisitedVertex(v1))!=-1){ vertexList[v2].wasVisited=true; displayVertex(v2); theQueue.insert(v2); } }
for (int j = 0; j < nVerts; j++) {
vertexList[j].wasVisited=false; } } }
package javaapplication1; //TEST类
import java.util.Scanner;
public class TEST {
public final static int INFINITY = Integer.MAX_VALUE; static final int maxVertices = 100;
static Character[] a = {new Character('A'), new Character('B'), new Character('C'), new Character('D'),
new Character('E'), new Character('F'), new Character('G'), new Character('H')};
public static void createGraph(AdjMWGraph g, Object[] v, int n, RowColWeight[] rc, int e) throws Exception {
for (int i = 0; i < n; i++) { g.insertVertex(v[i]); }
for (int k = 0; k < e; k++) {
g.insertEdge(rc[k].row, rc[k].col, rc[k].weight); } }
public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); Graph b = new Graph();
AdjMWGraph g = new AdjMWGraph(maxVertices); while (true) {
System.out.println(\0--建图 1--深度优先遍历 2--广度优先遍历 3--最小生成树 4--图的的最短路径 5--关键路径 6--退出\