数据结构 图

一个图是由顶点，和边集E组成的。

无向图，有向图 

若图中所有的便有两个顶点没有次序关系和方向，即（V1,V2）和V(V2,V1)代表同一个便，则称为无向图，反之则为有向图。

 

完全图 

在一个无向图中，如果任意两顶点都有一条边直接连接，则称该图为完全无向图。

路径

路径是指图中顶点的序列

回路

回路是指在有向图中路径至少为1一边初始顶点也是结束顶点。在有向图中，变可能相同，但在无向图中，边必须相同。

 

顶点的表示 

 public class Vertex

{

    public bool wasVisited;

    public string label;

    public Vertex(string label)

    {

        this.label = label;

        wasVisited = false;

    }

}

 

图的构造 

 

下边是4个顶点的图

int nVertices = 0;

vertices[nVertices] = new Vertex("A");

nVertices++;

vertices[nVertices] = new Vertex("B");

nVertices++;

vertices[nVertices] = new Vertex("C");

nVertices++;

vertices[nVertices] = new Vertex("D");

 

软后需要添加顶点的边

 

 

adjMatrix[0,1] = 1;

adjMatrix[1,0] = 1;

adjMatrix[1,3] = 1;

adjMatrix[3,1] = 1;

 

初步构造

public class Vertex

{

    public bool wasVisited;

    public string label;

    public Vertex(string label)

    {

        this.label = label;

        wasVisited = false;

    }

}

public class Graph

{

    private int NUM_VERTICES = 6;

    private Vertex[] vertices;

    private int[,] adjMatrix;

    int numVerts;

    public Graph(int numvertices)

    {

        NUM_VERTICES = numvertices;

        vertices = new Vertex[NUM_VERTICES];

        adjMatrix = new int[NUM_VERTICES, NUM_VERTICES];

        numVerts = 0;

        for (int j = 0; j <= NUM_VERTICES -1; j++)

            for (int k = 0; k <= NUM_VERTICES - 1; k++)

                adjMatrix[j, k] = 0;

    }

    public void AddVertex(string label)

    {

        vertices[numVerts] = new Vertex(label);

        numVerts++;

    }

    public void AddEdge(int start, int eend)

    {

        adjMatrix[start, eend] = 1;

    }

    public void ShowVertex(int v)

    {

        Console.Write(vertices[v].label + " ");

}

}

图的应用 

 

拓扑排序 会把有向图的顶点序列按照指定顺序显示出来。

拓扑排序的算法

1 找到一个没有后继顶点的顶点。

2 把此顶点添加到顶点列表

3从图中移除此顶点。

4重复步骤1直到吧所有顶点移除

 

public int NoSuccessors()  // 找后继顶点 

{

    bool isEdge;

    for (int row = 0; row <= NUM_VERTICES - 1; row++)

    {

        isEdge = false;

        for (int col = 0; col <= NUM_VERTICES - 1; col++)

        {

            if (adjMatrix[row, col] > 0)

            {

                isEdge = true;

                break;

            }

        }

        if (!isEdge)

            return row;

    }

    return -1;

}

 

    public void DelVertex(int vert) // 删除顶点

    {

        if (vert != NUM_VERTICES - 1)

        {

            for (int j = vert; j < NUM_VERTICES - 1; j++)

                vertices[j] = vertices[j + 1];

            for (int row = vert; row < NUM_VERTICES - 1; row++)

                MoveRow(row, NUM_VERTICES);

            for (int col = vert; col < NUM_VERTICES - 1; col++)

                MoveCol(col, NUM_VERTICES);

        }

        NUM_VERTICES--;

    }

    private void MoveRow(int row, int length)

    {

        for (int col = 0; col <= length - 1; col++)

            adjMatrix[row, col] = adjMatrix[row + 1, col];

    }

    private void MoveCol(int col, int length)

    {

        for (int row = 0; row <= length - 1; row++)

            adjMatrix[row, col] = adjMatrix[row, col + 1];

}

 

public void TopSort()  // 排序

{

    Stack<string> gStack = new Stack<string>();

    while (NUM_VERTICES > 0)

    {

        int currVertex = NoSuccessors();

        if (currVertex == -1)

        {

            Console.WriteLine("Error: graph has cycles.");

            return;

        }

        gStack.Push(vertices[currVertex].label);

        DelVertex(currVertex);

    }

    Console.Write("Topological sorting order: ");

    while (gStack.Count > 0)

        Console.Write(gStack.Pop() + " ");

}

 

