Graph

Graph and its representations

Graph is a data structure that consists of following two components:

• A finite set of vertices
• A finite set of ordered pair of the form (u,v) called as edge.

two types of graphs(n nodes) in terms of size

• sparse graph: with O(n) nodes;
• dense graph : with O(n^2) edges.

Two most commomly used representations of graph

• Adjacency Matrix
  • a(i,j) is true or false: represent if exist a edge from i to j;
  • a(i,j) is a number x: represent that the edge from i to j is weighted of x.
• Adjacency List
  • for each node v is the graph, maintain a list consisting of the head points from v;
• Comparison
  • Adjacency can quickly check whether exist a edge(u,v);
  • Adjacency List deals with large sparse graph, and can search the graph quickly.

Path and Reachable

A path a set of edges in graph G(V, E); Given two vertex u and v in graph G(V, E), v is reachable from u iff there is a path from u to v.

Search a graph

• We can imagine that every vertex in graph is a person, and we are trying to find some person x in the graph.
• So we pass a message(“to find person x”) to one person and check if he is exactly the one we want;
• If he is, we end this search; else he pass the message to person he heads to and try to ;
• Here is just a matter of how the message is passes across the graph;
• Every time we pass the message to another person, we want the guy to tell us if he can find person x;

Find one certain vertex in graph

We define a message called find vertex x; The message is passed across the graph; All vertices once received the message is called known vertex.

• DFS(Depth-First-Search) Every time person u just pass the message to one person v he trust most(just one certain order), and let person v helps to do the same thing; If v return “got x”; Else, v failed to find x, person u pass the message to another person he heads to; And we do this steps recursively until we find person x, or we can not find x even though we walk through all the graph.

• BFS(Breadth-First-Search) It like Broadcasting. We start at one person s(source vertex), and broadcast the message to all its head-points. All the known vertices do the same broadcasting one by one; Once one vertex got the message is x(the person we want), the return message to the vertex where x got the message; The the “I am x, I am here” message is passed back to the source.

Visit all the vertices in graph

• Differences between visiting all and visiting one +
• DFS +
• BFS

  #

Topo

C code for adjacency list representation of an undirected graph

// A C Program to demonstrate adjacency list representation of graphs	
#include <stdio.h>
#include <stdlib.h>

// A structure to represent an adjacency list node
struct AdjListNode
{
	int dest;
	struct AdjListNode* next;
};

// A structure to represent an adjacency liat
struct AdjList
{
	struct AdjListNode *head; // pointer to head node of list
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
struct Graph
{
	int V;
	struct AdjList* array;
};

// A utility function to create a new adjacency list node
struct AdjListNode* newAdjListNode(int dest)
{
	struct AdjListNode* newNode =
			(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
	newNode->dest = dest;
	newNode->next = NULL;
	return newNode;
}

// A utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
	struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
	graph->V = V;

	// Create an array of adjacency lists. Size of array will be V
	graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));

	// Initialize each adjacency list as empty by making head as NULL
	int i;
	for (i = 0; i < V; ++i)
		graph->array[i].head = NULL;

	return graph;
}

// Adds an edge to an undirected graph
void addEdge(struct Graph* graph, int src, int dest)
{
	// Add an edge from src to dest. A new node is added to the adjacency
	// list of src. The node is added at the begining
	struct AdjListNode* newNode = newAdjListNode(dest);
	newNode->next = graph->array[src].head;
	graph->array[src].head = newNode;

	// Since graph is undirected, add an edge from dest to src also
	newNode = newAdjListNode(src);
	newNode->next = graph->array[dest].head;
	graph->array[dest].head = newNode;
}

// A utility function to print the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
	int v;
	for (v = 0; v < graph->V; ++v)
	{
		struct AdjListNode* pCrawl = graph->array[v].head;
		printf("\n Adjacency list of vertex %d\n head ", v);
		while (pCrawl)
		{
			printf("-> %d", pCrawl->dest);
			pCrawl = pCrawl->next;
		}
		printf("\n");
	}
}

// Driver program to test above functions
int main()
{
	// create the graph given in above fugure
	int V = 5;
	struct Graph* graph = createGraph(V);
	addEdge(graph, 0, 1);
	addEdge(graph, 0, 4);
	addEdge(graph, 1, 2);
	addEdge(graph, 1, 3);
	addEdge(graph, 1, 4);
	addEdge(graph, 2, 3);
	addEdge(graph, 3, 4);

	// print the adjacency list representation of the above graph
	printGraph(graph);

	return 0;
}

public class Teisei {
    public static void main(String args[]){
        System.out.println("Hello world! This is Teisei's blog");
    }
}