برنامه ی پیمایش سطحی Bfs

shirini_forush

shirini_forush

Well-Known Member
بفرمایید. این یه مثال خیلی خوب برای cpp بید...

PHP: 
<?
#include <iostream>
using namespace std;
struct node {
	int info;
	node *next;
};
class Queue {
	public:
		Queue();
		~Queue();
		bool isEmpty();
		void add(int);
		int get();
	private:
		node *first, *last;
};
class Graph {
	public:
		Graph(int size = 2);
		~Graph();
		bool isConnected(int, int);
		// adds the (x, y) pair to the edge set
		void addEdge(int x, int y);
		// performs a Breadth First Search starting with node x
		void BFS(int x);
		// searches for the minimum length path
		// between the start and target vertices
		void minPath(int start, int target);
	private :
		int n;
		int **A;
};
Queue::Queue() {
	first = new node;
	first->next = NULL;
	last = first;
}
Queue::~Queue() {
	delete first;
}
bool Queue::isEmpty() {
	return (first->next == NULL);
}
void Queue::add(int x) {
	node *aux = new node;
	aux->info = x;
	aux->next = NULL;
	last->next = aux;
	last = aux;
}
int Queue::get() {
	node *aux = first->next;
	int value = aux->info;
	first->next = aux->next;
	if (last == aux) last = first;
	delete aux;
	return value;
}
Graph::Graph(int size) {
	int i, j;
	if (size < 2) n = 2;
	else n = size;
	A = new int*[n];
	for (i = 0; i < n; ++i)
		A[i] = new int[n];
	for (i = 0; i < n; ++i)
		for (j = 0; j < n; ++j)
			A[i][j] = 0;
}
Graph::~Graph() {
	for (int i = 0; i < n; ++i)
		delete [] A[i];
	delete [] A;
}
bool Graph::isConnected(int x, int y) {
	return (A[x-1][y-1] == 1);
}
void Graph::addEdge(int x, int y) {
	A[x-1][y-1] = A[y-1][x-1] = 1;
}
void Graph::BFS(int x) {
	Queue Q;
	bool *visited = new bool[n+1];
	int i;
	for (i = 1; i <= n; ++i)
		visited[i] = false;
	Q.add(x);
	visited[x] = true;
	cout << "Breadth First Search starting from vertex ";
	cout << x << " : " << endl;
	while (!Q.isEmpty()) {
		int k = Q.get();
		cout << k << " ";
		for (i = 1; i <= n; ++i)
			if (isConnected(k, i) && !visited[i]) {
				Q.add(i);
				visited[i] = true;
			}
	}
	cout << endl;
	delete [] visited;
}
void Graph::minPath(int start, int target) {
	Queue Q;
	int i, p, q;
	bool found;
	struct aux { int current, prev; };
	aux *X = new aux[n+1];
	int *Y = new int[n+1];
	bool *visited = new bool[n+1];
	for (i = 1; i <= n; ++i)
		visited[i] = false;
	Q.add(start);
	visited[start] = true;
	found = false;
	p = q = 0;
	X[0].current = start;
	X[0].prev = 0;
	while (!Q.isEmpty() && !found) {
		int k = Q.get();
		for (i = 1; i <= n && !found; ++i)
			if (isConnected(k, i) && !visited[i]) {
				Q.add(i);
				++q;
				X[q].current = i;
				X[q].prev = p;
				visited[i] = true;
				if (i == target) found = true;
			}
		++p;
	}
	cout << "The minimum length path from " << start;
	cout << " to " << target << " is : " << endl;
	p = 0;
	while (q) {
		Y[p] = X[q].current;
		q = X[q].prev;
		++p;
	}
	Y[p] = X[0].current;
	for (q = 0; q <= p/2; ++q) {
	int temp = Y[q];
		Y[q] = Y[p-q];
		Y[p-q] = temp;
	}
	for (q = 0; q <= p; ++q)
		cout << Y[q] << " ";
	cout << endl;
	cout << "Length = " << q-1 << endl;
	delete [] visited;
	delete [] X;
	delete [] Y;
}
 
shirini_forush