static void Main(string[] args)

{

    Graph theGraph = new Graph(4);

    theGraph.AddVertex("A");

    theGraph.AddVertex("B");

    theGraph.AddVertex("C");

    theGraph.AddVertex("D");

    theGraph.AddEdge(0, 1);

    theGraph.AddEdge(1, 2);

    theGraph.AddEdge(2, 3);

    theGraph.TopSort();

    Console.WriteLine();

Console.WriteLine("Finished.");

}

 

图的搜索 

 

深度优先搜索的含义是沿着一条路从开始顶点到达最后顶点，然后原路返回，并且沿着下一条路径到达最后的顶点。.如此反复直到走过所有路径。

 

 

private int GetAdjUnvisitedVertex(int v) // 未访问的路径的方法

{

    for (int j = 0; j <= NUM_VERTICES - 1; j++)

        if ( (adjMatrix[v,j] == 1) && (vertices[j].wasVisited  == false))

        return j;

    return -1;

}

 

 

public void DepthFirstSearch()

{

    Stack<int> gStack = new Stack<int>();

    vertices[0].wasVisited = true;

    ShowVertex(0);

    gStack.Push(0);

    int v;

    while (gStack.Count > 0)

    {

        v = GetAdjUnvisitedVertex(gStack.Peek());

        if (v == -1)

           gStack.Pop();

        else

        {

            vertices[v].wasVisited = true;

            ShowVertex(v);

            gStack.Push(v);

        }

    }

    for (int j = 0; j <= NUM_VERTICES - 1; j++)

        vertices[j].wasVisited = false;

}

 

 

static void Main(string[] args)

{

    Graph aGraph = new Graph(13);

    aGraph.AddVertex("A");

    aGraph.AddVertex("B");

    aGraph.AddVertex("C");

    aGraph.AddVertex("D");

    aGraph.AddVertex("E");

    aGraph.AddVertex("F");

    aGraph.AddVertex("G");

    aGraph.AddVertex("H");

    aGraph.AddVertex("I");

    aGraph.AddVertex("J");

    aGraph.AddVertex("K");

    aGraph.AddVertex("L");

    aGraph.AddVertex("M");

    aGraph.AddEdge(0, 1);

    aGraph.AddEdge(1, 2);

    aGraph.AddEdge(2, 3);

    aGraph.AddEdge(0, 4);

    aGraph.AddEdge(4, 5);

    aGraph.AddEdge(5, 6);

    aGraph.AddEdge(0, 7);

    aGraph.AddEdge(7, 8);

    aGraph.AddEdge(8, 9);

    aGraph.AddEdge(0, 10);

    aGraph.AddEdge(10, 11);

    aGraph.AddEdge(11, 12);

    aGraph.DepthFirstSearch();

    Console.WriteLine();

}

 

 

广度优先搜索 

 

算法 

1 找到一个与当前顶点相邻的未访问过的顶点，把它标记为已访问，然后把它标记已访问，然后把它添加到队列中。

2 如果找不到一个未访问过的相邻顶点，那么从队列中移除一个顶点（如果队列中有可以移除），把它作为当前顶点，然后重新开始。

3 如果由于队列为空而无法执行2操作，那么算法结束。

 

public void BreadthFirstSearch()

{

    Queue<int> gQueue = new Queue<int>();

    vertices[0].wasVisited = true;

    ShowVertex(0);

    gQueue.Enqueue(0);

    int vert1, vert2;

    while (gQueue.Count > 0)

    {

        vert1 = gQueue.Dequeue();

        vert2 = GetAdjUnvisitedVertex(vert1);

        while (vert2 != -1)

        {

            vertices[vert2].wasVisited = true;

            ShowVertex(vert2);

            gQueue.Enqueue(vert2);

            vert2 = GetAdjUnvisitedVertex(vert1);

        }

    }

    for (int i = 0; i <= NUM_VERTICES - 1; i++)

        vertices[i].wasVisited = false;

}

 

static void Main(string[] args)

