### Archive

Posts Tagged ‘graphs’

## Find a path between two vertices using Python

Representation of the graphs and their usage is very easy with the concept of Dictionaries in Python. Dictionaries come very handy in representing Graphs in Adjacency list form.

Here is the Python code:

```def Graph():
graph={}
size1=int(raw_input('Enter the size of the graph:'))

for i in range(size1):
node=(raw_input('Enter a node:'))

visited={}
for i in graph.keys():
visited[i]=False
print visited
start=raw_input('Enter start vertex:')
end=raw_input('Enter start vertex:')
print find_path(graph,start,end)

def find_path(graph,start,end, path=[]) :
path=path+[start]
if start==end :
return path
if not graph.has_key(start) :
return None
else :
for node in graph[start] :
if node not in path:
newpath = find_path(graph, node, end, path)
if newpath :
return newpath
return None

def main() :
Graph()

if __name__=='__main__' :
main()
```

## Adjacency list represention of graph in Java

Here is the program for adjacency list representation of graphs using java. If you are new to Graphs please read about graphs here before reading the rest of this post.

I used a List data structure inside the graph. I think much explanation is not required because it is very simple.

```import java.io.BufferedReader;
import java.io.IOException;

/**
*
* @author Vasanth Raja Chittampally
*/
class List{
int node;
List next;
}

class Node {
int node;
}

public class Graphs {
void insertVertices() throws IOException
{
System.out.println("Enter number of nodes in a graph: ");
Node g[]=new Node[n];
for (int i = 0; i < n; i++) {
g[i]=new Node();
g[i].node=i+1;
g[i].visit=false;
while(true)
{
System.out.println("Enter zero to stop");
System.out.println("Enter adjacent nodes to node "+(i+1)+" :");
break;
else
{
List l=new List();
l.next=null;
{
}
else
{
while(p.next!=null){
p=p.next;
}
p.next=l;
}
}
}
}
for (int i = 0; i < n; i++) {
System.out.print(g[i].node+" --> ");
while(l!=null)
{
System.out.print(l.node+" --> ");
l=l.next;
}
System.out.println("");
}
}

public static void main(String[] args) throws IOException {
new Graphs().insertVertices();
}

}
```