这里有没有编程高手阿？

chanel0388la

c++编程,小妹做作业中,有问题请教!谢谢谢谢了``````````

[ 本帖最后由 chanel0388la 于 2006-4-18 00:02 编辑 ]

chanel0388la

学习中

[ 本帖最后由 chanel0388la 于 2006-4-19 08:18 编辑 ]

sagood

/**** START DIJKSTRA ****/
                        while (nodes.Count > 0)
                        {
                                Node u = GetMin(nodes);                // get the minimum node
                                nodes.Remove(u);                        // remove it from the set Q

                                // iterate through all of u's neighbors
                                foreach(EdgeToNeighbor edge in u.Neighbors)
                                        Relax(u, edge.Neighbor, edge.Cost);                // relax each edge
                        }        // repeat until Q is empty
                        /**** END DIJKSTRA ****/



                                           private void Relax(Node uCity, Node vCity, int cost)
                {
                        int distTouCity = (int) dist[uCity.Key];
                        int distTovCity = (int) dist[vCity.Key];                       

                        if (distTovCity > distTouCity + cost)
                        {
                                // update distance and route
                                dist[vCity.Key] = distTouCity + cost;
                                route[vCity.Key] = uCity;
                        }
                }


                                           private Node GetMin(NodeList nodes)
                {
                        // find the node in nodes with the smallest distance value
                        int minDist = Int32.MaxValue;
                        Node minNode = null;
                        foreach(Node n in nodes)
                        {
                                if (((int) dist[n.Key]) <= minDist)
                                {
                                        minDist = (int) dist[n.Key];
                                        minNode = n;
                                }
                        }

                        return minNode;
                }

sagood

Graph.cs

using System;

namespace skmDataStructures.Graph
{
        /// <summary>
        /// The Graph class represents a graph, which is composed of a collection of nodes and edges.  This Graph class
        /// maintains its collection of nodes using the NodeList class, which is a collection of Node objects.
        /// It delegates the edge maintenance to the Node class.  The Node class maintains the edge information using
        /// the adjacency list technique.
        /// </summary>
        public class Graph
        {
                #region Private Member Variables
                // private member variables
                private NodeList nodes;
                #endregion

                #region Constructor
                /// <summary>
                /// Default constructor.  Creates a new Graph class instance.
                /// </summary>
                public Graph()
                {
                        this.nodes = new NodeList();
                }

                /// <summary>
                /// Creates a new graph class instance based on a list of nodes.
                /// </summary>
                /// <param name="nodes">The list of nodes to populate the newly created Graph class with.</param>
                public Graph(NodeList nodes)
                {
                        this.nodes = nodes;
                }
                #endregion

                #region Public Methods
                /// <summary>
                /// Clears out all of the nodes in the graph.
                /// </summary>
                public virtual void Clear()
                {
                        nodes.Clear();
                }

                #region Adding Node Methods
                /// <summary>
                /// Adds a new node to the graph.
                /// </summary>
                /// <param name="key">The key value of the node to add.</param>
                /// <param name="data">The data of the node to add.</param>
                /// <returns>A reference to the Node that was created and added to the graph.</returns>
                /// <remarks>If there already exists a node in the graph with the same <b>key</b> value then an
                /// <b>ArgumentException</b> exception will be thrown.</remarks>
                public virtual Node AddNode(string key, object data)
                {
                        // Make sure the key is unique
                        if (!nodes.ContainsKey(key))
                        {
                                Node n = new Node(key, data);
                                nodes.Add(n);
                                return n;
                        }
                        else
                                throw new ArgumentException("There already exists a node in the graph with key " + key);
                }

                /// <summary>
                /// Adds a new node to the graph.
                /// </summary>
                /// <param name="n">A node instance to add to the graph</param>
                /// <remarks>If there already exists a node in the graph with the same <b>key</b> value as <b>n</b> then an
                /// <b>ArgumentException</b> exception will be thrown.</remarks>
                public virtual void AddNode(Node n)
                {
                        // Make sure this node is unique
                        if (!nodes.ContainsKey(n.Key))
                                nodes.Add(n);
                        else
                                throw new ArgumentException("There already exists a node in the graph with key " + n.Key);
                }
                #endregion

