CmSc 125Preview of Computer Science

Basic Graph Concepts

A graph is a mathematical object that is used to model different situations – objects and processes:

City map

Electric circuits

Course curriculum

Definition: A graph is a collection (nonempty set) of vertices (nodes) and edges

Nodes: can have names and properties

Edges: connect two nodes, can be labeled, can be directed

Example:

Nodes:A,B,C,D

Edges:AB, AC, BC, CD

GRAPH1:

Same graph given in another way:

A path from nodex to nodey : a list of nodes in which successive nodes are connected by edges

Some paths in the above example are:A B C D, A C B A C D, A B, D C B, C B A

Graph representation: adjacency lists or matrix

Adjacency lists:

Matrix

Graph Algorithms: Spanning Trees and Minimum Spanning Trees

Problem:

Here is a diagram of a prison for political dissidents. The prisoners have been divided into seven groups as shown. A spy plans to help all the prisoners escape by blowing up the gates in the prison walls. Due to the danger of this plan, he wants to destroy as few gates as possible and still allow all prisoners to escape. How many gates must be blasted to do this?

The information can be represented as a graph, and the spanning tree will give the solution.

1. Spanning tree: a tree that contains all nodes in the graph.

Number of nodes: |V|

Number of edges: |V|-1

Algorithm to find a spanning tree

Data structures needed:

A table (an array) T with size = number of nodes, where Ti = parent of node vi

Graph representation (adjacency lists, matrix)

A queue of nodes to be processed

Algorithm

  1. Choose a node u and store it in the queue. Set a counter = 0 , and Tu = r (u would be the root of the tree)
  2. While the queue is not empty and counter < |V| -1 do the following:

Read a node vjfrom the queue.

For each uk in the adjacency list of vj do the following

If Tkis empty,

Tk = vj,

counter = counter + 1

store uk in the queue

2. Minimum Spanning Tree

Problem:

Agents A, B, C, D, E, F, G, and H are political conspirators in what has become known as the "Blottergate Affair". In order to coordinate their cover-up efforts, it is vital that each agent is able to communicate directly or indirectly with every other conspirator. Such communications involve a certain amount of risk to everyone. Below is the table of "risk factors" associated with direct communication between the indicated parties. All other direct communications are too likely to expose the cover-up scheme. What is the least total risk involved in a connecting system?

Agent pairs / A
B / A
C / A
E / A
F / A
G / B
C / B
F / C
D / C
F / C
G / C
H / D
E / D
H / E
H
Risk factors / 9 / 3 / 8 / 3 / 4 / 10 / 6 / 6 / 4 / 5 / 7 / 6 / 3 / 5

Given: weighted graph.

Find a spanning tree with the minimal sum of weights.

Kruskal's Algorithm

Kruskal's algorithm works with tree forests and the set of edges.

Each node belongs to only one tree in the forest.

Initially we build |V| trees consisting of one node only - each node is a tree of its own.

The basic operation of the algorithm is to choose an edge (u,v) from the set of edges with minimal weight (and remove the edge from the set) . This is implemented by storing the edges in a priority queue, with priority = the weight of the edge.

1