图的基本运算
[问题描述]
对给定图，实现图的深度优先遍历和广度优先遍历。
[基本要求]
以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
实验内容
public partial class Form1 : Form
{
public Form1()
{
InitializeComponent();
}
const int IMAXVF = 32767; //用作表示∞
const int MAXV = 10; //图最多为10个顶点
int[,] a = new int[MAXV, MAXV];
int ns; //图的顶点个数
int es; //图的边数
public TextBox[,] edge = new TextBox[MAXV, MAXV];
public Label[] hlabel = new Label[MAXV];
public Label[] vlabel = new Label[MAXV];
private void Dispgraph() //初始时屏幕上对象布局
{
int ix = 40, iy = 120, i, j, x, y; //(x,y)为每个方块左上角坐标
x = ix + 30; y = iy;
numericUpDown1.Value = ns;
Size s = new Size(30, 30);
for (i = 0; i < MAXV; i++) //显示第一行的标签
{
hlabel[i] = new Label();
hlabel[i].Left = x;
hlabel[i].Top = y;
hlabel[i].Size = s;
hlabel[i].Font = new Font("Arial", 11, FontStyle.Bold);
hlabel[i].Text = i.ToString();
hlabel[i].ForeColor = Color.Blue;
x += 31;
this.Controls.Add(hlabel[i]);
}
x = ix; y = iy + 30;
for (j = 0; j < MAXV; j++) //显示第一列的标签
{
vlabel[j] = new Label();
vlabel[j].Left = x;
vlabel[j].Top = y;
vlabel[j].Size = s;
vlabel[j].Font = new Font("Arial", 11, FontStyle.Bold);
vlabel[j].Text = j.ToString();
vlabel[j].ForeColor = Color.Blue;
y += 31;
this.Controls.Add(vlabel[j]);
}
x = ix + 30; y = iy + 30;
for (i = 0; i < MAXV; i++)
{
for (j = 0; j < MAXV; j++)
{
edge[i, j] = new TextBox();
edge[i, j].Left = x;
edge[i, j].Top = y;
edge[i, j].Size = s;
edge[i, j].Font = new Font("Arial", 12, FontStyle.Bold);
if (a[i, j] == IMAXVF)
edge[i, j].Text = "∞";
else
edge[i, j].Text = a[i, j].ToString();
if (i == j)
{
edge[i, j].Enabled = false;
edge[i, j].BackColor = System.Drawing.Color.Cyan;
}
this.Controls.Add(edge[i, j]);
x += 30;
}
x = ix + 30;
y += 30;
}
for (i = 0; i < ns; i++)
for (j = i + 1; j < ns; j++)
edge[i, j].Visible = false;
}
private void ReDispgraph() //用户修改时重新显示一个图
{
int i, j;
for (i = 0; i < MAXV; i++)
hlabel[i].Visible = false;
for (i = 0; i < ns; i++)
hlabel[i].Visible = true;
for (i = 0; i < MAXV; i++)
vlabel[i].Visible = false;
for (i = 0; i < ns; i++)
vlabel[i].Visible = true;
for (i = 0; i < MAXV; i++)
for (j = 0; j < MAXV; j++)
edge[i, j].Visible = false;
for (i = 0; i < ns; i++)
for (j = 0; j < ns; j++)
{
if (a[i, j] == IMAXVF)
edge[i, j].Text = "∞";
else
edge[i, j].Text = a[i, j].ToString();
edge[i, j].Visible = true;
}
for (i = 0; i < ns; i++)
for (j = i + 1; j < ns; j++)
edge[i, j].Visible = false;
}
private void Form1_Load(object sender, EventArgs e)
{
ns = 10; es = 11; //默认的图设置
a = new int[,] {
{ 0, 1, 1, 1, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 1, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 1, 0, 0, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 1, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 1, 0, 0, 0, 1 },
{ 0, 0, 0, 0, 0, 0, 0, 1, 1, 0 }};
Dispgraph();
}
Class1 C = new Class1();
private void button1_Click(object sender, EventArgs e)
{
int i, j;
for (i = 0; i < ns; i++) //求出新的a数组值
for (j = 0; j < ns; j++)
if (edge[i, j].Text == "∞")
a[i, j] = IMAXVF;
else
a[i, j] = Convert.ToInt16(edge[i, j].Text);
es = 0;
for (i = 0; i < ns; i++) //复制下三角部分到上三角部分
for (j = i; j < ns; j++)
{
a[i, j] = a[j, i];
if (a[i, j] > 0)
es++;
}
if(C.CreateALGraph(a,ns,es))
{
MessageBox.Show("创建成功");
}
else
{
MessageBox.Show("创建失败");
}
}
private void button2_Click(object sender, EventArgs e)
{
textBox1.Text = C.DFS(int.Parse(textBox3.Text));
textBox2.Text = C.BFS(int.Parse(textBox3.Text));
}
private void button3_Click(object sender, EventArgs e)
{
ns = int.Parse(numericUpDown1.Value.ToString()); //新的顶点数
if (ns < 3 || ns > 10)
{
MessageBox.Show("操作提示:顶点数必须为3～10之间的数");
return;
}
ReDispgraph();
}
}
class ArcNode //边结点类型
{
public int adjvex; //该边的终点编号
public ArcNode nextarc; //指向下一条边的指针
public int weight; //该边的相关信息,如边的权值
}
struct VNode //表头结点类型
{
public string data; //顶点信息
public ArcNode firstarc; //指向第一条边
}
struct ALGraph //图的邻接表类型
{
public VNode[] adjlist; //邻接表数组
public int n, e; //图中顶点数n和边数e
}
class Class1
{ const int MAXV = 10; //最大顶点个数
const int INF = 32767; //用INF表示∞
public ALGraph G = new ALGraph();
string gstr;
int[] visited = new int[MAXV]; //顶点的访问标识数组
public Class1() //构造函数
{
G.adjlist = new VNode[MAXV];
}
public bool CreateALGraph(int[,]a1,int ns1,int es1) //创建图邻接表G
{
int i, j;
int[,] a = a1;
int ns=ns1; //图的顶点个数
int es=es1; //图的边数
ArcNode p;
for (i = 0; i < ns; i++) //给邻接表中所有头结点的指针域置初值
G.adjlist[i].firstarc = null;
for (i = 0; i < ns; i++) //检查邻接矩阵中每个元素
for (j = ns - 1; j >= 0; j--)
if (a[i, j] != 0 && a[i, j] != INF) //存在一条边
{
p = new ArcNode(); //创建一个结点p
p.adjvex = j;
p.weight = a[i, j]; //边的权值
p.nextarc = G.adjlist[i].firstarc; //采用头插法插入p
G.adjlist[i].firstarc = p;
}
G.n = ns;
G.e = es;
return true;
}
public string DFS(int v) //图的深度优先遍历
{
int i;
for (i = 0; i < G.n; i++)
visited[i] = 0;
gstr = "";
DFS1(v);
return gstr;
}
void DFS1(int v) //被DFS调用进行深度优先遍历
{
ArcNode p;
int w;
visited[v] = 1; //置已访问标记
gstr += v.ToString() + " "; //输出被访问顶点的编号
p = G.adjlist[v].firstarc; //p指向顶点v的第一个邻接点
while (p != null)
{
w = p.adjvex;
if (visited[w] == 0) //若w顶点未访问,递归访问它
DFS1(w);
p = p.nextarc; //p指向顶点v的下一个邻接点
}
}
public string BFS(int v) //图的广度优先遍历
{
ArcNode p;
int[] qu = new int[MAXV];
int front = 0, rear = 0; //定义循环队列并初始化队头队尾
int[] visited = new int[MAXV]; //定义存放顶点的访问标志的数组
int w, i;
for (i = 0; i < G.n; i++)
visited[i] = 0; //访问标志数组初始化
gstr = "";
gstr += v.ToString() + " "; //输出被访问顶点的编号
visited[v] = 1; //置已访问标记
rear = (rear + 1) % MAXV;
qu[rear] = v; //v进队
while (front != rear) //若队列不空时循环
{
front = (front + 1) % MAXV;
w = qu[front]; //出队并赋给w
p = G.adjlist[w].firstarc; //找与顶点w邻接的第一个顶点
while (p != null)
{
if (visited[p.adjvex] == 0) //若当前邻接顶点未被访问
{
gstr += p.adjvex.ToString() + " "; //访问相邻顶点
visited[p.adjvex] = 1; //置该顶点已被访问的标志
rear = (rear + 1) % MAXV; //该顶点进队
qu[rear] = p.adjvex;
}
p = p.nextarc; //找下一个邻接顶点
}
}
return gstr;
}
}
}
运行结果如下图：