                #region Adding Edge Methods
                /// <summary>
                /// Adds a directed edge from one node to another.
                /// </summary>
                /// <param name="uKey">The <b>Key</b> of the node from which the directed edge eminates.</param>
                /// <param name="vKey">The <b>Key</b> of the node from which the directed edge leads to.</param>
                /// <remarks>If nodes with <b>uKey</b> and <b>vKey</b> do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddDirectedEdge(string uKey, string vKey)
                {
                        AddDirectedEdge(uKey, vKey, 0);
                }

                /// <summary>
                /// Adds a directed, weighted edge from one node to another.
                /// </summary>
                /// <param name="uKey">The <b>Key</b> of the node from which the directed edge eminates.</param>
                /// <param name="vKey">The <b>Key</b> of the node from which the directed edge leads to.</param>
                /// <param name="cost">The weight of the edge.</param>
                /// <remarks>If nodes with <b>uKey</b> and <b>vKey</b> do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddDirectedEdge(string uKey, string vKey, int cost)
                {
                        // get references to uKey and vKey
                        if (nodes.ContainsKey(uKey) && nodes.ContainsKey(vKey))
                                AddDirectedEdge(nodes[uKey], nodes[vKey], cost);
                        else
                                throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
                }

                /// <summary>
                /// Adds a directed edge from one node to another.
                /// </summary>
                /// <param name="u">The node from which the directed edge eminates.</param>
                /// <param name="v">The node from which the directed edge leads to.</param>
                /// <remarks>If the passed-in nodes do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddDirectedEdge(Node u, Node v)
                {
                        AddDirectedEdge(u, v, 0);
                }

                /// <summary>
                /// Adds a directed, weighted edge from one node to another.
                /// </summary>
                /// <param name="u">The node from which the directed edge eminates.</param>
                /// <param name="v">The node from which the directed edge leads to.</param>
                /// <param name="cost">The weight of the edge.</param>
                /// <remarks>If the passed-in nodes do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddDirectedEdge(Node u, Node v, int cost)
                {
                        // Make sure u and v are Nodes in this graph
                        if (nodes.ContainsKey(u.Key) && nodes.ContainsKey(v.Key))
                                // add an edge from u -> v
                                u.AddDirected(v, cost);
                        else                       
                                // one or both of the nodes were not found in the graph
                                throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
                }

                /// <summary>
                /// Adds an undirected edge from one node to another.
                /// </summary>
                /// <remarks>If nodes with <b>uKey</b> and <b>vKey</b> do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddUndirectedEdge(string uKey, string vKey)
                {
                        AddUndirectedEdge(uKey, vKey, 0);
                }

                /// <summary>
                /// Adds an undirected, weighted edge from one node to another.
                /// </summary>
                /// <param name="cost">The weight of the edge.</param>
                /// <remarks>If nodes with <b>uKey</b> and <b>vKey</b> do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddUndirectedEdge(string uKey, string vKey, int cost)
                {
                        // get references to uKey and vKey
                        if (nodes.ContainsKey(uKey) && nodes.ContainsKey(vKey))
                                AddUndirectedEdge(nodes[uKey], nodes[vKey], cost);
                        else
                                throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
                }

                /// <summary>
                /// Adds an undirected edge from one node to another.
                /// </summary>
                /// <remarks>If the passed-in nodes do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddUndirectedEdge(Node u, Node v)
                {
                        AddUndirectedEdge(u, v, 0);
                }

                /// <summary>
                /// Adds an undirected, weighted edge from one node to another.
                /// </summary>
                /// <param name="cost">The weight of the edge.</param>
                /// <remarks>If the passed-in nodes do not exist in the graph, an <b>ArgumentException</b>
                /// exception is thrown.</remarks>
                public virtual void AddUndirectedEdge(Node u, Node v, int cost)
                {
                        // Make sure u and v are Nodes in this graph
                        if (nodes.ContainsKey(u.Key) && nodes.ContainsKey(v.Key))
                        {
                                // Add an edge from u -> v and from v -> u
                                u.AddDirected(v, cost);
                                v.AddDirected(u, cost);
                        }
                        else                       
                                // one or both of the nodes were not found in the graph
                                throw new ArgumentException("One or both of the nodes supplied were not members of the graph.");
                }
                #endregion