shirini_forush

Well-Known Member
اینم اون java ه:
PHP: 
import java.util.Vector;

public class BreadthFirstSearch extends SearchApplet {

    public void init() {

	// Define a test network before calling the super class 'init':
	addNode("0", 0.0f, 0.0f);
	addNode("1", 1.0f, 1.0f);
	addNode("2", 5.0f, 2.0f);
	addNode("3", 2.0f, 5.0f);
	addNode("4", 7.0f, 5.0f);
	addNode("5", 8.0f, 8.0f);
	addNode("6", 10.0f, 5.0f);
	addNode("7", 8.0f, 2.0f);
	addNode("8", 12.0f, 8.0f);
	addNode("9", 13.0f, 5.0f);

	addLink(0,1);
	addLink(1,2);
	addLink(2,3);
	addLink(2,4);
	addLink(4,5);
	addLink(4,6);
	addLink(6,8);
	addLink(8,9);
	addLink(2,7);
	addLink(7,9);

	// Now that we have defined the network to search, we
	// can now call the super class init:
	super.init();
    }

    /** findPath - abstract method in super class */
    // Breadth first search  algorithm from "Algorithms"
    // (Cormen, Leiserson, Rivest) page 460:
    public int [] findPath(int node_1, int node_2) { // return an array of node indices
	System.out.println("Entered BreadthFirstSearch.findPath(" +
			   node_1 + ", " + node_2 + ")");
	if (node_1 == node_2)  {
	    repaintPath(null, 0);
	    return null;
	}
	// data structures for depth first search:
	boolean [] visitedFlag = new boolean[numNodes];
	float [] distanceToNode = new float[numNodes];
	int [] predecessor = new int[numNodes];
	Queue queue = new Queue(numNodes + 2);

	// data structures for graphical display (only):
	int [] display_path = new int[2 * numNodes + 1];
	int num_display_path = 0;

	for (int i=0; i<numNodes; i++) {
	    visitedFlag[i] = false;
	    distanceToNode[i] = 10000000.0f;
	    predecessor[i] = -1;
	}

	visitedFlag[node_1] = true;
	distanceToNode[node_1] = 0.0f;
	queue.enqueue(node_1);
outer:	while (queue.isEmpty() == false) {
	    int head = queue.head();
	    int [] connected = connected_nodes(head);
	    if (connected != null) {
		for (int i=0; i<connected.length; i++) {
		    if (visitedFlag[connected[i]] == false) {
			distanceToNode[connected[i]] = distanceToNode[head] + 1.0f;
			predecessor[connected[i]] = head;
			queue.enqueue(connected[i]);
			display_path[num_display_path++] = head;
			display_path[num_display_path++] = connected[i];
			repaintPath(display_path, num_display_path);
			if (connected[i] == node_2) break outer; // we are done
		    }
		}
		visitedFlag[head] = true;
		queue.dequeue(); // ignore return value
	    }
	}
	// now calculate the shortest path from the predecessor array:
	int [] ret = new int[numNodes + 1];
	int count = 0;
	ret[count++] = node_2;
	for (int i=0; i<numNodes; i++) {
	    ret[count] = predecessor[ret[count - 1]];
	    count++;
	    if (ret[count - 1] == node_1)  break;  // back to starting node
	}
	num_display_path = 0;
	int [] ret2 = new int[count];
	for (int i=0; i<count; i++) {
	    ret2[i] = ret[count - 1 - i];
	    if (i > 0) { // re-calculate the plot display points:
		display_path[num_display_path++] = ret2[i-1];
		display_path[num_display_path++] = ret2[i];
	    }
	}
	// now re-calculate the display path points:
	repaintPath(display_path, num_display_path);
	return ret2;   
    }

