CS计算机代考程序代写 data structure algorithm COMP2521

COMP2521
Data Structures & Algorithms

Week 7.2
Directed & Weighted Graphs

 

1

In this lecture

Why?

In the real world graph, edges often have a sense of
direction, and also a sense of cost to traverse.

What?

Directed Graphs
Weighted graphs

 

2

A more common graph

Often, graphs don’t look like the one on the left. They look like the
one on the right. They have directions and weights.

 

3

Directed graphs (Digraphs)

Digraphs are very similar to normal graphs, except that edges have a
sense of direction such that:

v → w   ≠   w → v
 

4 . 1

Digraph Properties

Directed path, directed cycle, as you expect
Degree of a vertex:

Outdegree: deg(v) = number of edges of the form (v, _)
Indegree: deg^-1(v) = number of edges of the form (_, v)

Reachability: w is reachable from v if there is directed path v,…,w
Strong connectivity: every vertex is reachable from every other
vertex
Directed acyclic graph: contains no directed cycles

4 . 2

Digraph Implementations

Virtually the same as undirected graphs, except the edge pairs
have a sense of direction

Array of edges Adjacency Matrix Adjacency List
Space usage E V^2 V + E
Insert edge E 1 deg(v)
exists edge (v,w) E 1 deg(v)
get edges leaving v E V deg(v)

4 . 3

Digraph Implementations

4 . 4

Traversing

Identical to undirected graphs

4 . 5

Weighted Graphs

Weighted graphs are similar to our previous graphs, except the edges
have a sense of COST / WEIGHT.

 
Generally speaking, this means that when we traverse the graph

certain edges will be “cheaper” to explore than others.
 

Each edge is now (s, t, w) instead of (s, t)

5 . 1

Weighted Graphs

Weighted graphs have substantially more parallels to reality:

5 . 2

Weighted Graphs

There are two main problems we try to solve with weighted graphs:
 

1. Cheapest way to connect all vertices (minimal spanning tree
problem) – for undirected weighted graphs

 
2. Cheapest way to get from A to B (shortest path problem) – for

directed weighted graphs
 

We will cover these in more detail.

5 . 3

Weighted Graphs

Adjacency Matrix Representation

5 . 4

Weighted Graphs

Adjacency List Representation

5 . 5

Weighted Graphs

Array/List of Edges Representation

5 . 6

Key changes to ADT/implementation
Graph.h

// edges are pairs of vertices (end-points) plus weight
typedef struct Edge {
Vertex v;
Vertex w;
int weight;
} Edge;

// returns weight, or 0 if vertices not adjacent
int GraphAdjacent(Graph, Vertex, Vertex);

1
2
3
4
5
6
7
8
9

typedef struct GraphRep {
int **edges; // adjacency matrix storing weights
// 0 if nodes not adjacent
int nV; // #vertices
int nE; // #edges
} GraphRep;

int GraphAdjacent(Graph g, Vertex v, Vertex w) {
assert(valid graph, valid vertices)
return (g->edges[v][w] != 0);
}

void GraphEdgeInsert(Graph g, Edge e) {
assert(valid graph, valid edge)
// edge e not already in graph
if (g->edges[e.v][e.w] == 0) g->nE++;
// may change weight of existing edge
g->edges[e.v][e.w] = e.weight;
g->edges[e.w][e.v] = e.weight;
}

void GraphEdgeRemove(Graph g, Edge e) {
assert(valid graph, valid edge)
// edge e not in graph
if (g->edges[e.v][e.w] == 0) return;
g->edges[e.v][e.w] = 0;
g->edges[e.w][e.v] = 0;
g->nE–;
}

1
2
3
4
5
6
7
8
9

10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Graph.c

5 . 7

Feedback

6