Graphs (BFS and TFS)

[Scott Dabot]

I am trying to write a program that uses graphs and I have this
algorithm for the Depth First Search.

//Input: Graph G=(V, E)
//Output Graph G with its vertices marked with consecutive integers in
//the order they've been first encountered by the DFS traversal mark
//each vertex in V with 0 as a mark of being "unvisited"

count<--0

for each vertex v in V do
if v is marked with 0 dfs(v)


algorithm for dfs
//visits recursively all the unvisited vertices connected to vertex v
and then assigns them the numers in the order they are encountered via
global variable count

count<-- count +1; mark v with count

for each vertex w in V adjacent to v do
if w is marked with 0
dfs(w)

My question is the first algorithm DFS(G), takes in a graph , and then
says a Graph is G(V,E)... What type of data structure is a graph, that u
can pass it in as a Graph and then it has a V(vertice) and E ( edge). I
also have the algorithm for the BFS but it takes in a Graph too. I do
not know exactly what a Graph data structure is so therefore i can't use
the algorithm. Any help is greatly appreciated.

 

[Michael Mair]

I am trying to write a program that uses graphs and I have this
algorithm for the Depth First Search.

//Input: Graph G=(V, E)
//Output Graph G with its vertices marked with consecutive integers in
//the order they've been first encountered by the DFS traversal mark
//each vertex in V with 0 as a mark of being "unvisited"

count<--0

for each vertex v in V do
if v is marked with 0 dfs(v)


algorithm for dfs
//visits recursively all the unvisited vertices connected to vertex v
and then assigns them the numers in the order they are encountered via
global variable count

count<-- count +1; mark v with count

for each vertex w in V adjacent to v do
if w is marked with 0
dfs(w)

My question is the first algorithm DFS(G), takes in a graph , and then
says a Graph is G(V,E)... What type of data structure is a graph, that u
can pass it in as a Graph and then it has a V(vertice) and E ( edge). I
also have the algorithm for the BFS but it takes in a Graph too. I do
not know exactly what a Graph data structure is so therefore i can't use
the algorithm. Any help is greatly appreciated.

Please note that algorithmical and related questions are mostly offtopic
round here, especially if you have not given us C code to comment on.
For general information, ask rather in *.program* newsgroups.

Your example looks like the definitions from a lecture, so probably
they tell you about graph representation, too. Maybe you can go from
there.
Depending on what you want to do with your graph and what you know
about your graph, there are several ways to represent it; just google
for these keywords
- Adjacency Matrix
- Incidence Matrix
- Edge Representation
In case of sparse matrices, you can just use the sparse matrix
representation or do everything equivalently by data structures
of your own, say linked lists for either the vertices or the edges
or both containing additional data as you need it.
For searching the vertices with dfs or bfs, I would just use the
adjacency matrices or related sparse structures, as they usually
are defined only in terms of vertices which makes applying the
abstract algorithm easier; in addition, for graphs with O(|V|^s),
s>1, edges you have smaller matrices most of the time.


Cheers
Michael

 

[CBFalconer]

I am trying to write a program that uses graphs and I have this
algorithm for the Depth First Search.

.... snip ...

You are in the wrong newsgroup. Try comp.programming. Around here
we limit discussion the the standardized portable C language.

 

[Elliott Back]

I am trying to write a program that uses graphs and I have this
algorithm for the Depth First Search.

//Input: Graph G=(V, E)
//Output Graph G with its vertices marked with consecutive integers in
//the order they've been first encountered by the DFS traversal mark
//each vertex in V with 0 as a mark of being "unvisited"

count<--0

for each vertex v in V do
if v is marked with 0 dfs(v)


algorithm for dfs
//visits recursively all the unvisited vertices connected to vertex v
and then assigns them the numers in the order they are encountered via
global variable count

count<-- count +1; mark v with count

for each vertex w in V adjacent to v do
if w is marked with 0
dfs(w)

My question is the first algorithm DFS(G), takes in a graph , and then
says a Graph is G(V,E)... What type of data structure is a graph, that u
can pass it in as a Graph and then it has a V(vertice) and E ( edge). I
also have the algorithm for the BFS but it takes in a Graph too. I do
not know exactly what a Graph data structure is so therefore i can't use
the algorithm. Any help is greatly appreciated.

A graph is a set of nodes and vertices. If you don't care about
performance, just write a linked list of nodes:

typedef struct _node{
void *data;
void *vertex_list;
void *next_node;
} node;

typedef struct _graph{
node* first;
node* last;
}