sagood

问题呢？好大的水哦，哈哈

野林歌声

洗澡了。。。。

chanel0388la

:9

[ 本帖最后由 chanel0388la 于 2006-4-23 20:41 编辑 ]

sagood

为什么要用C++，不能用Java或者C#么？

chanel0388la

原帖由 sagood 于 2006-4-18 21:55 发表
为什么要用C++，不能用Java或者C#么？

可以，但是我只会++

sagood

参考一下Java的：
class Vertex
{
   public char label;
   public boolean wasVisited;
   public Vertex(char lab)
   {
      label = lab;
      wasVisited = false;
   }
}

class Graph
{
        private final int MAX_VERTS = 20;
        private Vertex vertexList[];
        private int adjMat[][];
        private int nVerts;

        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;
        }

        public void addVertex(char lab) // argument is label
        {
                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);
        }
}

[ 本帖最后由 sagood 于 2006-4-18 22:09 编辑 ]

Flea

找到高手了么, 我也在找

橙色坦克

Sedgewick的"Algorithms in C++" 第5卷全是图算法，上面有这些东西。这书比较实用，Lehrbuchsammlung有。

sagood

因为是学C#的，所以去找了一下用C#表示的Graph，顺便也给自己复习一下：(不用泛型的)

Node.cs

using System;
using System.Collections;

namespace skmDataStructures.Graph
{
        /// <summary>
        /// A Node is uniquely identified by its string Key.  A Node also has a Data property of type object
        /// that can be used to store any extra information associated with the Node.
        ///
        /// The Node has a property of type AdjacencyList, which represents the node's neighbors.  To add a neighbor,
        /// the Node class exposes an AddDirected() method, which adds a directed edge with an (optional) weight to
        /// some other Node.  These methods are marked internal, and are called by the Graph class.
        /// </summary>
        public class Node
        {
                #region Private Member Variables
                // private member variables
                private string key;
                private object data;               
                private AdjacencyList neighbors;
                #endregion

                #region Constructors
                private Node() {}                // remove default constructor

                public Node(string key, object data) : this(key, data, null) {}

                public Node(string key, object data, AdjacencyList neighbors)
                {
                        this.key = key;
                        this.data = data;
                        if (neighbors == null)
                                this.neighbors = new AdjacencyList();
                        else
                                this.neighbors = neighbors;
                }
                #endregion

                #region Public Methods
                #region Add Methods
                /// <summary>
                /// Adds an unweighted, directed edge from this node to the passed-in Node n.
                /// </summary>
                protected internal virtual void AddDirected(Node n)
                {
                        AddDirected(new EdgeToNeighbor(n));
                }

                /// <summary>
                /// Adds a weighted, directed edge from this node to the passed-in Node n.
                /// </summary>
                /// <param name="cost">The weight of the edge.</param>
                protected internal virtual void AddDirected(Node n, int cost)
                {
                        AddDirected(new EdgeToNeighbor(n, cost));
                }

                /// <summary>
                /// Adds an edge based on the data in the passed-in EdgeToNeighbor instance.
                /// </summary>
                protected internal virtual void AddDirected(EdgeToNeighbor e)
                {
                        neighbors.Add(e);
                }
                #endregion
                #endregion

                #region Public Properties
                /// <summary>
                /// Returns the Node's Key.
                /// </summary>
                public virtual string Key
                {
                        get
                        {
                                return key;
                        }
                }

                /// <summary>
                /// Returns the Node's Data.
                /// </summary>
                public virtual object Data
                {
                        get
                        {
                                return data;
                        }
                        set
                        {
                                data = value;
                        }
                }

                /// <summary>
                /// Returns an AdjacencyList of the Node's neighbors.
                /// </summary>
                public virtual AdjacencyList Neighbors
                {
                        get
                        {
                                return neighbors;
                        }
                }
                #endregion
        }
}

[ 本帖最后由 sagood 于 2006-4-18 23:30 编辑 ]

sagood

NodeList.cs

using System;
using System.Collections;

namespace skmDataStructures.Graph
{
        /// <summary>
        /// The NodeList class represents a collection of nodes.  Internally, it uses a Hashtable instance to provide
        /// fast lookup via a <see cref="Node"/> class's <b>Key</b> value.  The <see cref="Graph"/> class maintains its
        /// list of nodes via this class.
        /// </summary>
        public class NodeList : IEnumerable
        {
                // private member variables
                private Hashtable data = new Hashtable();

                #region Public Methods
                /// <summary>
                /// Adds a new Node to the NodeList.
                /// </summary>
                public virtual void Add(Node n)
                {
                        data.Add(n.Key, n);
                }

                /// <summary>
                /// Removes a Node from the NodeList.
                /// </summary>
                public virtual void Remove(Node n)
                {
                        data.Remove(n.Key);
                }

                /// <summary>
                /// Determines if a node with a specified <b>Key</b> value exists in the NodeList.
                /// </summary>
                /// <param name="key">The <b>Key</b> value to search for.</param>
                /// <returns><b>True</b> if a Node with the specified <b>Key</b> exists in the NodeList; <b>False</b> otherwise.</returns>
                public virtual bool ContainsKey(string key)
                {
                        return data.ContainsKey(key);
                }

                /// <summary>
                /// Clears out all of the nodes from the NodeList.
                /// </summary>
                public virtual void Clear()
                {
                        data.Clear();
                }

                /// <summary>
                /// Returns an enumerator that can be used to iterate through the Nodes.
                /// </summary>
                /// <returns></returns>
                public IEnumerator GetEnumerator()
                {
                        return new NodeListEnumerator(data.GetEnumerator());
                }
                #endregion

                #region Public Properties
                /// <summary>
                /// Returns a particular <see cref="Node"/> instance by index.
                /// </summary>
                public virtual Node this[string key]
                {
                        get
                        {
                                return (Node) data[key];
                        }
                }

                /// <summary>
                /// Returns the number of nodes in the NodeList.
                /// </summary>
                public virtual int Count
                {
                        get
                        {
                                return data.Count;
                        }
                }
                #endregion

                #region NodeList Enumerator
                /// <summary>
                /// The NodeListEnumerator method is a custom enumerator for the NodeList object.  It essentially serves
                /// as an enumerator over the NodeList's Hashtable class, but rather than returning DictionaryEntry values,
                /// it returns just the Node object.
                /// <p />
                /// This allows for a developer using the Graph class to use a foreach to enumerate the Nodes in the graph.
                /// </summary>
                public class NodeListEnumerator : IEnumerator, IDisposable
                {
                        IDictionaryEnumerator list;
                        public NodeListEnumerator(IDictionaryEnumerator coll)
                        {
                                list = coll;                               
                        }

                        public void Reset()
                        {
                                list.Reset();
                        }

                        public bool MoveNext()
                        {
                                return list.MoveNext();
                        }

                        public Node Current
                        {
                                get
                                {
                                        return (Node) ((DictionaryEntry) list.Current).Value;
                                }
                        }

                        // The current property on the IEnumerator interface:
                        object IEnumerator.Current
                        {
                                get
                                {
                                        return (Current);
                                }
                        }
                  
                        public void Dispose()
                        {                       
                                list = null;
                        }
                }
                #endregion
        }
}

[ 本帖最后由 sagood 于 2006-4-18 23:31 编辑 ]