program.cs

此程序可实现一定的功能

using System;
using System.IO;
using System.Diagnostics;
using System.Collections.Generic;
using System.Text;

namespace MyGraph
{    
    class Program
    {
//从图gra的指定节点vtx开始进行DFS遍历，输出为outputlist，是节点链表
        static void DFS(Graph gra,LinkedListNode<Vertex> vtx,int[]visited,Queue<int> outputlist)
        {
            int i = vtx.Value.vtx;
            visited[i-1] = 1;
            outputlist.Enqueue(i);
            LinkedListNode<EdgeLink> tempEdge = vtx.Value.list.First;
            LinkedListNode<Vertex> tempVtx;
            while(tempEdge!=null)
            {
                i=tempEdge.Value.destVtx;
                if(visited[i-1]==0)
                {
                    tempVtx = gra.FindVetex(i);
                    DFS(gra,tempVtx,visited,outputlist);
                }
                tempEdge = tempEdge.Next;
            }
        }
//对图gra从节点链表第一个节点开始进行DFS遍历，输出为outputlist，是节点链表
        static void GraphDFS(Graph gra,Queue<int> outputlist)
        {
            
            int i = gra.VertexList.Count;
            int []visted=new int[i];
            while (i > 0)
            {
                visted[i - 1] = 0;
                i--;
            }
            LinkedListNode<Vertex> tempVtx = gra.VertexList.First;
            while (tempVtx != null)
            {
                i = tempVtx.Value.vtx;
                if (visted[i-1] == 0)
                {
                    DFS(gra, tempVtx, visted, outputlist);
                }
                tempVtx = tempVtx.Next;
            }
        }
//对图gra从vtx节点，进行DFS遍历，输出为endgelist，是遍历所经过边的链表
        static void DFSToEdgelist(Graph gra, LinkedListNode<Vertex> vtx, int[] visited, Queue<Edge> edgelist)
        {
            int i = vtx.Value.vtx;
            visited[i-1] = 1;
      
            LinkedListNode<EdgeLink> tempEdge = vtx.Value.list.First;
            LinkedListNode<Vertex> tempVtx;
            Edge temp;
            while (tempEdge != null)
            {
                i = tempEdge.Value.destVtx;
                if (visited[i-1] == 0)
                {
                    tempVtx = gra.FindVetex(i);
                    temp = new Edge(vtx.Value.vtx,i);
                    edgelist.Enqueue(temp);
                    DFSToEdgelist(gra, tempVtx, visited, edgelist);
                }
                tempEdge = tempEdge.Next;
            }
        }
//对图gra进行BFS遍历，输出为endgelist，是遍历所经过边的链表
        static void GraphDFSToEdgelist(Graph gra, Queue<Edge> edgelist)
        {
            int i = gra.VertexList.Count;
            int[] visted = new int[i];
            while (i > 0)
            {
                visted[i - 1] = 0;
                i--;
            }
            LinkedListNode<Vertex> tempVtx = gra.VertexList.First;
            while (tempVtx != null)
            {
                i = tempVtx.Value.vtx;
                if (visted[i-1] == 0)
                {
                    DFSToEdgelist(gra, tempVtx, visted, edgelist);
                }
                tempVtx = tempVtx.Next;
            }
        }
 //从图gra的指定节点vtx开始进行BFS遍历，输出为outputlist，是节点链表
        static void BFS(Graph gra, LinkedListNode<Vertex> vtx, int[] visited, Queue<int> outputlist)
        {
            LinkedListNode<EdgeLink> tempEdge = vtx.Value.list.First;
            LinkedListNode<Vertex> tempVtx;
            int i;
            Queue<int> q=new Queue<int>();
            while (tempEdge != null)
            {
                i = tempEdge.Value.destVtx;
                if (visited[i-1] == 0)
                {
                    q.Enqueue(i);
                    outputlist.Enqueue(i);
                    visited[i-1] = 1;
                }
                tempEdge = tempEdge.Next;
            }
            while (q.Count != 0)
            {
                i = q.Dequeue();
                tempVtx = gra.FindVetex(i);
                BFS(gra,tempVtx,visited,outputlist);
            }
        }
//对图gra从节点链表第一个节点开始进行BFS遍历，输出为outputlist，是节点链表
        static void GraphBFS(Graph gra,Queue<int> outputlist)
        {
            int i = gra.VertexList.Count;
            int []visited=new int[i];
            while( i > 0 )
            {
                visited[i - 1] = 0;
                i--;
            }
            LinkedListNode<Vertex> tempVtx = gra.VertexList.First;
            while (tempVtx != null)
            {
                i = tempVtx.Value.vtx;
                if (visited[i - 1] == 0)
                {
                    outputlist.Enqueue(tempVtx.Value.vtx);
                    visited[tempVtx.Value.vtx - 1] = 1;
                    BFS(gra, tempVtx, visited, outputlist);
                }
                tempVtx = tempVtx.Next;
            }


        }
//对图gra从vtx节点，进行BFS遍历，输出为endgelist，是遍历所经过边的链表
        static void BFSToEdgelist(Graph gra, LinkedListNode<Vertex> vtx, int[] visited, Queue<Edge> edgelist)
        {
            LinkedListNode<EdgeLink> tempEdge = vtx.Value.list.First;
            LinkedListNode<Vertex> tempVtx;
            Edge temp;
            int i;
            Queue<int> q = new Queue<int>();
            while (tempEdge != null)
            {
                i = tempEdge.Value.destVtx;
                if (visited[i-1] == 0)
                {
                    q.Enqueue(i);
                    temp = new Edge(vtx.Value.vtx,i);
                    edgelist.Enqueue(temp);
                    visited[i - 1] = 1;
                }
                tempEdge = tempEdge.Next;
            }
            while (q.Count != 0)
            {
                i = q.Dequeue();
                tempVtx = gra.FindVetex(i);
                BFSToEdgelist(gra, tempVtx, visited, edgelist);
            }
        }
//对图gra进行BFS遍历，输出为endgelist，是遍历所经过边的链表
        static void GraphBFSToEdgelist(Graph gra, Queue<Edge> edgelist)
        {
            int i = gra.VertexList.Count;
            int[] visited = new int[i];
            while (i > 0)
            {
                visited[i - 1] = 0;
                i--;
            }
            LinkedListNode<Vertex> tempVtx = gra.VertexList.First;
            while (tempVtx != null)
            {
                i = tempVtx.Value.vtx;
                if (visited[i-1] == 0)
                {
                    visited[tempVtx.Value.vtx-1] = 1;
                    BFSToEdgelist(gra, tempVtx, visited, edgelist);
                }
                tempVtx = tempVtx.Next;
            }
        }
//将遍历输出的边的链表转换成string，用来生成dot文件
        static string EdgelistToStr(Queue<Edge> edgelist)
        {
            string s = "digraph g{\n";
            s += "\tsize = \"10, 10\";\n";
            s += "\tnode [color=lightblue2, style=filled];\n";
            string temp1 = "\"";
            string temp2 = "->";
            string temp3 = ";\n";
            Edge tempEdge;
            while (edgelist.Count > 0)
            {
         //       Console.WriteLine("{0}",edgelist.Count);
                tempEdge = edgelist.Dequeue();
                s += temp1;
                s += tempEdge.from;
                s += temp1;
                s += temp2;
                s += temp1;
                s += tempEdge.to;
                s += temp1;
                s += temp3;
            }
            s += "}\n\n";
            return s;
        }
        static void EdgelistToJpg(Queue<Edge> edgelist,string name)
        {
            string strname = "";
            strname += name;
            string dotname = "";
            dotname += name;
            dotname += ".dot";
            string jpgname = "";
            jpgname += name;
            jpgname += ".jpg";
         //   string dotname2 = "c:\\" + dotname;
            string dotname2 = dotname;
            StreamWriter fp;
            fp = File.CreateText(dotname2);            
            string str = EdgelistToStr(edgelist);
            fp.WriteLine(str);
            fp.Close();

            string command = "dot -Tjpg -o ";
            command += jpgname;
            command += " ";
            command += dotname;

            Process p = new Process();
            p.StartInfo.FileName = "cmd.exe";

            
            // 关闭Shell的使用
            p.StartInfo.UseShellExecute = false;
            // 重定向标准输入
            p.StartInfo.RedirectStandardInput = true;
            // 重定向标准输出
            p.StartInfo.RedirectStandardOutput = true;
            //重定向错误输出
            p.StartInfo.RedirectStandardError = true;
            // 设置不显示窗口
            p.StartInfo.CreateNoWindow = true;

          
            p.Start();
            p.StandardInput.WriteLine(command);
            p.StandardInput.WriteLine("exit");
            p.StandardOutput.ReadToEnd();
            p.Close();

        }
        static void Main(string[] args)
        {


            Graph mygraph = new Graph();
            for (int i = 0; i < 5; i++)
            {
                mygraph.InsertVertex(i + 1);
            }
            mygraph.InsertEdge(1, 2);
            mygraph.InsertEdge(1, 3);
            mygraph.InsertEdge(2, 4);
            mygraph.InsertEdge(4, 3);
            mygraph.InsertEdge(1, 5);
            mygraph.InsertEdge(4, 5);
            Queue<Edge> edgelist = new Queue<Edge>();    
            GraphBFSToEdgelist(mygraph,edgelist);  
            string name = "Graph";
            mygraph.GraphToJPG(name);
            name = "BFSTree";
            EdgelistToJpg(edgelist,name);
            name = "DFSTree";
            edgelist.Clear();
            GraphDFSToEdgelist(mygraph,edgelist);
            EdgelistToJpg(edgelist,name);
 
            Tree mytree = new Tree();
            mytree.Insert(1, 2);
            mytree.Insert(1, 3);
            mytree.Insert(1, 4);
            mytree.Insert(2, 7);
            mytree.Insert(3, 5);
            mytree.Insert(4, 6);
            mytree.Insert(2, 8);
            mytree.TreeToJPG("mytree");
            LinkedList<int> output = new LinkedList<int>();
            LinkedListNode<Vertex> root = mytree.VtxList.First;
            mytree.PreOrder(root, output);
            mytree.OutputToJPG("preorder", output);
            output.Clear();
            mytree.InOrder(root, output);
            mytree.OutputToJPG("inorder", output);
            output.Clear();
            mytree.PostOrder(root, output);
            mytree.OutputToJPG("postorder", output);
            output.Clear();
            mytree.LevelOrder(output);
            mytree.OutputToJPG("leverorder", output);
        }
    }
}