{

    Graph aGraph = new Graph(13);

    aGraph.AddVertex("A");

    aGraph.AddVertex("B");

    aGraph.AddVertex("C");

    aGraph.AddVertex("D");

    aGraph.AddVertex("E");

    aGraph.AddVertex("F");

    aGraph.AddVertex("G");

    aGraph.AddVertex("H");

    aGraph.AddVertex("I");

    aGraph.AddVertex("J");

    aGraph.AddVertex("K");

    aGraph.AddVertex("L");

    aGraph.AddVertex("M");

    aGraph.AddEdge(0, 1);

    aGraph.AddEdge(1, 2);

    aGraph.AddEdge(2, 3);

    aGraph.AddEdge(0, 4);

    aGraph.AddEdge(4, 5);

    aGraph.AddEdge(5, 6);

    aGraph.AddEdge(0, 7);

    aGraph.AddEdge(7, 8);

    aGraph.AddEdge(8, 9);

    aGraph.AddEdge(0, 10);

    aGraph.AddEdge(10, 11);

    aGraph.AddEdge(11, 12);

    Console.WriteLine();

    aGraph.BreadthFirstSearch();

}

 

最小生成树

 

最小生成树即找连接数量最小值。

public void Mst()

{

    Stack<int> gStack = new Stack<int>();

    vertices[0].wasVisited = true;

    gStack.Push(0);

    int currVertex, ver;

    while (gStack.Count > 0)

    {

        currVertex = gStack.Peek();

        ver = GetAdjUnvisitedVertex(currVertex);

        if (ver == -1)

            gStack.Pop();

        else

        {

            vertices[ver].wasVisited = true;

            gStack.Push(ver);

            ShowVertex(currVertex);

            ShowVertex(ver);

            Console.Write(" ");

        }

    }

    for (int j = 0; j <= NUM_VERTICES - 1; j++)

        vertices[j].wasVisited = false;

}

对比代码发现，最小生成树代码和调用    ShowVertex(currVertex); 方法记录当前节点，    ShowVertex(ver);记录下节点。两次调用这个方法就产生了最小生成树的显示。

 

查找最短路径

 

确定最短路径的Dijkstra 算法

通过创建一张表来存储途中从起始顶点到其他顶点的一直距离就可以实用Dijkstra 算法。

 

public class Vertex

{

    public string label;

    public bool isInTree;

    public Vertex(string lab)

    {

        label = lab;

        isInTree = false;

    }

}

public class DistOriginal  // 记录起始顶点和远距离顶点的关系。

{

    public int distance;

    public int parentVert;

    public DistOriginal(int pv, int d)

    {

        distance = d;

        parentVert = pv;

    }

}

 

public void Path()  //最短路径计算

{

    int startTree = 0;

    vertexList[startTree].isInTree = true;

    nTree = 1;

    for (int j = 0; j <= nVerts; j++)

    {

        int tempDist = adjMat[startTree, j];

        sPath[j] = new DistOriginal(startTree, tempDist);

    }

    while (nTree < nVerts)

    {

        int indexMin = GetMin();

        int minDist = sPath[indexMin].distance;

        currentVert = indexMin;

        startToCurrent = sPath[indexMin].distance;

        vertexList[currentVert].isInTree = true;

        nTree++;

        AdjustShortPath();

    }

    DisplayPaths();

    nTree = 0;

    for (int j = 0; j <= nVerts - 1; j++)

        vertexList[j].isInTree = false;

}

 

public int GetMin()

{

    int minDist = infinity;

    int indexMin = 0;

    for (int j = 1; j <= nVerts - 1; j++)

        if (!(vertexList[j].isInTree) && sPath[j].distance < minDist)

        {

            minDist = sPath[j].distance;

            indexMin = j;

        }

    return indexMin;

}

public void AdjustShortPath()

{

    int column = 1;

    while (column < nVerts)

        if (vertexList[column].isInTree)

            column++;

        else

        {

            int currentToFring = adjMat[currentVert, column];

            int startToFringe = startToCurrent + currentToFring;

            int sPathDist = sPath[column].distance;

            if (startToFringe < sPathDist)

            {

                sPath[column].parentVert = currentVert;

                sPath[column].distance = startToFringe;

            }

            column++;

        }

}

using System;

using System.Collections.Generic;

public class DistOriginal

{

    public int distance;

    public int parentVert;