    // Queue algorithm from "Algorithms" (Cormen, Leiserson, Rivest) page 202:
    protected class Queue {
	public Queue(int num) {
	    queue = new int[num];
	    head = tail = 0;
	    len = num;
	}
	public Queue() {
	    this(400);
	}
	private int [] queue;
	int tail, head, len;
	public void enqueue(int n) {
	    queue[tail] = n;
	    if (tail >= (len - 1)) {
		tail = 0;
	    } else {
		tail++;
	    }
	}
	public int dequeue() {
	    int ret = queue[head];
	    if (head >= (len - 1)) {
		head = 0;
	    } else {
		head++;
	    }
	    return ret;
	}
	public boolean isEmpty() {
	    return head == (tail + 1);
	}
	public int head() {
	    return queue[head];
	}	
    }

    protected int [] connected_nodes(int node) {
	int [] ret = new int[SearchApplet.MAX];
	int num = 0;

	for (int n=0; n<numNodes; n++) {
	    boolean connected = false;
	    // See if there is a link between node 'node' and 'n':
	    for (int i=0; i<numLinks; i++) {
		if (link_1[i] == node) {
		    if (link_2[i] == n) {
			connected = true;
			break;
		    }
		}
		if (link_2[i] == node) {
		    if (link_1[i] == n) {
			connected = true;
			break;
		    }
		}
	    }
	    if (connected) {
		ret[num++] = n;
	    }
	}
	if (num == 0)  return null;
	int [] ret2 = new int[num];
	for (int i=0; i<num; i++) {
	    ret2[i] = ret[i];
	}
	return ret2;
    }
		
    private int [] path = new int[SearchApplet.MAX];
    private int num_path = 0;

    private int [] copy_path(int [] path, int num_to_copy) {
	int [] ret = new int[SearchApplet.MAX];
	for (int i=0; i<num_to_copy; i++) {
	    ret[i] = path[i];
	}
	return ret;
    }


}
 
B

bahare_22

New Member
برنامه این 2 تا error رو میده LIBCD.lib(crt0.obj) : error LNK2001: unresolved external symbol _main

Debug/dsad.exe : fatal error LNK1120: 1 unresolved externals

اگه ممکنه راهنماییم کنید خیلی وقت ندارم
 
shirini_forush

shirini_forush

Well-Known Member
ممنون این برنامه همین برنامه ی bfs به کمک صف هستش ؟
کلیک کنید تا باز شود...

خیلی ببخشید میپرسم... شما درباره bfs و پیمایش کلا اطلاعات دارید؟
من میخواستم سودو کد بفرستم براتون :-?
توصیه میکنم کتاب Introduction to algorithm رو حتما بخونید...

برنامه این 2 تا error رو میده LIBCD.lib(crt0.obj) : error LNK2001: unresolved external symbol _main

Debug/dsad.exe : fatal error LNK1120: 1 unresolved externals

اگه ممکنه راهنماییم کنید خیلی وقت ندارم
کلیک کنید تا باز شود...

من تست کردم مورد نداشت...
البته احتمال میدم به خاطر اون علامت اضافی "?>" تو خط اوله.
اون رو بردارید. اون اضافیه.
 
P

parvin_nik11

New Member
از رو شکل اره اما برنامه شو نه اصلا استادمون بهمون برنامه نویسی و یاد نداده ازمون برنامه می خواد
 
shirini_forush

shirini_forush

Well-Known Member
شما چند تا user درست کردی؟ :lol: :-?
در مورد اول شما هم سودو کد bfs خالی به استادتون تا چشمش درآد!
در مورد دوم ممکنه...
(فکر کنم VC++ استفاده میکنید. DEVC++ رو هم امتحان کنید...)
 
shirini_forush

shirini_forush

Well-Known Member
اینم سودوکد:
کد: 
for (all vertices 1<= i <= n) do
visited [ i ] = false
ADD x to Queue
visited [ x ] = true
while (Queue is not empty) do
extract information from the Queue to variable k
display k
for (all vertices 1<= i <= n) do
if (visited[ i ] == false AND there is an edge between k and i) then
ADD i to Queue
visited [ i ] = true
end if
end while
 
P

parvin_nik11

New Member
ممنون از کمکتون . پس با این گفته ی شما مشکل از برنامه نیست از کامپایلر هستش
 
برای ارسال پاسخ شما باید وارد سیستم شوید.

آخرین مطالب مجیدآنلاین

جدیدترین ارسال ها

بالا