                #region Contains Methods
                /// <summary>
                /// Determines if a node exists within the graph.
                /// </summary>
                /// <param name="n">The node to check for in the graph.</param>
                /// <returns><b>True</b> if the node <b>n</b> exists in the graph, <b>False</b> otherwise.</returns>
                public virtual bool Contains(Node n)
                {
                        return Contains(n.Key);
                }

                /// <summary>
                /// Determines if a node exists within the graph.
                /// </summary>
                /// <param name="key">The key of the node to check for in the graph.</param>
                /// <returns><b>True</b> if a node with key <b>key</b> exists in the graph, <b>False</b> otherwise.</returns>
                public virtual bool Contains(string key)
                {
                        return nodes.ContainsKey(key);
                }
                #endregion
                #endregion

                #region Public Properties
                /// <summary>
                /// Returns the number of nodes in the graph.
                /// </summary>
                public virtual int Count
                {
                        get
                        {
                                return nodes.Count;
                        }
                }

                /// <summary>
                /// Returns a reference to the set of nodes in the graph.
                /// </summary>
                public virtual NodeList Nodes
                {
                        get
                        {
                                return this.nodes;
                        }
                }
                #endregion
        }
}

sagood

EdgeToNeighbor.cs

using System;

namespace skmDataStructures.Graph
{
        /// <summary>
        /// EdgeToNeighbor represents an edge eminating from one <see cref="Node"/> to its neighbor.  The EdgeToNeighbor
        /// class, then, contains a reference to the neighbor and the weight of the edge.
        /// </summary>
        public class EdgeToNeighbor
        {
                #region Private Member Variables
                // private member variables
                private int cost;               
                private Node neighbor;
                #endregion

                #region Constructors
                private EdgeToNeighbor() {}

                public EdgeToNeighbor(Node neighbor) : this(neighbor, 0) {}

                public EdgeToNeighbor(Node neighbor, int cost)
                {
                        this.cost = cost;
                        this.neighbor = neighbor;
                }
                #endregion

                #region Public Properties
                /// <summary>
                /// The weight of the edge.
                /// </summary>
                /// <remarks>A value of 0 would indicate that there is no weight, and is the value used when an unweighted
                /// edge is added via the <see cref="Graph"/> class.</remarks>
                public virtual int Cost
                {
                        get
                        {
                                return cost;
                        }
                }

                /// <summary>
                /// The neighbor the edge is leading to.
                /// </summary>
                public virtual Node Neighbor
                {
                        get
                        {
                                return neighbor;
                        }
                }
                #endregion
        }
}

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

sagood

AdjacencyList.cs

using System;
using System.Collections;


namespace skmDataStructures.Graph
{
        /// <summary>
        /// AdjacencyList maintains a list of neighbors for a particular <see cref="Node"/>.  It is derived from CollectionBase
        /// and provides a strongly-typed collection of <see cref="EdgeToNeighbor"/> instances.
        /// </summary>
        public class AdjacencyList : CollectionBase
        {
                /// <summary>
                /// Adds a new <see cref="EdgeToNeighbor"/> instance to the AdjacencyList.
                /// </summary>
                /// <param name="e">The <see cref="EdgeToNeighbor"/> instance to add.</param>
                protected internal virtual void Add(EdgeToNeighbor e)
                {
                        base.InnerList.Add(e);
                }

                /// <summary>
                /// Returns a particular <see cref="EdgeToNeighbor"/> instance by index.
                /// </summary>
                public virtual EdgeToNeighbor this[int index]
                {
                        get { return (EdgeToNeighbor) base.InnerList[index]; }
                        set { base.InnerList[index] = value; }
                }
        }
}

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

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 编辑 ]

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 编辑 ]

橙色坦克

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

Flea

找到高手了么, 我也在找