    public DistOriginal(int pv, int d)

    {

        distance = d;

        parentVert = pv;

    }

}

public class Vertex

{

    public string label;

    public bool isInTree;

    public Vertex(string lab)

    {

        label = lab;

        isInTree = false;

    }

}

public class Graph

{

    private const int max_verts = 20;

    int infinity = 1000000;

    Vertex[] vertexList;

    int[,] adjMat;

    int nVerts;

    int nTree;

    DistOriginal[] sPath;

    int currentVert;

    int startToCurrent;

    public Graph()

    {

        vertexList = new Vertex[max_verts];

        adjMat = new int[max_verts, max_verts];

        nVerts = 0;

        nTree = 0;

        for (int j = 0; j <= max_verts - 1; j++)

            for (int k = 0; k <= max_verts - 1; k++)

                adjMat[j, k] = infinity;

        sPath = new DistOriginal[max_verts];

    }

    public void AddVertex(string lab)

    {

        vertexList[nVerts] = new Vertex(lab);

        nVerts++;

    }

    public void AddEdge(int start, int theEnd, int weight)

    {

        adjMat[start, theEnd] = weight;

    }

    public void Path()

    {

        int startTree = 0;

        vertexList[startTree].isInTree = true;

        nTree = 1;

        for (int j = 0; j <= nVerts; j++)

        {

            int tempDist = adjMat[startTree, j];

            sPath[j] = new DistOriginal(startTree, tempDist);

        }

        while (nTree < nVerts)

        {

            int indexMin = GetMin();

            int minDist = sPath[indexMin].distance;

            currentVert = indexMin;

            startToCurrent = sPath[indexMin].distance;

            vertexList[currentVert].isInTree = true;

            nTree++;

            AdjustShortPath();

        }

        DisplayPaths();

        nTree = 0;

        for (int j = 0; j <= nVerts - 1; j++)

            vertexList[j].isInTree = false;

    }

    public int GetMin()

    {

        int minDist = infinity;

        int indexMin = 0;

        for (int j = 1; j <= nVerts - 1; j++)

            if (!(vertexList[j].isInTree) && sPath[j].distance < minDist)

            {

                minDist = sPath[j].distance;

                indexMin = j;

            }

        return indexMin;

    }

    public void AdjustShortPath()

    {

        int column = 1;

        while (column < nVerts)

            if (vertexList[column].isInTree)

                column++;

            else

            {

                int currentToFring = adjMat[currentVert, column];

                int startToFringe = startToCurrent + currentToFring;

                int sPathDist = sPath[column].distance;

                if (startToFringe < sPathDist)

                {

                    sPath[column].parentVert = currentVert;

                    sPath[column].distance = startToFringe;

                }

                column++;

            }

    }

    public void DisplayPaths()

    {

        for (int j = 0; j <= nVerts - 1; j++)

        {

            Console.Write(vertexList[j].label + "=");

            if (sPath[j].distance == infinity)

                Console.Write("inf");

            else

                Console.Write(sPath[j].distance);

            string parent = vertexList[sPath[j].parentVert].

            label;

            Console.Write("(" + parent + ") ");

        }

    }

    class chapter16

    {

        static void Main()

        {

            Graph theGraph = new Graph();

            theGraph.AddVertex("A");

            theGraph.AddVertex("B");

            theGraph.AddVertex("C");

            theGraph.AddVertex("D");

            theGraph.AddVertex("E");

            theGraph.AddVertex("F");

            theGraph.AddVertex("G");

            theGraph.AddEdge(0, 1, 2);

            theGraph.AddEdge(0, 3, 1);

            theGraph.AddEdge(1, 3, 3);

            theGraph.AddEdge(1, 4, 10);

            theGraph.AddEdge(2, 5, 5);

            theGraph.AddEdge(2, 0, 4);

            theGraph.AddEdge(3, 2, 2);

            theGraph.AddEdge(3, 5, 8);

            theGraph.AddEdge(3, 4, 2);

            theGraph.AddEdge(3, 6, 4);

            theGraph.AddEdge(4, 6, 6);

            theGraph.AddEdge(6, 5, 1);

            Console.WriteLine();

            Console.WriteLine("Shortest paths:");

            Console.WriteLine();

            theGraph.Path();

            Console.WriteLine();

        }

    }