dfs and bfs in python

1#include<stdio.h>
2#include<stdlib.h>
3 
4#define MAX 100  
5 
6#define initial 1
7#define waiting 2
8#define visited 3
9 
10int n;    
11int adj[MAX][MAX];
12int state[MAX]; 
13void create_graph();
14void BF_Traversal();
15void BFS(int v);
16 
17int queue[MAX], front = -1,rear = -1;
18void insert_queue(int vertex);
19int delete_queue();
20int isEmpty_queue();
21 
22int main()
23{
24	create_graph();
25	BF_Traversal();
26	return 0;
27}
28 
29void BF_Traversal()
30{
31	int v;
32	
33	for(v=0; v<n; v++) 
34		state[v] = initial;
35	
36	printf("Enter Start Vertex for BFS: \n");
37	scanf("%d", &v);
38	BFS(v);
39}
40 
41void BFS(int v)
42{
43	int i;
44	
45	insert_queue(v);
46	state[v] = waiting;
47	
48	while(!isEmpty_queue())
49	{
50		v = delete_queue( );
51		printf("%d ",v);
52		state[v] = visited;
53		
54		for(i=0; i<n; i++)
55		{
56			if(adj[v][i] == 1 && state[i] == initial) 
57			{
58				insert_queue(i);
59				state[i] = waiting;
60			}
61		}
62	}
63	printf("\n");
64}
65 
66void insert_queue(int vertex)
67{
68	if(rear == MAX-1)
69		printf("Queue Overflow\n");
70	else
71	{
72		if(front == -1) 
73			front = 0;
74		rear = rear+1;
75		queue[rear] = vertex ;
76	}
77}
78 
79int isEmpty_queue()
80{
81	if(front == -1 || front > rear)
82		return 1;
83	else
84		return 0;
85}
86 
87int delete_queue()
88{
89	int delete_item;
90	if(front == -1 || front > rear)
91	{
92		printf("Queue Underflow\n");
93		exit(1);
94	}
95	
96	delete_item = queue[front];
97	front = front+1;
98	return delete_item;
99}
100 
101void create_graph()
102{
103	int count,max_edge,origin,destin;
104 
105	printf("Enter number of vertices : ");
106	scanf("%d",&n);
107	max_edge = n*(n-1);
108 
109	for(count=1; count<=max_edge; count++)
110	{
111		printf("Enter edge %d( -1 -1 to quit ) : ",count);
112		scanf("%d %d",&origin,&destin);
113 
114		if((origin == -1) && (destin == -1))
115			break;
116 
117		if(origin>=n || destin>=n || origin<0 || destin<0)
118		{
119			printf("Invalid edge!\n");
120			count--;
121		}
122		else
123		{
124			adj[origin][destin] = 1;
125		}
126	}
127}
128

1def dfs_paths(graph, start, goal, path=None):
2    if path is None:
3        path = [start]
4    if start == goal:
5        yield path
6    for next in graph[start] - set(path):
7        yield from dfs_paths(graph, next, goal, path + [next])
8
9list(dfs_paths(graph, 'C', 'F')) # [['C', 'F'], ['C', 'A', 'B', 'E', 'F']]
10

1def bfs(graph, start):
2    visited, queue = set(), [start]
3    while queue:
4        vertex = queue.pop(0)
5        if vertex not in visited:
6            visited.add(vertex)
7            queue.extend(graph[vertex] - visited)
8    return visited
9
10bfs(graph, 'A') # {'B', 'C', 'A', 'F', 'D', 'E'}
11

1def shortest_path(graph, start, goal):
2    try:
3        return next(bfs_paths(graph, start, goal))
4    except StopIteration:
5        return None
6
7shortest_path(graph, 'A', 'F') # ['A', 'C', 'F']
8